Рекомендуемая литература. Упражнения.
Хорошим введением в проблематику искусственного интеллекта могут послужить книги Рича и Найта [Rich and Knight, 1991] и Уинстона [Winston, 1992].
Для студентов хорошим источником ссылок на работы в этой области, хотя и несколько устаревшие с точки зрения сегодняшнего дня, являются различные выпуски серии Handbook of Artificial Intelligence ([Barr and Feigenbaum, 1981, 1982]; [Cohen and Feigenbaum, 1982]).
Читателям, интересующимся проблемой машинного распознавания естественного языка, рекомендую прочесть книгу Аллена (Allen, 1995), в которой описаны фундаментальные исследования в этой области, а о том, каким видится будущее искусственного интеллекта из окон лабораторий МИТ, читатель сможет узнать в книге Уинстнона и Шелларда [Winston andShellard, 1990].
Начальные главы книги Нильсона [Nilsson, 1980] по-прежнему остаются лучшим описанием методики эвристического поиска, но более строгое математическое изложение этого материала можно найти в работе Перла [Pearl, 1984].
Некоторые примеры приложения методики эвристического поиска, взятые из современной практики, собраны в сборнике [Rayward-Smith et al, 1996], а Рейард-Смит в своей книге излагает современный взгляд на эти методы [Rayward-Smith, 1994].
Алгоритмы, аналогичные рассмотренному А, по-прежнему привлекают немалое внимание. Например, в одной из последних статей Корфа и Рейда [Korf and Reid, 1998] показано, что эвристики значительно улучшают процесс поиска не тем, что сужают поиск, как считалось до сих пор, а уменьшая его глубину. Таким образом, оказывается, что эвристики способствуют отысканию более коротких путей решения, не снижая при этом фактор ветвления.
Упражнения
Упражнение 1
Почему пакет программ статистического анализа нельзя считать программой искусственного интеллекта?
Упражнение 2
Могут ли психологи подсказать нам, как сконструировать думающую машину?
Упражнение 3
Как вы понимаете термин "пространство поиска"? Что представляет собой пространство поиска в игре в шахматы?
Упражнение 4
Как вы понимаете термин "пространство решений"? Что представляет собой пространство решений в игре в шахматы?
Упражнение 5
Ниже приведен алгоритм поиска в глубину. Он записан с помощью функциональной нотации, которая подчеркивает его рекурсивную структуру. Таким образом, dfs представляет собой функцию трех аргументов: goal, current и pending:
- goal – это объект поиска,
- current – текущий узел на графе состояний (в самом начале – узел исходного состояния),
- pending – список узлов, претендующих на обработку (в самом начале – пустой).
В дальнейшем используются следующие обозначения:
- символ: = означает присваивание;
- функция expand формирует узлы, следующие за аргументом этой функции; знак + означает слияние двух списков, т.е.
(а b с) + (d e f) = (а b с d e f);
- () означает пустой список;
- first и rest – функции, которые возвращают начало и конец списка:
first(a b с) = a rest(a b c) = (b c).
I) Выразите следующий алгоритм на каком-либо из известных вам языков программирования.
dfsfgoal, current, pending)
{
if current = goal, then success;
else
{
pending: = expand (current}+ pending;
if pending = () then fail;
else dfs(goal, first(pending),.rest(pending));
} }
II) Разработайте аналогичный алгоритм для поиска в ширину и реализуйте его на том же языке. Необходимо будет изменить только одно выражение в функции dfs.