3. Методы эвристического поиска

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

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

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

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

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

Алгоритм подъема на холм:

1. создать одноэлементную очередь, включающую путь нулевой длины.

2. пока головной путь в очереди не оканчивается целью и пока очередь не пуста повторять:

• удалить головной путь из очереди

• создать новые пути, расширяя его

• удалить из новых путей все циклические

• отсортировать новые пути по эвристике, частичный путь с мин расстоянием до цели должен оказаться в голове очереди

• добавить новые пути в голову очереди

3. если полный путь найден, показать его, иначе сообщить о неудаче.

Проблемы метода

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

Локальные максимумы. Выбираем направление из т. А на север, обеспечивающее макс набор высоты, и приходим в т. В, являющуюся локальным максимумом.

Платформы. Не можем выбрать направление из т. А, так как все направления дают одинаковый прирост высоты.

Острые лезвия. Сколько бы ни выбирали направлений, это не гарантирует выбора верного направления.

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

Метод «Первый - лучший». Если в процессе поиска дальнейшее продвижение невозможно, то откат производится не на предыдущий уровень, как при подъеме на холм, а в узел, имеющий лучшую эвристическую оценку.