Представление и термилогия

Содержание

Представьте, что вы потеряли ключи от своей машины. Известно, что они находятся где-то в вашем доме, план которого выглядит примерно так:

+---------+---------+------+------------+
|         |         |      |            |
|Спальня 2|Спальня 1|Ванная|Кухня(ключи)|
|         |         |      |            |
+---/ ----+----/ ---+--/ --+-----/ -----+
|                                       |
|            Холл                       |
+-------/ ----------+                   |
|                   |                   |
|  Большая спальня  |      Гостиная     |
|                   |                   |
+-------------------+-------- X --------+


Вы стоите там, где находится входная дверь (указанная буквой X). Начиная поиск, вы проверяете гостиную. Потом проходите через холл в первую спальню, затем, опять пересекая холл, — во вторую спальню, возвращаетесь в холл и проходите в большую спальню. Не найдя ключи, вы возвращаетесь, снова проходя через гостиную, и находите свои ключи на кухне. Такую ситуацию легко представить в виде графа (рис. 25.1).

Тот факт, что задачи поиска можно представить в виде графа, является достаточно важным, потому что граф наглядно показывает, как работают разные приемы поиска[1]. (Кроме того, возможность представлять задачи в виде графов позволяет исследователям искусственного интеллекта применять разные теоремы теории графов. Однако эти теоремы в книге не рассматриваются.) Помня о такой возможности, познакомьтесь с такими определениями из теории графов:



Вершина (графа)Дискретная точка
ЛистВершина дерева, не имеющая дочерних вершин
Область поискаМножество всех вершин
ЦельРазыскиваемая вершина
ЭвристикаПроцедура предпочтения при выборе вершины
Цепочка, ведущая к решению (путь к решению)Ориентированный граф с вершинами, через которые пришлось пройти при поиске решения



В примере с потерянными ключами каждая комната в доме — это вершина, весь дом — это область поиска; целью, при достижении которой поиск завершается, является кухня, а цепочка, ведущая к решению, показана на рис. 25.1. Спальни, кухня и ванная являются листами, потому что никуда дальше не ведут. Хотя в приведенном примере эвристика не используется, но в данной главе мы рассмотрим ее чуть позже.

----------
[1]Поиск связан с методами исследования древовидных структур, с помощью которых представляется предметная область. Поэтому особое значение в методах искусственного интеллекта уделяется поиску в специальных графах — деревьях. По этой же причине и терминология в этой области испытывает сильное влияние теории деревьев.