5.5. Эвристический поиск

Широкий класс задач можно разрешить следующим способом:

Этап 1. Выбрать из множества возможных действий некоторое действие.

Этап 2. Осуществить выбранное действие и изменить текущую ситуацию.

Этап 3. Оценить ситуацию.

Этап 4. Отбросить бесполезные ситуации.

Этап 5. Если достигнута конечная ситуация — конец; если нет, выбрать новую исходную ситуацию и начать сначала.

До сих пор для этапов «принятия решений» (этапы 1, 3 и 5) мы использовали одну и ту же численную функцию. Теперь уточним эту схему. В табл. 5.1 перечислены общие идеи и стратегии поиска, которые используются человеком и/или существующими программами.

Таблица 5.1. (см. скан) Методы эвристического поиска

Если в соответствии с табл. 5.1 6 некоторой задаче на. обнаружение дерева с минимальным весом мы решаем на каждом шаге добавлять в. искомое дерево по одному ребру, на первом этапе выбрать ребро с минимальной стоимостью, а на пятом этапе вернуться по дереву, следуя по пути его формирования, то тогда мы имеем дело с доказанным выше алгоритмом скаля. Однако возможны и другие варианты этого алгоритма, которые, как можно доказать, также приводят к решению: в процессе построения дерева мы можем как прибавлять ребра, так и отбрасывать их; на первом этапе можно отказаться от сортировки ребер и взять первое попавшееся; на третьем этапе, если в V имеется цикл, мы исключаем из X принадлежащее этому циклу ребро, обладающее наибольшей стоимостью; на пятом этапе мы исходим из текущего дерева (X, V). Если учесть свойство связности, получим другие варианты. Даже если все эти алгоритмы сходятся, они не обязательно предполагают одно и то же число элементарных операций. Первый из них имеет сложность порядка второй (без сортировки) фактически имеет такую же сложность; лучший из известных алгоритмов обладает сложностью

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

Отметим, что в общем случае при таком типе поиска нет никакой гарантии, что на пятом этапе не возникнет снова ситуация, уже рассмотренная на одном из предыдущих шагов и данный алгоритм даст эффективное решение, если оно существует. Оба замечания учитываются в более изысканной версии общего метода градиента, разработанной Хартом, Нильсоном и Рафаэлем (1968 и 1972) и известной под названием «алгоритм А».