Intel_Nils, страница 11

Простой алгоритм полнота перебора на дереве состоит из следующей последовательности шагов: (!) Поместить начальную вершину в список, называемый ОТКРЫТ. (2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу. Гл. 3. Методы поиска в пространстве состояний (3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список ЗАКРЫТ; назовем эту вершину и.

(4) Раскрыть вершину п, образовав все вершины, непосредственно следующие за п.,Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за п вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине и. Р и с ЗЛ. Блок-схема программы алгоритма полного перебора для деревьев.

(5) Если какие-нибудь из этих непосредственно следующих за и вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2). д.е. Методы полного перебора В этом алгоритме предполагается, что начальная вершина не удовлетворяет поставленной цели, .хотя нетрудно ввести этап проверки такой возможности. Блок-схема алгоритма показана на рис. 3.1. Вершины и указатели, построенные в процессе перебора, образуют поддерево всего неявно определенного дерева пространства состояний. Мы будем называть такое поддерево деревом перебора.

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

Эти вершины занумерованы в том порядке, в котором они получались при раскрытии '); зачерненная ветвь представляет собой решение из пяти шагов. (Стрелки на дугах не указаны, поскольку в данном случае совершенно ясно происхождение каждой вершины.) Заметьте, что было раскрыто 26 и построено 46 вершин, прежде чем удалось найти это решение. Непосредственное рассмотрение этого графа показывает также, что не существует решения, содержащего меньшее число шагов. Могут встретиться задачи, в которых к решению предъявляются какие-то иные требования, отличные от требования получения наикратчайшей последовательности операторов. Присваивание дугам дерева определенных цен (с последующим нахождением решающего пути, имеющего минимальную '1 Порядок последующих вершин соответствует перемещению пустой клетки сначала влево, затем вверх, вправо и вниз.

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

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

В методе равных цен вершины раскрываются в порядке возрастания стоимости я(п). Этот метод характеризуется такой последовательностью шагов: (!) Поместить начальную вершину з в список, называемый ОТКРЫТ. Положить ф(з) = О. (2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска; в противном случае переходить к следующемуу ш а гу.

(3) Взять из списка ОТКРЫТ ту вершину, для которой величина ф имеет наименьшее значение, и поместить ее в список, называемый ЗАКРЫТ. Дать этой вершине название п. (В случае совпадения значений выбирать вершину' с минимальным й произвольно, ио всегда отдавая предпочтение целевой вершине.) (4) Если и есть целевая вершина, то иа выход выдать решающий путь, получаемый путем просмотра назад в соответствии с указателями; в противном случае переходить к следующему шагу. (5) Раскрыть вершину п, построив все непосредственно следующие за ней вершины.

(Если таковых не оказалось, то переходить сразу к шагу (2).1 Для каждой из такой непосредственно следующей (дочерней) вершины и; вычислить стоимость йт(и;), положив 3(иг) = ~(п) + с(п,п;). Поместить эти вершины вместе с соответствующими им только что найденными значениями к в список ОТКРЫТ и построить указатели, идущие назад к п. (б) Перейти к шагу (2). Блои-схема этого алгоритма показана на рис.

3.3. Заметьте, что проверка того, является лн некоторая вершина целевой, Гл. 8, Методы поиска в пространстве состояний Р и с. З.Х Блок-схема программы алгоритма равных пеи лля деревьев. включена в эту схему так, что' гарантируется обнаружение путей минимальной стоимости. Мы видим, что алгоритм, работающий по методу равных цен, может быть также использован для поиска путей минимальной длины, если просто положить стоимость каждого ребра равной единице. Если имеется несколько начальных вершин, то алгоритм просто модифицируется: на шаге (1) все начальные вершины помещаются в список ОТКРЫТ.

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

З.З. МЕТОД ПЕРЕБОРА В ГЛУБИНУ В методах перебора в глубину прежде всего раскрываются те вершины, которые были построены последними. Определим глубину вершины в дереве следующим образом: Глубина корня дерева равна нулю. Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует. Таким образом, вершиной, имеющей наибольшую глубину в дереве перебора, в данный момент служит та, которая должна в этот момент быть раскрыта.

Такой подход может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения. После того как в ходе процесса строится вершина с глубиной, превышающей некоторую граничную глубину, мы раскрываем вершину наибольшей глубины, не превышающей этой границы, и т. д. Метод перебора в глубину определяется следующей последовательностью шагов: (1) Поместить начальную вершину в список, называемый ОТКРЫТ. (2) Если список ОТКРЫТ пуст, то иа выход дается сигнал о неудаче поиска, в противном случае перейти к шагу (3). (3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список, называемый ЗАКРЪ|Т. Эту вершину назвать'л.

(4) Если глубина вершины и равна граничной глубине, то переходить к (2), в противном случае — к (5). (5) Раскрыть вершину и, построив все непосредственно следующие за ней вершины. Поместить их (в произвольном порядке) в начало списка ОТКРЫТ и построить указатели, идущие от них к вершине и. (6) Если одна из этих вершин целевая, то на выход выдать решение, просматривая для этого соответствующие указатели, в противном случае переходить к шагу (2). На рис. 3.4 приведена блок-схема для метода перебора в глубину. Дерево, которое получается в результате применения метода перебора в глубину к той же самой игре в восемь, что и прежде, показано на рис.

3.5. Снова нужно найти енрго целеаыми р Р н с. 3.4. Блок-схема программы алгорнтма поиска в глуониу для дереве Гя. д Метода аоиска в аростраистве состояний последовательность ходов для преобразования левой конфигурации в правую: Вершины здесь занумерованы в том порядке, в котором они были раскрыты, причем граничная глубина выбрана равной 5 (т. е. ищутся пути, ведушне к цели, длина которых не больше пяти). Мы видим, что в алгоритме поиска в глубину сначала идет перебор вдоль одного пути, пока не будет достигнута максимальная глубина, затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются от него лишь последним шагом, после чего рассматриваются пути, отличающиеся последними двумя шагами, и т.

д. 34. ИЗМЕНЕНИЯ ПРИ ПЕРЕБОРЕ НА ПРОИЗВОЛЬНЫХ ГРАФАХ При переборе на графах, а не на деревьях, нужно внести некоторые естественные изменения в указанные алгоритмы. В простом методе полного перебора не нужно вносить никаких изменений; следует лишь проверять, не находится ли уже вновь построенная вершина в списках ОТКРЫТ или ЗАКРЫТ по той причине, что она уже строилась раньше в результате раскрытия какой-то вершины. Если это так, то ее не нужно вновь помещать в список ОТКРЫТ. Несколько более сложные изменения должны быть сделаны в алгоритме равных цен; (!) Если вновь построенная вершина уже имеется в списке ОТКРЫТ, то ее не следует вносить в этот список снова.