Искусственный интеллект

146 6.3. Направленный поиск © Иваново Владимир( 1 Юрьев-Польский h = 180 h= 140 {Иваново Юрьев-Польский Владимир Переславль Киржач Залесский h=150 h=116 Яроа = 52 h = 0 Москва Рис. 6.5. Поиск по критерию близости к цели На первом шаге вычисляется кратчайшее расстояние от корневой вершины (Иваново) до Москвы (Л = 230). На втором шаге просматриваются все вершины (города), в которые ведет дорога из Иванова и вычисляется кратчайшее расстояние Л от этих городов до Москвы. По этому критерию ближайшим по прямой до цели (Москвы) оказывается Юрьев-Польский (Л = 140). На третьем шаге просматриваются все вершины, в которые ведет дорога из Юрьева- 147 6. Стратегии поиска Польского. Для них снова вычисляется кратчайшее расстояние Л до Москвы. Кратчайшим оказывается расстояние от Киржача (Л = 76). Наконец, на последнем шаге вновь просматриваются все вершины, в которые ведет дорога из Киржача, а также вычисляется кратчайшее расстояние до этих городов. Среди этих городов оказывается город с кратчайшим расстоянием h — О, т.е. целевая вершина (Москва). На этом поиск по критерию близости к цели завершается. Поиск по критерию близости к цели является поиском в глубину, но с выбором на каждом шаге единственной вершины, от которой начинается следующий шаг. Недостатки этой стратегии те же, что и для слепого поиска в глубину, а именно, она неоптимальная и неполная, поскольку может случиться, что поиск пойдет по бесконечному пути и никогда не вернется назад. Оценка сложности по времени этой стратегии поиска равна 0(/<0, где d— максимальная глубина пространства поиска.При поиске по критерию близости.к цели приходится хранить все вершины, рассматриваемые при поиске. Поэтому оценка сложности по памяти для этой стратегии та же, что и оценка сложности по времени. Если критерий близости к цели выбран достаточно удачно, то сложность поиска может быть существенно уменьшена.