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


 

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

85373. Вади мовлення та причини її порушення. Будова мовного апарату 49.5 KB
  Необхідно враховувати що 3 останніх дефекту часто є лише сприяючим моментом до появи дефектів звуковимови так як у фізично і психічно здорової дитини при правильному мовному вихованні в більшості випадків знаходяться природні шляхи компенсації такого дефекту. У доопераційний період у дитини готують до операції мязи і тканини виробляють навик направляти повітряний струмінь через рот викликають можливі звуки; в післяопераційний період йде постановка звуків. Зустрічаються і більш складні мовні порушення в яких недоліки звуковимови є лише...
85374. Психокорекційна та профілактична робота з дітьми, які мають мовні порушення 34.15 KB
  У дітей з мовними порушеннями в порівнянні з віковою нормою спостерігається зниження пізнавальної діяльності та входять до її структури процесів: менший обсяг запамятовування і відтворення матеріалу нестійкість уваги швидка відволікання виснаженість психічних процесів зниження рівня узагальнення і осмислення дійсності; у них утруднена розгорнута звязна мова.
85375. Профілактика порушень слуху 39.23 KB
  Групи ризику дітей першого року життя по приглухуватості і глухоті: діти що народилися від багатоплідної вагітності; діти з масою тіла менше 15 кг; діти матері яких перенесли під час вагітності краснуху герпетичну інфекцію цитометоловірусну інфекцію; діти матері яких приймали під час вагітності ототоксичні препарати; діти що отримували в період новонародженості за вітальними свідченнями антибіотики ряду аміноглікозидів; діти слабочуючих або глухих батьків; діти з родовими травмами і внутрічерепним крововиливом. Ці діти...
85376. Предмет, завдання і методи логопедії та логопсихології 38.25 KB
  Найточнішим на сьогодні вважається таке визначення цієї науки: логопсихологія це галузь спеціальної психології в якій вивчається своєрідність психічного розвитку осіб з вадами мовлення первинного походження а також розробляються принципи і методи психокорекційної роботи з ними. Основною метою спеціального психологічного супроводу в системі освіти осіб з порушеннями мовлення є виявлення усунення і попередження дисбалансу між процесами навчання і розвитку цієї категорії та їх потенційними можливостями. З огляду на визначення логопсихології...
85377. Розвиток психіки глухої дитини. Розвиток словесно-логічного мислення і словесна пам’ять глухих дітей 38.39 KB
  Для першої I III класи характерний поширюється тип запамятовування тобто приріст відтвореного матеріалу від повторення до повторення. Для другої стадії IVVI класи характерний охоплює тип запамятовування при якому дитина розуміє і запамятовує загальний зміст тексту і ключові його слова а в подальшому поповнює його відсутніми елементами. Для третьої стадії розвитку словесної памяті VIIVIII класи характерно повне розуміння і запамятовування тексту. Часто спостерігається сплав осмисленого і механічного запамятовування: те що...
85378. Мониторинг воздействия на окружающую среду 67 KB
  Мониторинг воздействия на окружающую среду. Методы мониторинга воздействия на окружающую среду. Мониторинг воздействия на окружающую среду часть экологического мониторинга многоцелевая информационная система в задачи которой входит описание наблюдение оценка и прогноз источников воздействия на окружающую среду и отходов сбросы выбросы размещение и удаление отходов использование ресурсов и готовой продукции. Источник воздействия на окружающую среду ограниченная в пространстве область к которой могут быть отнесены все...
85379. Нормирование и лимитирование воздействия на окружающую среду 46.5 KB
  Нормативы воздействия на окружающую среду предельные характеристики источников воздействия на окружающую среду и условия размещения и удаления отходов соблюдение которых в любом случае не может привести к нарушению установленных критериев качества окружающей среды. Лимитирование воздействия на окружающую среду временное установление определенных характеристик источников воздействия на окружающую среду и отходов для соблюдения и контроля которых имеются необходимые возможности и средства. Лимиты воздействия на окружающую среду ...
85380. Распространение загрязняющих веществ 64 KB
  Если выбрасываемые в воздух примеси состоят из крупных частиц то распространяясь в атмосфере они под действием силы тяжести начинают спускаться с определенной постоянной скоростью в соответствии с законом Стокса. Естественно что почти все примеси в конечном итоге осаждаются на поверхности земли причем тяжелые осаждаются в основном под действием гравитационного поля а легкие в результате диффузионного процесса. Поскольку наиболее опасны для окружающей среды примеси газообразного вида типа окислов то именно таким легким соединениям...
85381. Нормирование качества воздуха, воды, почвы 67.5 KB
  Совершенно недопустимо сравнивать уровни загрязнения селитебной зоны с установленными ПДКрз а также говорить о ПДК в воздухе вообще не уточняя о каком нормативе идет речь. Уровень загрязнения атмосферы обычно описывается набором статических характеристик для ряда измеряемых вредных веществ. Для оценки степени загрязнения атмосферы средние максимальные концентрации веществ нормируются на величину средней максимальной концентрации для большого региона или на санитарногигиснический норматив ПДК. Нормированные характеристики загрязнения...