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

Размещено на http://www.allbest.ru/

ОГЛАВЛЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но поиска в пространстве состояний не достаточно для автоматизации интеллектуального поведения, обеспечивающего автоматическое решение проблем, хотя это важный инструмент для проектирования интеллектуальных программ. Если бы поиска в пространстве состояний было достаточно, то было бы довольно просто написать программу, играющую в шахматы. Для определения последовательности ходов, ведущих к победе, на каждом этапе игры нужно было бы осуществлять полный поиск по всему пространству состояний. Этот метод решения задач известен как исчерпывающий, или поиск методом полного перебора. Хотя полный перебор может применяться в любом пространстве состояний, огромный размер пространства для интересных задач делает этот подход практически неприемлемым. Игре в шахматы, например, соответствует приблизительно 10¹²⁰ различных состояний игровой доски. Это на порядок больше, чем число молекул во Вселенной или число наносекунд, которые минули с "большого взрыва" (момента создания Вселенной). Поиск в таком пространстве состояний выходит за рамки возможностей любого вычислительного устройства, размеры которого должны быть ограничены до известной области. Поиск обеспечивает структуру для автоматизации решения задач, но эта структура лишена интеллекта. Такой подход не дает возможности формально описать задачу. Кроме того, простой полный перебор большого пространства вообще практически неосуществим и непригоден для описания сущности разумной деятельности.

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

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

Люди используют большое количество эвристик в решении задач.

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

Пространство состояний:

- Пространство состояний используется в качестве формализованной структуры для представления проблем.

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

- Задачи оптимизации можно моделировать, назначая стоимости дугам в пространстве состояний.

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

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

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

- Поиск в ширину всегда позволяет в первую очередь найти кратчайший путь решения, но это утверждение не относится к стратегии поиска в глубину.

- Для поиска в ширину требуется больше пространства, чем для поиска в глубину. На практике пространство часто является наиболее важным и ограниченным ресурсом. *

- Метод поиска в глубину с итеративным углублением сочетает в себе наилучшие свойства поиска в глубину и в ширину.

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

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

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

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

1.3 ПОСТРОЕНИЕ ЭВРИСТИЧЕСКОЙ ОЦЕНКИ

Пусть для дуг пространства состояний определена функция с(n, n') - стоимость перехода из вершины n к вершине-преемнику n'.

Пусть f - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) "трудности" этой вершины.

Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой f принимает минимальное значение. Мы будем использовать здесь функцию f специального вида, приводящую к хорошо известному А*-алгоритму.

Функция f( n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n. Давайте предположим, что такой путь существует и что t - это целевая вершина, для которой этот путь минимален.

Тогда оценку f( n) можно представить в виде суммы из двух слагаемых:

f( n) = g( n) + h( n)

Здесь

g( n) - оценка оптимального пути из s в n, стоимость уже пройденного пути;

h( n) - оценка оптимального пути из n в t.

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

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный.

Он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. Кроме того, при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) -- это стоимость пути от начальной вершины).

В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается.

На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x).

Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

Чем меньше эвристика h(x), тем больше приоритет.

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

Пятнашки -- это головоломка, которая представляет собой набор из 15 костяшек с числами в квадратной коробке. Костяшки расположены таким образом, что одна ячейка остается пустой:

13 11 15 10 8 9 12 1 6 3 2 4 7 14 5	?	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Рисунок 2.1 - Игра «Пятнашки»

Цель игры -- упорядочить костяшки по номерам, перемещая их в коробке.

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

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

В данной работе эвристика h(t) считается как сумма расстояний от каждой фишки до ее «конечной» клетки и значения "оценки упорядоченности", умноженного на 4 (потому что поле пятнашек 4*4).

Оценка упорядоченности считается как сумма оценок фишек. Оценка фишки, за которой следует допустимый преемник, равна 0. Например, в нашем случае, если за фишкой 1 следует фишка 2, то оценка фишки 1 равна 0. Для фишки 2 допустимым приемником будет фишка 3, для 3 - 4, для 4 - 5 и т.д.

Таким образом, программа будет находить возможных дальнейших преемников вершины, упорядочивать их по f-значениям, выбирать оптимальное и раскрывать поддерево этого преемника. И так далее, возвращаясь к поиску преемников. До тех пор, пока f-значение другого поддерева не станет меньше, либо пока не будет достигнут предел, либо пока не встретится тупиковый конец, либо пока не найдется искомый лист-узел (конечное решение), которое в нашем примере представляет собой последовательность фишек от 1 до 15.

Каждый узел представляет собой комбинацию фишек на доске, которая отображается в виде упорядоченного списка, на первом месте которого отображается позиция пустой фишки, на втором - фишки 1 и т.д.

На каждом следующем шаге (создание нового узла) пустая фишка и любая другая могут меняться местами, но таким образом, чтобы расстояние между ними оставалось равным 1.



Манхэттенское расстояние -- это сумма расстояний по строкам и столбцам от текущего расположения костяшки до ее правильной позиции:

2	?	2

Рисунок 3.1 - Манхэттенское расстояние

На рисунке 3.1 манхэттенское расстояние равно 4.

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

· Факт start задает начальные позиции фишек.

· Предикат 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.

- Way -путь между начальным узлом поиска и поддеревом;

- Three 1 - поддерево Three, развернутое в пределах Tie;

- если цель найдена, то Decision - путь решения и Decided = yes

· Предикатd(Node,SonNode,Cost) определяет узел, его преемника и стоимость дуги между ними.

· Предикат exchange(Free, Counter, Counters, Countersl) меняетместамифишкуFree и фишкуCounter в спискеCounters, возвращает Countersl.

· Процедураfollow (Way, Tree, Tie, NewTree, SubtreeDecided, TreeDecided, Decision) либовставляет дерево в список деревьев Tree(предикат insert), находит лучшее f-значениев списке вновь полученного списка деревьев(thebestf) и рекурсивно вызывает expo, либопросто находит лучшее f-значениев списке деревьев Tree и рекурсивно вызывает expo, возвращает NewTree.

· Предикатinsert (Tree,Trees,NewTree)вставляетдеревоTreeв список деревьев Trees, с условием упорядоченности по f-значениям, возвращает NewTree.

· Предикат thebestf(Trees,F)возвращает лучшее f-значение в списке деревьев Trees.

· Предикат f(TorL,F) возвращает f-значение листа или дерева TorL.

· Предикат min(X,Y,Z) возвращает в Zлибо X, либо Yв зависимости от того, что меньше.

· Предикатorderlist(G,Sons, Subtrees) упорядочивает список листьев поиска поихf-значениям. Sons- листья(преемники), Subtrees - новое дерево, полученное как список упорядоченных листьев Sons. Упорядочение происходит за счет подсчета эвристической оценки с помощью предиката heuristic(N,H) и суммирования пройденного пути Gи пройденного пути до каждого листа.

· Предикат heuristic(Position,H)дает эвристическую оценку данному узлу Position (какая стоимость осталась до целевой вершины), и возвращает ее.

· Факт aim(N) задает целевую позицию.

· Предикатsumdist(Coun,Goal,Summd) подсчитывает суммарное расстояние Summd клеток позиции Counдо конечных клеток позиции Goal.

· Предикатorderliness(CounterPositions, Mark) возвращаетоценкуупорядоченностиMark, исходя из позиций клеток CounterPositions.

· Факт mark(N,P,M) дает оценкуM фишке N, которая стоит рядом с фишкой P.

· Предикатmanhattandist(X/Y,Xl/Yl,Md) подсчитывает Манхэттенское расстояние Md между двумя клетками X/Y,Xl/Yl.

· Предикат seepos(N)показывает позицию Nна доске.

· Предикат seedecision(Dec) показывает путь решения как список позиций на доске.

стратегия поиск пространство пятнашки

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

%d(Node,SonNode,Cost)

d([Free|Counters],[ Counter|Countersl],1):- %Вседугистоят 1

exchange(Free, Counter, Counters, Countersl). %Передвинуть

% фишку Counter на пустое место Freeв вписке Counters

exchange(Free, Counter,[ Counter| Subtrees],[ Free | Subtrees]):- manhattandist(Free, Counter,1).

%Если они рядом(манхэттенскоерасстояние = 1)

exchange(Free, Counter,[ Cn | Subtrees],[ Cn | Subtreesl]):-

exchange(Free, Counter, Subtrees, Subtreesl).

manhattandist(X/Y,Xl/Yl,Md):-

dif(X,Xl, Mdx),

dif(Y,Yl, Mdy),

Md is Mdx + Mdy.

dif(A,B, Md):- % Mdравно |A-B|

Md is A-B, Md>=0,!

;

Md is B-A.

heuristic([_|Counters],H):-

aim([_|GoalCells]),

sumdist(Counters,GoalCells, Md),

%Md- сумма расстояний от каждой фишки до ее "конечной" клетки

orderliness(Counters,S), % оценкаупорядоченности

H is Md + 4*S.

sumdist([],[],0).

sumdist([Counter|Counters],[Cell| Cells], Md):-

manhattandist(Counter, Cell, Md1),

sumdist(Counters, Cells, Md2),

Md is Md1 + Md2.

%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):-!. %Оценка пустой фишки равна 1

mark(1/4,2/4,0):-!. %Описание оценок фишек с допустимыми преемниками

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). %Если преемник недопустим

aim([4/1,1/4,2/4,3/4,4/4,1/3,2/3,3/3,4/3,1/2,2/2,3/2,4/2,1/1,2/1,3/1]).

%Показать список позиций на доске, которые встречались на пути к цели

seedecision([]).

seedecision([W |L]):-

seedecision(L),

nl,nl, write('___***___***___'),

nl,nl,

seepos(W).%Показатьпозициюнадоске

seepos([S0,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14,S15]):-

member(Y,[4,3,2,1]), %Последовательностькоординат Y

nl, member(X,[1,2,3,4]) , %Последовательность координат X

member(Counter-X/Y, %Фишкавклетке X/Y

[' '-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8,9-S9,10-S10,11-S11,12-S12,13-S13,14-S14,15-S15]),

write(Counter),

fail %Выполнить перебор с возвратом к следующей клетке

;

true. %Все клетки выведены

solve(Start, Decision):-

expo([],l(Start,0/0),15000,_,yes, Decision).

% 15000 - ограничение для f-значений

%expo(Way,Tree, Tie,Tree1, Decided, Decision):

% Way -путь от начального узла поиска до поддерева

%Three 1 - дерево Three, развернутое в пределах ограничения;

%если цель найдена, то Decision - путь решения и Decided = yes

%1 Лист-узел и есть цель

expo(W,l(N,_),_,_,yes,[N| W]):-

aim(N).

%2. Лист-узел не цель, но f-значение меньше чем ограничение

%Сформулировать узлы-преемники и развернуть их

%впределах Tie

expo(W,l(N,F/G), Tie,Treel, Decided,Dec) :-

F=< Tie,

(bagof(M/C,( d(N,M,C),not(member(M, W))), Sons),

!, %Sons - узлы преемникиС

orderlist(G,Sons,Subtrees), %упорядочитьподдеревья Subtrees

thebestf(Subtrees,Fl), %найти лучшее f-значение, выбрать преемника

expo(W,t(N,Fl/G, Subtrees), Tie,Treel, Decided, Dec)

;

Decided=never). %Узел N не имеет преемников

%3. Рассматриваемый узел Nне имеет преемников, f-значение меньше чем Tie.

% Развернуть наиболее перспективное дерево.

% Процедура follow примет решение,как дальше действовать

expo(W,t(N,F/G,[T| Subtrees]), Tie,Treel, Decided, Dec):-

F=< Tie,

thebestf(Subtrees,BF),

min(Tie,BF, Tiel),

expo([N| W],T, Tiel,Cn, Decidedl, Dec),

follow(W,t(N,F/G,[Cn| Subtrees]),

Tie,Treel, Decidedl, Decided, Dec).

% 4. Не лист-узел с пустыми поддеревьями. Решение не может быть найдено

expo(_,t(_,_,[]),_,_,never,_):-!.

%5. Получено f-значение больше, чем Tie. Дерево больше не может расти

expo(_,Tree, Tie,Tree,no,_):-

f(Tree,F),F> Tie.

% follow (Way, Tree, Tie, NewTree,SubtreeDecided,TreeDecided,Decision)

follow(_,_,_,_,yes,yes,_).

follow(W,t(N,_/G,[ Cn | Subtrees]), Tie, Treel,no, Decided, Dec):-

insert(Cn, Subtrees,NSubtrees),

thebestf(NSubtrees,Fl),

expo(W,t(N,Fl/G,NSubtrees),Tie,Treel, Decided, Dec).

follow(W,t(N,_/G,[_| Subtrees]), Tie,Treel,never, Decided, Dec):-

thebestf(Subtrees,Fl),

expo(W,t(N,Fl/G, Subtrees), Tie,Treel, Decided, Dec).

%упорядочить список листьев по F-значениям

orderlist(_,[],[]).

orderlist(Do,[N/C|NCs], Subtrees):-

G is Do + C,

heuristic(N,H),

F is G+H,

orderlist(Do,NCs, Subtreesl),

insert(l(N,F/G), Subtreesl, Subtrees).

%Вставить дерево в список деревьев Subtreesупорядоченно по f-значениям.

insert(T, Subtrees,[T| Subtrees]):-

f(T,F), thebestf(Subtrees,Fl),

F=<Fl,!.

insert(T,[ Cn | Subtrees],[ Cn | Subtreesl]):-

insert(T, Subtrees, Subtreesl).

%Получить f-значение

f(l(_,F/_),F).

f(t(_,F/_,_),F).

thebestf([T|_],F):- %Лучшее f-значение в списке деревьев

f(T,F).

thebestf([],15000). %Деревья отсутствуют. Неприемлемое f-значение

min(X,Y,X) :- X=<Y,!.

min(_,Y,Y).

%Начальная позиция

start([1/4,1/1,2/4,3/4,4/4,1/3,2/3,3/3,4/3,1/2,2/2,3/2,4/2,4/1,2/1,3/1]).



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

Рисунок 3.4 - Пример работы программы

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

1) Братко И. "Алгоритмы искусственного интеллекта на языке Prolog"

Размещено на Allbest.ru

...