Методы комбинаторного поиска. Дерево поиска без повторения ситуаций, страница 3

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

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

Способ заключается в том, чтобы выбирать в текущей ситуации такой шаг, который приводит к новой ситуации, какой именно — неважно, и этот процесс заканчивается, когда очередная ситуация оказывается решением.

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

00 — а — 50 — б — 57 — в — 07 — е — 52 — в —

02 — е — 20 — б — 27 — е — 54 — в —

04 — е — 40 — б — 47 — е — 56.

Методы комбинаторного поиска. Задача, с которой мы познакомились, принадлежит обширному классу так называемых лабиринтных задач, процесс решения которых напоминает блуждание по лабиринту в попытках найти выход из него. Для простейших методов их решения, подобных описанным, характерно сильное ограничение информации, используемой при поиске решения, из-за чего в каждой возникающей ситуации приходится рассматривать все возможные в ней действия вместе с их последствиями, за исключением, быть может, лишь тех действий, которые приводят к уже исследованным ситуациям. Универсальность этого простого метода в сильной степени обесценивается его малой эффективностью:

метод может оказаться практически реализуемым лишь при достаточно простых исходных данных решаемой задачи.

Желая построить более эффективные методы, мы должны использовать и больший объем информации о свойствах формальной модели, в рамках которой ставится рассматриваемая задача, и в особенности о свойствах искомых решений этой задачи. Выявление характера этой информации и разработка способов ее использования должны производиться на основе содержательного исследования конкретных задач.

Излагаемые в настоящей книге методы при всем своем разнообразии обладают общей структурой, отражающей весьма общий подход к поиску решений и позволяющей присвоить этим методам обобщающее название методов комбинаторного поиска.

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