Метод поиска решения на графе пространства состояний

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Комсомольский – на - Амуре государственный технический университет»

Кафедра математического обеспечения и применения ЭВМ

Расчетно-графическое задание

По курсу: «Функциональное программирование»

Студент группы 4ВС-1:                                                                                 Шелестов И.А.

Рогозин В.А.

Преподаватель:                                                                                              Абарникова Е.Б.

2007 г.

Тема:                     Метод поиска решения на графе пространства состояний.

Цель:           научиться строить граф пространства состояний, изучить методы поиска решений на графе пространства состояний.

Задание:       Используя метод поиска решений в пространстве состояний, разработать программу для автоматизации логической игры «Уголки».

Общие понятия теории графов

Граф – множество вершин вместе с множеством ребер. Каждое ребро задается парой вершин. Если ребра направлены, то называются дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать имена или метки, в зависимости от конкретного приложения.

Графы можно представлять:

1.  Каждое ребро – отдельное предложение:

link ( a, b ).

link ( b, c ).

2.  Весь граф – как один объект, состоящий из двух множеств: множество вершин и множество ребер (дуг). Каждое множество – список.

  G = graf ( [ a, b, c, d, e ], [ p( a, b ), p( b, c ),…,p( d, e ) ] ).

Для направленного графа:

  G1= graf ( [ a | _ ], [ d( a, b, 1 ), d( b, c, 4 ) …] ).

Типичные операции:

а) Найти путь между двумя заданными вершинами.

б) Найти подграф, обладающий некоторыми заданными свойствами.

Конкретная задача определяется:

а) Пространством состояний б) Стартовой вершиной в) Целевым условием – условием, к достижению которого надо стремиться. Целевые волны – волны, удовлетворяющие этим условиям.

Граф пространства состояний

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

Метод поиска решений «образовать и проверить»

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

Граф пространства состояний для игры «Уголки».

Начальное состояние

                         

 

Состояние на i-ом шаге

                                                                     

 

…

                          

                                                               

		…             …             …             …             …             …

 

					Конечное состояние
	Выигрыш двоек		Выигрыш единиц

 

Начальное состояние – два игрока (игрок 1 и игрок 2) располагаются каждый в своем углу. Затем начинается последовательное перемещение шашек. Из состояния, отображенного на i-ом шаге возможно 15 различных вариантов хода для игрока 2 (здесь показаны 6 из них).