Структуры и стратегии поиска в пространстве состояний - Лабораторная работа

Игрок также рассматривает преимущества в краткосрочных стратегиях (например, взятие ферзя противника), возможности пожертвовать фигуру за позиционное преимущество или строит предположения относительно психологического состояния противника, его опыта и умения. Но поиска в пространстве состояний не достаточно для автоматизации интеллектуального поведения, обеспечивающего автоматическое решение проблем, хотя это важный инструмент для проектирования интеллектуальных программ. Если бы поиска в пространстве состояний было достаточно, то было бы довольно просто написать программу, играющую в шахматы. Поиск в таком пространстве состояний выходит за рамки возможностей любого вычислительного устройства, размеры которого должны быть ограничены до известной области. Однако в реальной жизни люди используют поиск: шахматист рассматривает ряд возможных ходов, доктор исследует несколько возможных диагнозов, ученый-программист принимает во внимание различные варианты проекта перед тем, как приступить к написанию кода.Программа поиска по заданному критерию может быть создана как усовершенствование программы поиска в ширину.Стратегия поиска в ширину предусматривает посещение в первую очередь тех узлов, которые являются ближайшими к начальному узлу.Пусть для дуг пространства состояний определена функция с(n, n") - стоимость перехода из вершины n к вершине-преемнику n". Пусть f - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) "трудности" этой вершины. Функция f( n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n.A пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдет минимальный. В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех еще не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока все дерево не будет просмотрено).В данной работе эвристика h(t) считается как сумма расстояний от каждой фишки до ее «конечной» клетки и значения "оценки упорядоченности", умноженного на 4 (потому что поле пятнашек 4*4). Оценка упорядоченности считается как сумма оценок фишек. Например, в нашем случае, если за фишкой 1 следует фишка 2, то оценка фишки 1 равна 0. Таким образом, программа будет находить возможных дальнейших преемников вершины, упорядочивать их по f-значениям, выбирать оптимальное и раскрывать поддерево этого преемника.· Предикат solve(Start, Decision) получает как входной поток начальные значения, выдает Decision - полученное решение. · Терм l( N, F/G) представляет отдельный узел дерева (лист), где N - узел в пространстве состояний, G - значение функции (стоимость пути, пройденного от начального узла до N), F - значение функции f (N) = G h(N). · Терм t( N, F/G, Subt) представляет дерево с непустыми поддеревьями, где N - корень дерева, Subt - список его поддеревьев, G - значение функции g (N), F - "обновленное" f-значение N (под этим подразумевается f-значение наиболее перспективного преемника N), список Subs упорядочен в соответствии с возрастающими f-значения ми поддеревьев. · Процедура expo (Way, Tree, Tie,Tree1,Decided, Decision) развертывает текущее дерево (поддерево), при условии, что f-значение этого дерева остается меньшим или равным значению Tie. · Процедураfollow (Way, Tree, Tie, NEWTREE, SUBTREEDECIDED, TREEDECIDED, Decision) либовставляет дерево в список деревьев Tree(предикат insert), находит лучшее f-значениев списке вновь полученного списка деревьев(thebestf) и рекурсивно вызывает expo, либопросто находит лучшее f-значениев списке деревьев Tree и рекурсивно вызывает expo, возвращает NEWTREE.Md is B-A. heuristic([_|Counters],H):-aim([_|GOALCELLS]), sumdist(Counters,GOALCELLS, Md), %Md-сумма расстояний от каждой фишки до ее "конечной" клетки orderliness(Counters,S), % оценкаупорядоченности %orderliness(COUNTERPOSITIONS, Mark) orderliness([First|OTHERCOUNTERS],S):-orderliness([First|OTHERCOUNTERS],First,S). orderliness([Counter1, Counter2|Counters],First,S):-mark(Counter1, Counter2,S1), orderliness([Counter2|Counters],First,S2), S is S1 S2. orderliness([Last],First,S):-mark(Last,First,S). mark(4/1,_,1):-!. %Описание оценок фишек с допустимыми преемниками mark(2/4,3/4,0):-!. mark(3/4,4/4,0):-!. mark(4/4,1/3,0):-!. mark(1/3,2/3,0):-!. mark(2/3,3/3,0):-!. mark(3/3,4/3,0):-!. mark(4/3,1/2,0):-!. mark(1/2,2/2,0):-!. mark(2/2,3/2,0):-!. mark(3/2,4/2,0):-!. mark(4/2,1/1,0):-!. mark(1/1,2/1,0):-!. mark(2/1,3/1,0):-!. mark(_,_,2).

ОГЛАВЛЕНИЕ

1. СТРУКТУРЫ И СТРАТЕГИИ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

1.1 ОБЩЕЕ ОПИСАНИЕ СТРАТЕГИЙ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

1.2 ПОИСК ПО ЗАДАННОМУ КРИТЕРИЮ

1.4 А* - АЛГОРИТМ

2. ИГРА «ПЯТНАШКИ»

3. ОПИСАНИЕ РЕАЛИЗАЦИИ ИГРЫ

3.1 ЭВРИСТИКИ. ОПИСАНИЕ ПРИНЦИПОВ РАБОТЫ ПРОГРАММЫ

3.2 ОПИСАНИЕ ПРЕДИКАТОВ

3.3 КОД ПРОГРАММЫ

3.4 ПРИМЕР РАБОТЫ ПРОГРАММЫ

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

1. СТРУКТУРЫ И СТРАТЕГИИ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

1.1 ОБЩЕЕ ОПИСАНИЕ СТРАТЕГИЙ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ