78192

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

Лекция

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

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

Русский

2015-02-07

87.5 KB

7 чел.

екция: Алгоритмы поиска с возвращением                                                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.  Дать описание алгоритма обхода графа в глубину и ширину. В чем заключается суть алгоритма?


 

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

78786. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ВОСПРИЯТИЯ БАЗИСНЫХ ЧАСТЕЙ РЕЧИ В ТЕКСТЕ: ПОЗИЦИОННЫЙ АСПЕКТ 3.64 MB
  Данная диссертационная работа посвящена экспериментальному исследованию восприятия базисных частей речи в позиционной структуре текста и выполнена в русле общей теории текста с учетом знаний, накопленных в области теории языка, психолингвистики и лингвосинергетики.
78787. Формирование траектории устойчивого развития региональной социально-экономической системы 861 KB
  Социально-экономическое развитие общества в XX веке, ориентированное в основном на быстрые темпы экономического роста, нанесло огромный ущерб окружающей природной среде. По существу развитие отождествлялось с экстенсивным вовлечением природных ресурсов в экономику, индустриализацией промышленности...
78788. Сім’я буде щасливої коли… 156 KB
  Завдання для груп: І група Відшукати словничок свого роду. ІІ група Що робити щоб були злагода щастя і радість Знайти відповіді з народних джерел. ІІІ група Скласти кросворд ребус про сімю родину. Самостійна пошукова робота учнів: Група 1 Віками складається й передається...
78789. Голос рідної природи серцем слухати навчись (інтегрований урок) 371.5 KB
  Мета: вдосконалювати навички виразного читання, навички чітко і повно відповідати на запитання, збагачувати словниковий запас образними висловами, розвивати усне мовлення учнів; розширювати уявлення про поняття птахи, ознайомити учнів із зимуючими птахами своєї місцевості...
78790. Скарб над скарбами. Казки народів світу. Пагінець місячного дерева (Японська народна казка) 3.93 MB
  Завдання проекту. Розширити і поглибити знання про народні казки світу. Розвивати вміння оцінювати вчинки персонажів і визначати мотиви їхньої поведінки. Учити здійснювати проектну діяльність на основі відбору інформації з довідкової літератури.
78791. Мова – дивний скарб 63.5 KB
  Мета: формування ключових компетентностей: вміння вчитися – самоорганізовуватися до навчальної діяльності у взаємодії; загальнокультурної – дотримуватися норм мовленнєвої культури, зв’язно висловлюватися в контексті змісту; соціальної – здатність працювати в групі, в парі, з усіма в колективі...
78792. Скарби бабусиної скрині 77.5 KB
  Ліна: Ну а я що можу зробити? Візьми он книжку яку почитай. Марія: Та ти що з дуба впала, яка книжка, я ж покоління ХХІ століття - часу інтернету, - ми книжок не читаємо. Ліна: Тобі ж гірше. Не хочеш читати - візьми в хаті поприбирай. Подвійна користь буде: себе займеш і бабусі допоможеш.
78793. Как нечисть Любовь украла 45 KB
  На сцене стоит избушка старушки - сказочницы. Ставни открываются - в избушке сидит старушка. Во время её слов перебежками вокруг дома бегает нечистая сила. Старушка: Это было… иль не было Иль приснилось мне опять. Раз - окошки отворила - Сказку буду начинать! Сказку эту иль неправду...
78794. Скелет и мышцы 198 KB
  Цель: Знакомить учащихся со строением человека. Формировать интерес к познанию самого себя. Проверить усвоение материала по теме «Кожа». Расширить кругозор учащихся. Оборудование: индивидуальные карточки, плакаты, справочник, пособие «Скелет человека».