4. Поиск оптимального пути

Исключение избыточных путей

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

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

В алгоритм вводится правило: удаляются все пути, приводящие в одну и ту же точку кроме пути, имеющего минимальную оценку (после расширения, перед сортировкой).

Применение недооценок для увеличения эффективности поиска.

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

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

Алгоритм А*

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

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

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

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

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

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

• исключить все пути, приводящие в точку, кроме одного с минимальной оценкой

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

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

3.4 Задание на лабораторную работу

1. Постройте граф, иллюстрирующий транспортную сеть. Выберете в нем стартовую и целевую вершину.

2. Постройте поисковое дерево графа. Покажите, каким путем пойдет поск при использовании различных алгоритмов.

3. Представьте граф в виде структуры на Пролог.

4. Реализуйте процедуры поиска в ширину и поиска в глубину на Пролог.

5. Реализуйте алгоритмы эвристического поиска и поиска оптимального пути на Пролог.

4. Лабораторная работа № 4

ПРЕДСТАВЛЕНИЕ ИГРОВЫХ ДЕРЕВЬЕВ В ПРОЛОГ

Цель занятия

Ознакомиться с основными принципами теории игр и осуществления поиска в игровых деревьях на языке Пролог.

Порядок выполнения работы

1 Изучить основные понятия теории игр

2 Реализовать процедуру минимакса на языке Пролог

3 Оформить отчет

4 Ответить на контрольные вопросы

Содержание отчета

1. Иллюстрация игрового дерева

2. Представление структуры дерева на языке Пролог

3. Текст процедуры минимакса на языке Пролог

4. Вопросы системе и результаты

Контрольные вопросы

1. Основные понятия теории игр: конфликтная ситуация, игра, стратегия, ход.

2. Представление игры в матричной форме

3. Представление игры в виде дерева

4. Алгоритм процедуры минимакса

1. Основные понятия теории игр

Теория игр представляет собой активно развивающуюся математическую дисциплину, предметом исследования которой являются методы принятия решений в конфликтных ситуациях. Ситуация называется конфликтной, если в ней сталкиваются интересы двух или более сторон, преследующих различные или противоположные цели. Каждая из сторон может осуществлять какие-то мероприятия для достижения своих целей, причем успех одной стороны означает обычно неудачу другой. Первые работы по теории игр (Дж.фон Неймана и О.Моргенштерна) рассматривали конфликтные ситуации в экономике, когда при наличии свободной конкуренции борющимися сторонами выступали предприятия, торговые фирмы и т.п. Примеры конфликтных ситуаций многообразны. Они встречаются при планировании военных операций, охране объектов от нападения, выборе системы оружия, на спортивных состязаниях, выборах при наличии нескольких кандидатов, в судопроизводстве и многих других областях. В современном планировании и экономике большое значение имеют деловые игры.

Игрой называется упрощенная формализованная модель конфликтной ситуации, а конфликтующие стороны называются игроками. От реального конфликта игра отличается тем, что ведется по определенным правилам. Каждый случай разыгрывания игры от начала и до конца представляет собой партию игры. Элементами игры являются ходы, которые могут быть личными и случайными. При личном ходе игрок сознательно выбирает то или иное действие из предусмотренного правилами игры множества действий. Например, личным ходом является любой ход в шахматах, шашках. При случайном ходе выбор осуществляется посредством некоторого механизма случайного выбора (бросание монете, игральной кости и т.п.). Так называемые «чисто азартные» игры состоят только из случайных ходов. Теория игр не рассматривает такие игры. Ее цель – нахождение оптимального поведения игрока в игре, где имеются личные ходы, возможно, наряду со случайными. Такие игры называются стратегическими.

Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Эта совокупность правил должна быть «всеобъемлющей», т.е.-должна указывать как действовать в любой ситуации, которая может возникнуть в процессе игры. Если игра состоит только из личных ходов и каждый игрок выбрал свою стратегию, то исход игры определен. Однако, если в игре имеются случайные ходы, то игра будет носить вероятностный характер и выбор стратегий игроками еще не определит окончательно исход игры. Оптимальной стратегией игрока называется стратегия, которая обеспечивает ему наилучшее положение в игре, т.е. максимальный выигрыш (или минимальный проигрыш, если игра такова, что в ней игрок всегда проигрывает). При неоднократном повторении игры и наличии в ней, кроме личных, еще и случайных ходов, оптимальная стратегия обеспечивает игроку максимальный средний выигрыш.

Игра называется игрой с полной информацией, если каждый игрок при каждом личном ходе знает всю предысторию развития игры, т.е. результаты всех предыдущих личных и случайных ходов. Примерами таких игр являются шахматы, шашки и т.п. Если вся предыстория развития игры неизвестна игрокам,» то игра называется игрой с неполной информацией. К игровым моделям с неполной информацией сводится, в частности, планирование военных операций. Игра называется игрой с нулевой суммой, если суммарный выигрыш всех игроков равен нулю. Такой игрой является, например, антагонистическая игра двух сторон. Следует отметить, что наиболее исследованы в теории игр именно антагонистические игры.