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