78192

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

Лекция

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

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

Русский

2015-02-07

87.5 KB

9 чел.

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


 

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

31520. Зайнятість населення та безробіття 217.5 KB
  Зайнятість населення та безробіття Зміст учбового матеріалу: Зайнятість населення: сутність види класифікація Безробіття як складне економічне соціальне і психологічне явище Система показників оцінки ринку праці зайнятості та безробіття Регулювання зайнятості населення Програми сприяння зайнятості Зайнятість населення: сутність види класифікація Зайнятість населення являє собою діяльність частини населення щодо створення суспільного продукту національного доходу. Економічна сутність зайнятості полягає у тому що вона...
31521. Соціально-трудові відносини та соціальне партнерство 206 KB
  Соціальнотрудові відносини та соціальне партнерство Зміст учбового матеріалу: Сутність соціальнотрудових відносин та особливості формування в умовах ринкової економіки. Система соціального захисту і соціальної забезпеченості Сутність соціального партнерства 1. Сутність соціальнотрудових відносин та особливості формування в умовах ринкової економіки. Соціальнотрудові відносини це взаємозалежність і взаємодія субєктів цих відносин яка виникає в процесі праці і спрямована на регулювання умов трудового життя.
31522. Організація праці 290 KB
  Організація праці Зміст учбового матеріалу: Сутність завдання напрямки обєкти організації праці Форми організації праці Поділ та кооперація праці Організація та обслуговування робочих місць Оцінювання стану організації праці 1. Сутність завдання напрями обєкти організації праці Організація праці це система науково обґрунтованих заходів раціонального поєднання працівників із засобами виробництва з метою створення сприятливих умов праці для одержання високих кінцевих соціальноекономічних результатів. Це процес приведення...
31523. Особливості ринкової економіки та промисловий перворт на українськиї землях, які перебували у складі Російської імперії у першій половині ХІХ століття 112.5 KB
  Можна прорахувати певні наслідки впливу такої країни як Росія на соціально- економічний та політичний стан нашої держави, який ніколи не був дружелюбний і носив більш колоніальний характер.Також, на основі вивчення даної теми, можна дослідити причини прискореного розвитку ринкових відносин і промисловості
31524. Предупреждение рабства и принудительного труда в практике Европейского Суда по правам человека 308.5 KB
  Предмет исследования составляют нормы, содержащиеся в международно-правовых актах в сфере предупреждения и запрещения рабства и принудительного труда (международные конвенции, декларации и рекомендации), а также нормы российского законодательства в указанной области.
31525. Информационный сервис на примере интернет-магазина Аниме 1.65 MB
  Рассмотреть теоретические аспекты разработки и использования информационных систем. Разработать план внедрения автоматизирования бизнес процессов деятельности интернет магазина Разработать “бизнес-план” открытия интернет-магазина “Столица Аниме” Проработать методические аспекты
31526. Размножение организмов. Индивидуальное развитие организмов 709.5 KB
  Способность размножаться, т.е. производить новое поколение особей того же вида, - одна из основных особенностей живых организмов. В процессе размножения происходит передача генетического материала от родительского поколения следующему поколению, что обеспечивает воспроизведение признаков не только данного вида
31527. Разработка бизнес-плана на примере конноспортивной школы 748.5 KB
  Бизнес план - это документ, который описывает все основные аспекты коммерческого предприятия, анализирует все проблемы, с которыми оно может столкнуться, а также определяет способы решения этих проблем. Это общепринятая в мировой хозяйственной практике форма представления деловых предложений и проектов
31528. Совершенствование системы управления качеством услуг предприятия ресторанного бизнеса 316.5 KB
  Цель дипломного исследования заключается в разработке комплекса научно-методических и практических рекомендаций по совершенствованию системы управления качеством услуг предприятия ресторанного бизнеса, способствующих повышению конкурентоспособности и эффективности функционирования хозяйствующих субъектов данной сферы национальной экономики.