78192

Алгоритмы поиска с возвращением

Лекция

Информатика, кибернетика и программирование

Рассмотрим общий случай, когда решение задачи имеет вид вектора (а1, а2,), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое аi является элементом некоторого конечного линейно упорядоченного множества

Русский

2015-02-07

87.5 KB

8 чел.

екция: Алгоритмы поиска с возвращением                                                4 из 4 с.

Оглавление

[1] Оглавление

[2] Алгоритм поиска с возвращением

[2.1] Обходы ордерева в глубину и в ширину

[2.2] Обходы графа в глубину и в ширину

[2.3] Контрольные вопросы

Лекция №23

Алгоритм поиска с возвращением

Рассмотрим общий случай, когда решение задачи имеет вид вектора 1, а2,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое аi является элементом некоторого конечного линейно упорядоченного множества  Аi . Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества  А1  А2 … Аi   для любого i, где ir , и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из А1 являются кандидатами для их рассмотрения в качестве а1 (множество таких элементов а1 из А1  ниже обозначается через а1). В качестве а1 выбирается наименьший элемент множества S1, что приводит к частичному решению (а1) . В общем случае ограничения, описывающие решения, говорят о том, из какого подмножества Sk  множества Аk  выбираются кандидаты для расширения частичного решения от 1, а2,… , аk-1) до 1, а2,… , аk-1, аk) . Если частичное решение 1, а2,… , аk-1) не предоставляет других возможностей для выбора нового аk (т.е. у частичного решения 1, а2,… , аk-1) 
либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента 
аk-1 из Sk-1 . Если новый элемент аk-1   выбрать нельзя, т.е. к данному моменту множество Sk-1  уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент аk-2  и т.д.

Общую схему алгоритма, осуществляющего поиск с возвращением для нахождения всех решений, можно представить в следующем виде:

k:=1; 
Вычислить S1 (*например, в качестве S1 взять А1  *); 
while k>0 do 
    while не пусто Sk do 
        (* Продвижение *) 
        В качестве 
аk взять наименьший элемент из Sk , удалив его из Sk  
        if (а1, а2,… , аk)  является решением 
        then Записать это решение 
        
end
        if  k<r then 
           
k := k + 1; Вычислить Sk 
            (* Например, в качестве 
Sk можно взять Аk  *) 
        end 
    end
    (* Возврат *)
k := k - 1 
end
(* Все решения найдены *) 

Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:

procedure ПОИСК (X: ВЕКТОР; i : Integer); 
begin 
        if  Х является решением then записать его end
        if  i <= r then 
               
Вычислить Si 
                for all from Si  do ПОИСК (X || (a),i+1) end 
        end 
end

Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е. 
(
а1, а2,… , аn) || (b1, b2,… , bm)= (а1, а2,… , аn,,b1, b2,… , bm) и () || (а1) для любых а1, а2,… , аn,,b1, b2,… , bm.

Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а1, а2, а3, а4, а5, а6, а7, а8), где аi – номер вертикали, на которой стоит ферзь, находящийся в i-й горизонтали, т.е. А1 =А2 =А3=А4 =А5 =А6 =А7 =А8 ={1,2,3,4,5,6,7,8} . Каждое частичное решение – это расстановка N ферзей (где 1N8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества Sk .

Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k1 вершины k-го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а1, а2,… , аk-1, аk), где  (а1, а2,… , аk-1)  – это то частичное решение, которое соответствует вершине p, а аk  Sk; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов аk в Sk .

Обходы ордерева в глубину и в ширину

Во многих задачах необходимо обойти некоторое ордерево в глубину или в ширину, посещая каждую его вершину в точности один раз и выполняя при этом некоторую систематическую обработку информации, относящейся к этой вершине. Посещение каждой вершины дерева может быть связано или с выполнением простой операции, например с распечаткой пометки вершины дерева, или со сложной, например, с вычислением некоторой функции.

Рис. 20. Дерево

При префиксном обходе ордерева T, сначала нужно посетить его корень v, а затем, если v не является листом, то реализовать префиксный обход всех ее поддеревьев в порядке их упорядоченности. Например, для дерева, показанного на рис. 20, вершины будут проходиться в следующем порядке: A,B,C,D,E,F,G,H,I,J,K,L. Следующая рекурсивная процедура реализует префиксный обход ордерева:

procedure ПРЕФИКСНЫЙ-ОБХОД(T: ордерево); 
begin 
    Посетить корень 
v ордерева T
    if v не лист then 
        Пусть 
T1,…,Tk – поддеревья корня v; 
        for i := 1 to k do ПРЕФИКСНЫЙ-ОБХОД(Ti) end 
    end 
end.

Если использовать стек S для хранения текущего пути по дереву, т.е. пути, который начинается в корне дерева и кончается в вершине, посещаемой в данный момент, то можно предложить следующий нерекурсивный алгоритм префиксного обхода ордерева:

Посетить корень дерева и поместить его в пустой стек  S ; 
while стек  S  не является пустым do 
    Пусть 
p  – вершина, находящаяся на верху стека  S ; 
    if Сыновья вершины p еще не посещались 
    then Посетить старшего сына вершины p и поместить его в стек  S  
    else 
           Удалить вершину p из стека S; 
            if p имеет братьев then Посетить брата вершины p и поместить его в стек  S  end 
    end 
end

Способ обхода ордерева в ширину предполагает посещение вершин ордерева по старшинству, уровень за уровнем, отправляясь от корня. Например, при обходе в ширину изображенного на рис. 20 дерева вершины проходятся сверху вниз и слева направо и посещаются в следующем порядке: A,B,C,G,H,D,E,F,I,L,J,K. Приведенный ниже алгоритм реализует обход дерева в ширину, используя очередь О.

Поместить корень в пустую очередь O
while очередь O не пуста do 
        Пусть p  – первая вершина очереди O
        Посетить вершину 
p  и удалить ее из O
        Поместить всех сыновей вершины 
p  в очередь O, начиная со старшего сына 
end 
 

Следует заметить, что обход дерева поиска в ширину позволяет обходить дерево поиска одновременно с его построением. Таким образом, можно решать задачу нахождения какого-нибудь одного решения в форме вектора 1, а2,…)  неизвестной длины (не зная r), если только известно, что существует конечное решение задачи.

 Обходы графа в глубину и в ширину

Алгоритмы обхода дерева в глубину и в ширину можно модифицировать таким образом, чтобы их можно было использовать для систематического обхода всех вершин произвольного графа.

Например, используя рекурсивную процедуру, линейный по временной сложности алгоритм обхода графа G в глубину можно записать следующим образом:

procedure ОБХОД-В-ГЛУБИНУ(р: вершина); 
begin 
    Посетить вершину 
р 
    for all q from множества вершин, смежных с р do 
        if q еще не посещалась then ОБХОД-В-ГЛУБИНУ(qend 
    end 
end; 
begin 
    for all р from множества вершин G do 
        if р еще не посещалась then ОБХОД-В-ГЛУБИНУ(рend 
    end 
end.

В результате работы алгоритма, пройденные ребра графа образуют вместе с посещенными вершинами одно или несколько деревьев (по одному дереву для каждой компоненты связности графа). Если приписать пройденным ребрам ориентацию в соответствии с тем направлением, в каком они проходятся при выполнении алгоритма, то мы получим совокупность ордеревьев, причем их корнями будут служить все те вершины, которые в процессе работы алгоритма помещались в пустой стек.

Например, для графа, изображенного на рис. 21,а, описанным способом будут получены два ордерева, приведенных на рис. 21,б. Порядок на всем множестве вершин графа, а также порядок вершин, смежных всякой его вершине, соответствует алфавитному порядку букв, помечающих вершины.

Нерекурсивный вариант алгоритма обхода графа G в глубину может иметь следующий вид:

procedure ОБХОД-В-ГЛУБИНУ-1(р : вершина); 
begin 
    Посетить вершину
р  и поместить ее в пустой стек S
    while Стек S непуст do 
            Пусть р  – вершина, находящаяся на верхушке стека S
            if у р есть непосещенные смежные вершины then 
                    Пусть 
q – непосещенная вершина, смежная вершине р
                    Пройти по ребру (
р, q), посетить вершину q и поместить ее в стек S 
            else Удалить вершину р из стека
            end 
    end 
end;

Рис. 21. Граф и его обход в глубину

Обход в ширину связного графа предполагает рассмотрение всех его вершин в порядке возрастания расстояния от некоторой вершины, с которой начался данный обход графа. Например, в результате обхода графа G (рис. 21) в ширину возможен следующий порядок посещения вершин: C,A,B,D,H,K,L,E,F,G.

 Следующий алгоритм позволяет осуществить обход в ширину любого связного графа G:  

procedure ОБХОД-В-ШИРИНУ(р: вершина); 
begin 
    Поместить вершину 
р в пустую очередь O
    while очередь O не пуста do 
            Взять первую вершину 
р из очереди O
            if р еще не посещалась then 
                    Посетить вершину 
р и поместить в очередь все вершины, смежные с р 
            end 
    end 
end;

Контрольные вопросы

  1.  Дать описание алгоритму поиска с возвращением. В чем заключается суть алгоритма с возвращением?
  2.  Дать описание алгоритма обхода ордерева в глубину и ширину. В чем заключается суть алгоритма?
  3.  Дать описание алгоритма обхода графа в глубину и ширину. В чем заключается суть алгоритма?


 

А также другие работы, которые могут Вас заинтересовать

80552. Фінансова санація підрприємства 97.5 KB
  Неплатоспроможність у свою чергу є підставою для оголошення підприємства банкрутом. Водночас банкрутство підприємства та його ліквідація означають не тільки збитки для акціонерів кредиторів виробничих партнерів споживачів продукції а й зменшення податкових надходжень у бюджет а також збільшення безробіття що теж може стати одним із факторів макроекономічної нестабільності. За умови проведення санації оздоровлення чи реструктуризації такі підприємства можуть розрахуватися з боргами і продовжити діяльність. Під фінансовою кризою...
80553. Планування санації 102.5 KB
  Оцінка санаційної спроможності підприємства. Аналіз факторів і причин впливу на підприємство стану підприємства. Головним критерієм прийняття рішення щодо санації чи ліквідації підприємства є його санаційна спроможність. Санаційна спроможність це наявність у підприємства що зазнало фінансової кризи фінансових організаційнотехнічних та правових можливостей які забезпечуватимуть успішне проведення його фінансової санації.
80554. Джерела санації підрприємств 95 KB
  У цьому випадку мова іде насамперед про зменшення статутного фонду за рахунок зменшення номінальної вартості акцій та зменшення їх кількості з метою: одержання санаційного прибутку з наступним спрямуванням його на покриття балансових збитків; приведення у відповідність розміру основних та оборотних засобів підприємства з розміром його власного капіталу та ін. Санаційний прибуток це прибуток який виникає внаслідок викупу підприємством власних корпоративних прав акцій паїв за курсом нижчим від номінальної вартості цих...
80555. Реорганізація і банкрутство підприємства 157.5 KB
  Тема: Реорганізація і банкрутство підприємства. Зовнішнім показником банкрутства неспроможності підприємства є припинення його поточних платежів і нездатність забезпечити виконання вимог кредиторів якщо вони сукупно складають не менше 300 мінімальних розмірів заробітної плати і не були задоволені боржником протягом як правило трьох місяців з дня настання строків їх виконання. До зовнішніх можна віднести: скорочення попиту на продукцію підприємства і спад цін на неї; зростання цін на сировину матеріали й енер горесурси; економічна...
80556. Особливості організації фінансів на підприємствах різних форм господарювання. Фінансовий механізм 142 KB
  Корпоративними є підприємства створені у формі господарських товариств: повного товариства товариства з обмеженою відповідальністю товариства з додатковою відповідальністю командитного товариства акціонерного товариства тощо. Підприємство колективної власності корпоративне або унітарне підприємство що діє на основі колективної власності засновників зокрема господарські товариства це підприємства...
80557. Доходність і прибутковість підприємств 231 KB
  Для кожного підприємства важливо знати його фінансовий стан у плановому періоді згідно з передбачуваними витратами і конюнктурою ринку на ті види продукції які воно виробляє і реалізує. Насамперед менеджерам підприємства треба знати при якому обсязі реалізації того чи іншого виду продукції обсяг продажу досягається беззбитковість виробництва нульова рентабельність. Менеджерам підприємства також важливо знати на скільки потрібно збільшити обсяг виробництва і реалізації продукції щоб одержати бажану суму прибутку і як вплине на...
80558. Непрямі податки, податки і платежі за майно і ресурси підприємств 239.5 KB
  Акцизний збір — це непрямий податок, що встановлюється на підакцизні товари та включається в їхню ціну. Акцизний збір (далі – АЗ) – специфічний акциз, що застосовується для обмеженої кількості товарів, які називаються підакцизними.
80559. Місцеві податки і збори. Спрощена система оподаткування 160 KB
  Особливості їх стягнення і впливу на фінансовогосподарську діяльність субєктів господарювання полягають у такому: Місцеві податки і збори включають до складу валових витрат що вираховуються зі скоригованого валового доходу а отже зменшують суму оподатковуваного прибутку. Місцеві податки і збори субєкти господарювання відносятьна собівартість продукції робіт послуг що впливає на формування бухгалтерського прибутку. Платниками цього податку є субєкти підприємницької діяльності їхні філії відділення представництва постійні...
80560. Визначення потреби в оборотних коштах 42.5 KB
  Нормування незавершеного виробництва і готової продукції. Аналогічно нормується запас палива за видами на виробничі і невиробничі цілі норматив на тару з урахуванням часу виготовлення або транспортування прошивки та інших стадій підготовки до запакування продукції. Усі витрати на початі але незавершені вироби у цехах майстернях інших виробничих приміщеннях після видачі зі складу матеріалів до моменту передачі продукції на склад визначаються вартістю незавершеного виробництва. Нароматив незавершеного виробинцтва залежить від: обсягу і...