Универсальные методы решения задач

Все реально работающие алгоритмы искусственного интеллекта основаны на переборе с возвратом, базирующемся на некотором приоритете (упорядочении) действий по «степени их пригодности» для достижения конечной цели. Алгоритм GPS (General Problem Solve) (конец 50-х гг.) – от приоритета средств к приоритету цели.

Как бы сами решали эту задачу?

Единственный ход рассуждений человека в этом случае – не прямой (от начального состояния к конечному), а обратный. Главная цель – попасть в конечное состояние «банан=у обезьяны». Как можно его достичь?

Единственное действие в нашем мире, меняющее состояние банана – схватить. Если схватить получается (функция схватить определена), то всё ОК, а если нет, то спрашиваем себя: «Почему?!».

Условием хватания является свойство:

(банан=висит) and (обезьянаXY=в середине) and (обезьянаZ=на ящике).

Цель «банан=висит» удовлетворена по условию, то есть главная цель разбивается на две конъюнктивные подцели.

Мы не можем преследовать сразу две цели, попробуем удовлетворить наиболее важную цель – встать на ящик. Какие средства приводят к этой цели?

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

Какая дополнительная информация (кроме, собственно, спецификации) неявно использовалась в наших рассуждениях? Ответ: различия в ситуации; точки – приоритет этих различий. Различие состояний определяется по координатам:

D1: положение банана;

D2: Z – положение обезьяны;

D3: XY – положение ящика;

D4: XY – положение обезьяны.

Приоритет: D1>D2>D3>D4.

procedure GPS(s:wState;{начальное состояние}цель: set of wState; var успех:boolean

{спецификация});

begin

with s do if s in цель{цель достигнута: различия между желанным и настоящим состояниями нет} then успех:=true

else

begin

{удалить все различия в порядке важности}

for D:=D₁ to D_n do

if S.D<>цель.D then {найти подходящую функцию для удаления

найденного различия}

for p:=p₁ to p_m {перебираем имена процедур (схватить и т.д.)} do

if s in Dom(p) {область определения} then GPS(s, p^-1(цель), успех);

Решение любой задачи можно свести к поиску путей в графе, либо поиску пути в лабиринте. Что помимо перебора с возвратом можно предложить в качестве универсального решателя?

1) Эвристические алгоритмы – перебор правдоподобных решений (мох на стене);

2) Вероятностный алгоритм (бросить монету);

3) Параллельные (распределённые) алгоритмы – предполагают наличие нескольких исполнителей.

Лекции читал: Бухараев Н.Р.

Набрал: Иванов Нияз (гр. 9109).

[N1]

Дата добавления: 2014-01-05