Упражнения

Упражнения

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.

6. Рассмотрите головоломку "миссионеры и каннибалы", схематически представленную на рис. 2.6.