Главная Промышленная автоматика.

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

"Жадный" алгоритм для задачи коммивояжера, речь о котором пойдет ниже, является вариантом алгоритма Крускала. Здесь, как и в основном алгоритме Крускала, сначала рассматриваются самые короткие ребра. В алгоритме Крускала очередное ребро принимается в том случае, если оно не образует цикл с уже принятыми ребрами; в противном случае ребро отвергается. В случае задачи коммивояжера "критерием принятия" ребра является то, что рассматриваемое ребро (в сочетании с уже принятыми ребрами)

• не приводит к появлению вершины со степенью три и более;

• не образует цикл (за исключением случая, когда количество выбранных ребер равняется количеству вершин в рассматриваемой задаче).

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

На рис. 10.11,а сначала выбирается ребро (d, е), поскольку оно является кратчайшим, имея длину 3. Затем рассматриваются ребра (Ь, с), (а, Ь) и (е, /) - длина всех этих ребер равна 5. В каком порядке они будут рассмотрены, значения не имеет - все они удовлетворяют условиям для выбора, и мы должны выбрать их, если собираемся строго следовать "жадному методу". Следующим кратчайшим ребром является ребро (а, с), длина которого равна 7.08. Однако это ребро может образовать цикл с ребрами (а, Ь) и (6, с), поэтому принимаем решение отвергнуть его. Затем по той же причине отвергаем ребро (d, f). Далее надо рассмотреть ребро (Ь, е), но его также придется отвергнуть, поскольку оно повышает степени вершин Ь и е до трех и не образует маршрут с теми ребрами, которые уже отобраны. Точно так же отвергается ребро (Ь, d). Затем рассматриваем ребро (с, а) и принимаем его. Итак, уже образовался путь а->b->c->d->e->/, и, завершая маршрут, выбираем ребро (a,f). В результате получаем маршрут, показанный на рис. 10.11,6. Он по своей "оптимальности" находится на четвертом месте среди всех возможных маршрутов; его стоимость всего лишь на 4% больше стоимости оптимального маршрута.

10.4. Поиск с возвратом

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

Рассмотрим какую-либо игру с участием двух игроков, например шахматы, шашки или "крестики-нолики". Игроки попеременно делают ходы, и состояние игры отражается соответствующим положением на доске. Допустим, что есть конечное число позиций на доске и в игре предусмотрено определенное "правило остановки", являющееся критерием ее завершения. С каждой такой игрой можно ассоциировать дерево, называемое деревом

Степенью вершины назьшается количество ребер, инцидентньг>£ этой вершине. - Прим. ред. 10.4. ПОИСК С ВОЗВРАТОМ 291



игры. Каждый узел такого дерева представляет определенную позицию на доске. Начальная позиция соответствует корню дерева. Если позиция х ассоциируется с узлом п, тогда потомки узла я соответствуют совокупности допустимых ходов из позиции X, ш с каждым потомком ассоциируется соответствующая результирующая позиция на доске. Например, на рис. 10.12 показана часть дерева для игры в "крестики-нолики".

Ход игрока X

Ход игрока X

Ход игрока О

Ход игрока X


Рис. 10.12. Часть дерева игры в "крестики-нолики"

Листья этого дерева соответствуют таким позициям на доске, из которых невозможно сделать ход, - то ли потому, что кто-то из игроков уже одержал победу, то ли потому, что все клетки заполнены и игра закончилась вничью. Каждому узлу дерева соответствует определенная цена. Сначала назначается цены листьям. Допустим, речь идет об игре в "крестики-нолики". В таком случае листу назначается цена -1, О или 1 в зависимости от того, соответствует ли данной позиции проигрыщ, ничья или выиг-рыщ игрока 1 (который ставит "крестики").

Эти цены распространяются вверх по дереву в соответствии со следующим правилом. Если какой-либо узел соответствует такой позиции, из которой должен сделать ход игрок 1, тогда соответствующая цена является максимальной среди цен потомков данного узла. Нри этом предполагаем, что игрок 1 сделает самый выгодный для себя ход, т.е. такой, который принесет ему самый ценный результат. Если же узел соответствует ходу игрока 2, тогда соответствующая цена является минимальной среди цен потомков данного узла. Нри этом мы предполагаем, что игрок 2 также сделает самый выгодный для себя ход, т.е. такой, который при самом благоприятном исходе приведет к проигрыщу игрока 1, а при менее предпочтительном исходе - к ничьей.

Пример 10.6. На рис. 10.12 показаны цены позиций в игре "крестики-нолики". Листьям, которые приносят выигрыщ для игрока О (который рисует "нолики"), назначается цена -1; листьям, которые приносят ничью, назначается цена О; а листь-



ям, которые приносят выигрыш для игрока X (который рисует "крестики"), назначается цена -1-1. Затем продвигаемся вверх по дереву. На уровне 8, где остается только одна пустая клетка, и предстоит ход игроку X, ценой для неразрешенных позиций является "максимум" из одного потомка на уровне 9.

На уровне 7, где предстоит ход игроку О, и имеются два варианта решения, в качестве цены для внутреннего узла принимаем минимальную из цен его потомков. Крайняя слева позиция на уровне 7 представляет собой лист и имеет цену 1, поскольку она является выигрышем для X. Вторая позиция на уровне 7 имеет цену mm(0, -1) = -1, тогда как третья имеет цену mm(0, 1) = 0. Одна позиция, показанная на уровне 6 (на этом уровне предстоит ход игроку X), имеет цену тах(1, -1, 0) = 1. Это означает, что для обеспечения выигрыша игроку X нужно сделать определенный выбор и в этом случае выигрыш последует немедленно. □

Обратите внимание: если цена корня равняется 1, то выигрышная стратегия находится в руках игрока 1. Действительно, когда наступает его очередь ходить, он гарантирован, что может выбрать ход, который приведет к позиции, имеющей цену 1. Когда же наступает очередь игрока 2 делать свой ход, ему не остается ничего иного, как выбрать ход, ведущий к все той же позиции с ценой 1, что для него означает проигрыш. Тот факт, что игра считается завершившейся, гарантирует в конечном счете победу первого игрока. Если же цена корня равняется О, как в случае игры в "крестики-нолики", тогда ни один из игроков не располагает выигрышной стратегией и может гарантировать себе лишь ничью, если будет играть без ошибок. Если же цена корня равняется -1, то выигрышная стратегия находится в руках игрока 2.

Функции выигрыша

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

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

Ниже перечислен ряд других правил, в соответствии с которыми действуют хорошие шахматные программы:

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

2. Распространение "цепочек взятия", которые представляют собой последовательности ходов, сопрово>1<дающиеся взятием фигур противника, за пределы последнего уровня, до которого обычно распространяется дерево. Это помогает более точно оценить относительную материальную силу позиций.

3. Сокращение поиска на дереве методом альфа-бета отсечения (см. дальше в этом разделе). 10.4. ПОИСК С ВОЗВРАТОМ 293





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002