Представьте, что вы потеряли ключи от своей машины. Известно, что они находятся где-то в вашем доме, план которого выглядит примерно так:
+---------+---------+------+------------+
| | | | |
|Спальня 2|Спальня 1|Ванная|Кухня(ключи)|
| | | | |
+---/ ----+----/ ---+--/ --+-----/ -----+
| |
| Холл |
+-------/ ----------+ |
| | |
| Большая спальня | Гостиная |
| | |
+-------------------+-------- X --------+
Вы стоите там, где находится входная дверь (указанная буквой X). Начиная поиск, вы проверяете гостиную. Потом проходите через холл в первую спальню, затем, опять пересекая холл, — во вторую спальню, возвращаетесь в холл и проходите в большую спальню. Не найдя ключи, вы возвращаетесь, снова проходя через гостиную, и находите свои ключи на кухне. Такую ситуацию легко представить в виде графа (рис. 25.1).
Тот факт, что задачи поиска можно представить в виде графа, является достаточно важным, потому что граф наглядно показывает, как работают разные приемы поиска[1]. (Кроме того, возможность представлять задачи в виде графов позволяет исследователям искусственного интеллекта применять разные теоремы теории графов. Однако эти теоремы в книге не рассматриваются.) Помня о такой возможности, познакомьтесь с такими определениями из теории графов:
| Вершина (графа) | Дискретная точка |
| Лист | Вершина дерева, не имеющая дочерних вершин |
| Область поиска | Множество всех вершин |
| Цель | Разыскиваемая вершина |
| Эвристика | Процедура предпочтения при выборе вершины |
| Цепочка, ведущая к решению (путь к решению) | Ориентированный граф с вершинами, через которые пришлось пройти при поиске решения |
В примере с потерянными ключами каждая комната в доме — это вершина, весь дом — это область поиска; целью, при достижении которой поиск завершается, является кухня, а цепочка, ведущая к решению, показана на рис. 25.1. Спальни, кухня и ванная являются листами, потому что никуда дальше не ведут. Хотя в приведенном примере эвристика не используется, но в данной главе мы рассмотрим ее чуть позже.
[1]Поиск связан с методами исследования древовидных структур, с помощью которых представляется предметная область. Поэтому особое значение в методах искусственного интеллекта уделяется поиску в специальных графах — деревьях. По этой же причине и терминология в этой области испытывает сильное влияние теории деревьев.