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

148 6.3. Направленный поиск © Иваново f = 0+230 = = 230 I Иваново Юрьев-Польский Владимир f= 100+164 = = 264 f =150+180 = = 320 f = 200+140 = = 340 Иваново Владимир Юрьев-Польский f = 200+140 = = 340 t =150+180 = f = 100+164 = \= 320 = 264 Москва I 9 Иваново f =200+230= =430 f« 350+0 = 350 Рис. б.б. Поиск по критерию цены пути (А* - поиск) почти для всех допустимых критериев Л(А) близости к цели. Критерии/(А), для которых имеет место подобное свойство, называются монотонными. Если монотонность нарушается, то путем незначительной коррекции это нарушение может быть устранено. Рассмотрим, например, пару вершин Ь> Ь', где b предшественник, а Ь' — последователь. Предположим, что g(b) = 3, h(b) = 4. Тогда f(b) = 7, т.е. цена пути через вершину b самое меньшее равна 7. Предположим также, что g(b') = 4, h(b') - 2, т.е. fibyl— 6 . Ясно, что в этом случае критерий f(b) не является монотонным. К' счастью, благодаря тому, что любой путь через Ь является также путем через Ь, цена пути /(#) = 6 является бессмысленной. Поэтому каждый раз, как рассматривается какая-либо вершина Ь' и оказывается, что ее цена пути f(V) < f(b), мы полагаем, что f(b') =/(fc), т.е.Дб') « max (f{b), f(b')).