Материал: Описание самостоятельной работы студентов по дисциплине Cистемы представления знаний

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

Представить в виде системы продукций. Рассмотреть применение различных стратегий управления системами продукций и сравнить результаты.

2.2.3. Задача о разливе воды

Имеется два кувшина: емкостью 5 л и 2 л. Большой кувшин полон воды, малый кувшин пуст. Требуется отлить 1 л воды в малый кувшин. Больше воды нет.

Представить в виде системы продукций. Рассмотреть применение различных стратегий управления системами продукций и сравнить результаты.

2.2.4. Приведение к каноническому виду

Привести логическое выражение, составленное из переменных и связок

, , ¬ к каноническому виду (канонической формой логических выражений, являются, частности, дизъюнктивная нормальная форма и конъюнктивная нормальная форма).

Предложить систему продукций и исследовать ее тип. Можно ли использовать эту систему продукций для доказательства тождества двух логических выражений?

12

Тема 3. Алгоритмы поиска

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

3.1.Вопросы для самопроверки

1.Что такое граф поиска? Что является узлами и что является дугами в этом графе?

2.Сформулируйте основной алгоритм поиска на графе. Какова трудоемкость этого алгоритма в худшем случае?

3.Что называется эвристическим поиском? Что такое оценочная функция, и какова ее роль в эвристическом поиске?

4.Какими свойствами обладает алгоритм поиска на графе? Каково достаточное условие, обеспечивающее нахождение решения алгоритмом поиска на графе?

5.Сформулируйте теорему состоятельности.

6.Сформулируйте следствия к теореме состоятельности.

7.Что такое монотонное ограничение?

8.Какими свойствами обладает алгоритм поиска на графе, если оценочная функция удовлетворяет монотонному ограничению?

9.В каком случае оценочная функция называется более информированной по сравнению с другой оценочной функцией?

10.Что такое граф И/ИЛИ? Можно ли считать, что произвольный ориентированный гиперграф является графом И/ИЛИ?

13

11.Что такое граф решения? Можно ли считать, что произвольный гиперпуть является графом решения?

12.Что такое игровое дерево? Что общего и в чем отличия игровых деревьев и графов И/ИЛИ?

13.В чем заключается метод минимакса для поиска на игровых деревьях?

14.В чем заключается α-β отсечение при поиске на игровых деревьях?

15.Каков максимальный возможный выигрыш в эффективности при применении α-β отсечения?

3.2.Задачи для самостоятельного решения

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

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

14

3.2.1. Задача коммивояжера

Имеется множество городов, соединенных дорогами. Коммивояжер должен посетить все города ровно один раз. Расстояния между городами известны. Начинать можно с любого города. Возвращаться в него не обязательно. Дороги есть из любого города в любой. Нужно найти, по возможности, кратчайший маршрут.

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

3.2.2. Задача о четырех ферзях

Имеется квадратная доска 4 на 4. Расставить на доске 4 ферзя так, чтобы они не били друг друга. Ферзь бьет поля, расположенные на той же горизонтали, вертикали и диагоналях (на рисунке знаком Х отмечены те поля, которые бьет ферзь, помещенный в поле, отмеченное Q).

Рассмотреть граф поиска, предложить различные оценочные функции и сравнить их применение.

3.2.3. Игра НИМ

Игра НИМ (упрощенная). Имеется куча из семи монет. Играют двое. За один ход можно взять 1, 2 или 3 монеты. Проигрывает тот, кто берет последнюю монету.

15