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


 

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

45436. Понятие ядра и процесса, состояние процесса, подпроцессы. Межпроцессное взаимодействие 175.5 KB
  Межпроцессное взаимодействие Резидентная в RM часть OS UNIX называется ядром. Все работы вне ядра оформлены в виде процессов выполнения системных и прикладных программ. Под процессом понимается единица вычислительной работы потребляющая ресурсы предоставляемые ядром для обработки системных и прикладных программ которые оформлены как командные или выполняемые файлы на внешнем устройстве.
45437. Понятия приоритета и очереди процессов. Диспетчеризация и синхронизация процессов 128.5 KB
  Диспетчеризация и синхронизация процессов. Алгоритмы планирования процессов Планирование процессов включает в себя решение следующих задач: определение момента времени для смены выполняемого процесса; выбор процесса на выполнение из очереди готовых процессов; переключение контекстов старого и нового процессов. Средства аппаратной поддержки управления памятью и многозадачной среды в микропроцессорах Intel 80386 80486 и Pentium .
45438. Программирование на Shell. Скрипты 227 KB
  Shell интерпретатор командного языка В этом разделе описаны команды и символы имеющие специальное значение которые позволяют: находить с помощью шаблона и манипулировать группами файлов; запускать команду в фоновом режиме или в определенное время; выполнять последовательно группу команд; перенаправлять стандартный ввод и вывод; завершать работающие программы. Таблица 20 Метасимволы Символ Функция [ ] Эти метасимволы позволяют указывать сокращенные имена файлов при поиске по шаблону Означает что команда будет выполняться...
45439. Управление оперативной памятью (распределение и защита) в многозадачной ОС. Механизм реализации виртуальной памяти 211 KB
  Механизм реализации виртуальной памяти. От выбранных механизмов распределения памяти между выполняющимися процессорами в значительной степени зависит эффективность использования ресурсов системы ее производительность а также возможности которыми могут пользоваться программисты при создании своих программ. С другой стороны поскольку любой процесс имеет потребности в операциях вводавывода и процессор достаточно часто переключается с одной задачи на другую желательно в оперативной памяти расположить достаточное количество активных задач с...
45440. Планирование и диспетчеризация процессов и задач 611 KB
  Долгосрочный планировщик решает какой из процессов находящихся во входной очереди в случае освобождения ресурсов памяти должен быть переведен в очередь процессов готовых к выполнению. Они определяются не только переключениями контекстов задач но и при переключении на потоки другого приложения перемещениями страниц виртуальной памяти а также необходимостью обновления данных в кэше коды и данные одной задачи находящиеся в кэше не нужны другой задаче и будут заменены что приведет к дополнительным задержкам. От выбранных механизмов...
45441. Расчет системы управления автомобилем на базе технологии CAN 277 KB
  Узлы системы Батарея BTTERY Контроллер CONT Контроллер двигателя MOTOR Дисплей панели инструментов DISP Управление водителя DRIVE Тормоза BRKES Управление коробкой передач TRNS Сеть оперирует 32 сообщениями которые делятся на различные группы: Спорадические сигналы.0 BTTERY CONT 2 Ток батареи 8 0.0 BTTERY CONT 3 Температура батареи 8 0.0 BTTERY CONT 4 Параметры батареи 10 1.
45442. Расчет системы «Интеллектуальное здание» на базе технологии EIB 315 KB
  Узлы системы Контроллер CONT Система управления светом LIGHT Система управления теплом HET Система управления вентиляцией VENT Система управления дверью DOOR Охранная система SECUR Пожарная система FIRE Сеть оперирует 30 сообщениями которые делятся на различные группы: Спорадические сигналы. Номер сигнала Описания сигнала Размер в битах Задержка в мсек J Период выполнения T мсек Тип сообщения Крайний срок выполнения Dмсек Источник Приемник 1 Сигнал датчика двери 8 01 50 S 20 DOOR CONT 2 Проверка...
45443. Расчет системы «Управление коммунальной системой (вода, газ, электрическая энергия, отключение функций, формирование квитанций и устранение аварий)» на базе технологии LonWorks 267 KB
  Узлы системы Система управления холодной водой CW Система управления горячей водой HW Система управления газом G Система управления электричеством EL Система экономических расчетов EC Ремонтная служба RS Пользователь USER Сеть оперирует 30 сообщениями которые делятся на различные группы: Спорадические сигналы. Номер сигнала Описания сигнала Размер в битах Задержка в мсек J Период выполнения T мсек Тип сообщения Крайний срок выполнения Dмсек Источник Приемник 1 Включение отключение холодной воды 1 01 50...
45444. Классификация систем реального времени. Средства разработки систем РВ. Понятие систем реального времени. Организация систем РВ. Требования к системам реального времени. Общие характеристики систем РВ 148.5 KB
  Классификация реализации систем реального времени СРВ распределенные системы управления с большим количеством контролируемых параметров. Система ориентирована на автоматизированные системы в которых требуется своевременная адекватная реакция на события. Языки СРВ предназначены для создания СРВ ssembler C d спутниковые системы наблюдения. Предназначены для визуализации работы автоматизированной системы или автоматизированного объекта.