Описать проблемную среду GPS и основные методы. Расписать один из методов подробно

Написать 4 варианта классификации алгоритмов поиска в пространстве состояний.

Дана формула, к ней нужно применить все операции обобщения (4 штуки).

XXXXXXXXXX

XX_______XX

XX_______XX

XXXXXXXXXX

XXXXXXXXXX

XX_______XX

XX_______XX

XXXXXXXXXX

XXXXXXXXXX

----------------

---------------

(Пирамида п)

(Куб к1)

(Куб к2)

(Башня б)

(Содержит б п)

(Содержит б к1)

(Содержит б к2)

(СтоитНа к1 п)

(СтоитНа к2 к1)

про основные операции обобщения см. выше

• использование эвристической информации;

• порядок раскрытия (перебора) вершин;

• полнота просмотра пространства состояний;

• направление поиска.

Что такое эвристика?

Метод, позволяющий ускорить процесс решения задачи.

Что такое оценочная функция, зачем нужна, где применяется?

Эта функция определяется на множестве вершин пространства состояний и принимает числовые значения. Значение эвристической оценочной функции Est(V) может интерпретироваться как перспективность раскрытия вершины (иногда – как вероятность ее расположения на решающем пути). Обычно считают, что меньшее значение Est(V) соответствует более перспективной вершине, и вершины раскрываются в порядке увеличения (точнее, неубывания) значения оценочной функции.

Что такое А*-алгоритмы?

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

Est(v) = g(V) + h(V),

где g(V) – стоимость пути от начальной вершины до вершины V, а h(V) – оценка оптимального пути от вершины V до целевой вершины.

Если при этом для всех вершин V пространства состояний выполняется соотношение

h(V) <= h*(V),

где h*(V) - стоимость оптимального пути из вершины V в целевую вершину, то такой алгоритм называют A*-алгоритмом.

A*-алгоритмы замечательны тем, что они допустимы.

Какие алгоритмы называются допустимыми(состоятельными)?

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

Что такое алгоритм равных цен (или Алгоритм Дейкстры)?

Это А-алгоритм с Est(V) = g(V). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V), т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.

8) Что такое GPS?

General Problem Solver - одна из наиболее известных систем искусственного интеллекта (А.Ньюэлл, Г.Саймон, Дж.Шоу – 1957 г.).

Процесс работы GPS в общем воспроизводит методы решения задач, применяемые человеком: выдвигаются подцели, приближающие к решению; применяется эвристический метод (один, другой и т. д.), пока не будет получено решение. Попытки прекращаются, если получить решение не удается.

Проблемная среда в системе GPS описывается с использованием таких понятий/терминов:

● Объекты (элементы проблемной среды)

● Различия (между Объектами)

● Операторы (способы преобразования Объектов)

● Цель

Три основных Метода (не зависящих от конкретной предметной области):

1. Преобразовать один Объект в другой: A → B

а) Сравнить A с B, найти D = (A - B)

если D = 0, то FIN (успех)

б) ПОДЦЕЛЬ: Уменьшить Различие D

если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с B)

в) ПОДЦЕЛЬ: Преобразовать A’ → B

если это не удается, то FIN (неудача), иначе FIN (успех)

2. Уменьшить Различие между двумя Объектами: D = (A - B)

а) Найти оператор Q, подходящий для уменьшения Различия D

если это не удается, то FIN (неудача)

б) Предварительная проверка применимости Оператора

если Оператор эту проверку не прошел, то FIN (неудача)

в) ПОДЦЕЛЬ: Применить Оператор Q (A), результат A’, FIN (успех)

3. Применить Оператор к Объекту: Q (A)

а) Найти D = (prec (Q) - A)

если D = 0, то результат A’’, FIN (успех)

б) ПОДЦЕЛЬ: Уменьшить Различие D

если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с prec(Q))

в) ПОДЦЕЛЬ: Применить Оператор Q (A’), результат A’’,

если это не удается, то FIN (неудача), иначе FIN (успех)

Какие части GPS являются общими для разных систем, какие меняются, дать примеры. Почему можно утверждать, что GPS реализует редукцию задач?

Дата добавления: 2015-06-27