Часть 8.

<4.1. ><Алгоритм ><эвристического ><поиска>

<><4.1.1. ><"Жадный" ><алгоритм ><поиска>

<Наиболее ><простой ><путь ><эвристического ><поиска- ><это ><применение ><процедуры ><поиска ><экстремума ><(hill ><Стратегии, ><основанные ><на ><поиске ><экстремума, ><оценивают ><не ><только ><текущее ><состояние ><поиска, ><но ><и ><его ><потомков. ><Для ><дальнейшего ><поиска ><выбирается ><наилучший ><потомок; ><при ><этом ><о ><его ><братьях ><и ><родителях ><просто ><забывают. ><Поиск ><>прекращается<, ><когда ><достигается ><состояние, ><которое ><лучше ><чем ><любой ><из ><его ><наследников. ><Поиск ><экстремума ><- ><название ><стратегии, ><которая ><может ><быть ><использована ><энергичным, ><но ><>слепым< ><альпинистом, ><поднимающимся ><вдоль ><наиболее ><крутого ><склона ><до ><тех ><пор, ><пока ><он ><не ><сможет ><идти ><дальше. ><Так ><как ><в ><этой ><стратегии ><данные ><о ><предыдущих ><состояниях ><не ><>сохраняются<, ><то ><алгоритм ><не ><может ><быть ><восстановлен ><из ><точки, ><которая ><привела ><к ><"неудаче".>

<Основная ><проблема ><стратегий ><поиска ><экстремума ><- ><это ><их ><тенденция ><>останавливаться< ><в ><локальном ><максимуме. ><Другими ><словами, ><как ><только ><они ><достигают ><состояния, ><имеющего ><лучшую ><оценку, ><чем ><его ><потомки, ><алгоритм ><завершается. ><Если ><это ><состояние ><является ><не ><решением ><задачи, ><а ><только ><локальным ><максимумом, ><то ><такой ><алгоритм ><не­><приемлем ><для ><данной ><задачи. ><Это ><значит, ><что ><решение ><может ><быть ><оптимальным ><на ><>ограниченном< ><множестве, ><но ><из-за ><формы ><всего ><пространства, ><возможно, ><никогда ><не ><будет ><выбрано ><наилучшее ><решение. ><Пример ><такого ><локального ><экстремума ><появляется ><в ><игре ><в ><"пятнашки". ><Часто ><для ><того, ><чтобы ><передвинуть ><фишку ><в ><нужную ><позицию, ><необходимо ><сдвинуть ><фишку, ><находящуюся ><в ><наилучшей ><позиции. ><Без ><этого ><невозможно ><решить ><>головоломку<, ><но ><в ><то ><же ><время ><на ><данном ><этапе ><это ><ухудшает ><состояние ><системы. ><Дело ><в ><том, ><что ><"лучший" ><не ><означает ><"идеальный". ><Методы ><поиска ><без ><механизмов ><возврата ><или ><других ><приемов ><восстановления ><не ><могут ><отличить ><локальный ><максимум ><от ><>глобального<. ><Существуют ><методы ><приближенного ><решения ><этой ><проблемы, ><например, ><случайное ><возмущение ><оценки. ><Однако ><гарантированно ><решать ><задачи ><с ><использованием ><техники ><поиска ><экстремума ><нельзя. ><Вариант ><алгоритма ><поиска ><экстремума ><предлагается ><в ><тесто­><вой ><программе, ><описанной ><в ><подразделе ><4.3.2.>

<Несмотря ><на ><эти ><ограничения, ><алгоритм ><поиска ><экстремума ><может ><быть ><достаточно ><>эффективным<, ><если ><оценивающая ><функция ><позволяет ><избежать ><локального ><максимума ><и ><>зацикливания< ><алгоритма. ><В ><общем, ><однако, ><эвристический ><поиск ><требует ><более ><гибкого ><>метода<, ><предусмотренного ><в ><"жадном" ><алгоритме ><поиска, ><где ><при ><использовании ><приоритет­><ной ><очереди ><возможно ><восстановление ><алгоритма ><из ><точки ><локального ><максимума.>

<Подобно ><алгоритмам ><поиска ><в ><глубину ><и ><алгоритмам ><поиска ><в ><ширину, ><описанным ><в ><главе ><3, ><"жадный" ><алгоритм ><поиска ><использует ><списки ><сохраненных ><состояний: ><список ><отслеживает ><текущее ><состояние ><поиска, ><а ><в ><записываются ><уже ><проверен->

<><Глава ><4. ><Эвристический ><поиск>< ><153>

><<ные ><состояния. ><На ><каждом ><шаге ><алгоритм ><записывает ><в ><список ><состояние ><с ><учетом ><некоторой ><эвристической ><оценки ><его ><"близости ><к ><цели". ><Таким ><образом, ><на ><каждой ><>итерации< ><рассматриваются ><наиболее ><перспективные ><состояния ><из ><списка ><Псевдокод ><для ><функции, ><реализующей ><"жадный" ><алгоритм ><поиска ><приведен ><ниже.>

< ><:= >< >< ><[Start]><; ><%инициализация >< >< ><:= >< >< ><[ >< >< ><];>

< >< ><[ >< >< ><] >< >< >< ><%оставшиеся ><состояния>

<удалить >< ><первое >< ><состояние ><из ><списка >< >< ><путь >< ><от >< ><к ><.>

<сгенерировать ><потомок ><каждого ><потомка >

<потомок ><не >< ><содержится >< ><в >< ><списке ><или >

<присвоить >< ><потомку ><эвристическое >< ><значение; ><добавить >< ><потомок ><в >< ><список >

<потомок ><уже ><содержится ><в ><списке ><потомок ><был ><достигнут >< ><по ><кратчайшему ><пути ><записать >< ><это ><состояние ><в ><список ><потомок ><уже >< ><содержится >< ><в >< ><списке >< >< ><потомок ><был ><достигнут >< ><по ><кратчайшему ><пути >

<удалить >< ><состояние ><из >< ><списка ><добавить ><потомок ><в ><список >

< ><%case>

<поместить ><в >< ><список >

<переупорядочить >< ><состояния ><в >< ><списке ><в >< ><соответствии ><с ><эвристикой >< >< ><(лучшие ><слева) >

< ><%список ><пуст>

<На ><каждой ><итерации ><функция ><удаляет ><первый ><элемент ><из ><списка ><Достигнув ><цели, ><алгоритм ><возвращает ><путь, ><который ><ведет ><к ><решению. ><За­><метим, ><что ><каждое ><состояние ><сохраняет ><информацию ><о ><предшествующем ><состоянии, ><чтобы ><впоследствии ><восстановить ><его ><и ><позволить ><алгоритму ><найти ><кратчайший ><путь ><к ><решению ><(см. ><подраздел ><3.2.3.).>

<Если ><первый ><элемент ><в ><списке ><не ><является ><решением, ><то ><алгоритм ><использует ><про­><дукционные ><правила ><проверки ><соответствия ><и ><операции, ><чтобы ><сгенерировать ><все ><возможные ><потомки ><данного ><элемента. ><Если ><потомок ><уже ><находится ><в ><списке ><или ><то ><ал­><горитм ><выбирает ><кратчайший ><из ><двух ><возможных ><путей ><достижения ><этого ><состояния.>

<Затем ><функция ><вычисляет ><эвристическую ><оценку ><состояний ><в ><списке ><и ><сортирует ><список ><в ><соответствии ><с ><этими ><эвристическим ><значениям. ><При ><этом ><"лучшие" ><состояния ><ставятся ><в ><начало ><списка. ><Заметим, ><что ><из-за ><эвристической>

<><154>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<природы ><оценивания ><следующее ><состояние ><должно ><проверяться ><на ><любом ><уровне ><>пространства< ><состояний. ><Отсортированный ><список ><часто ><называют ><приоритетной ><очередью ><(priority >

<>

<Рис. ><4.4. ><Эвристический ><поиск ><в ><гипотетическом ><пространстве ><состояний>

<На ><рис. ><4.4 ><показано ><гипотетическое ><пространство ><с ><эвристическими ><оценками ><>некоторых< ><из ><его ><состояний. ><Состояния, ><рядом ><с ><которыми ><стоит ><их ><эвристическая ><оценка, ><были ><сгенерированы ><функцией ><Состояния, ><по ><которым ><велся ><>эвристический< ><поиск, ><отмечены ><полужирном ><шрифтом; ><заметьте, ><что ><поиск ><не ><ведется ><по ><всему ><пространству. ><Другими ><словами, ><цель ><"жадного" ><алгоритма ><поиска ><состоит ><в ><том, ><чтобы ><прийти ><к ><целевому ><состоянию ><кратчайшим ><путем. ><Чем ><более ><обоснованной ><является ><>эвристика< ><(см. ><подраздел ><4.2.3), ><тем ><меньше ><состояний ><нужно ><проверить ><при ><поиске ><цели.>

<Путь, ><по ><которому ><функция ><находит ><целевое ><состояние, ><по><казан ><на ><рисунке ><жирными ><стрелками. ><Предположим, ><что ><Р ><- ><целевое ><состояние ><(см. ><рис. ><4.4). ><Поскольку ><Р ><- ><цель, ><состояния ><на ><пути ><к ><Р ><имеют ><низкие ><эвристические ><зна­><чения. ><Эвристика ><подвержена ><ошибкам: ><состояние ><О ><имеет ><более ><низкое ><эвристическое ><значение, ><чем ><целевое, ><и ><поэтому ><было ><исследовано ><ранее. ><В ><отличие ><от ><поиска ><экстре­><мума, ><который ><не ><сохраняет ><приоритетную ><очередь ><для ><отбора ><"следующих" ><состояний, ><данный ><алгоритм ><восстанавливается ><после ><ошибки ><и ><находит ><целевое ><состояние.>

<- ><[А-5]; ><= ><[].>

<Вычисляем ><А-5;ореn ><= ><[B-4, ><С-4, ><= ><[А-5].>

<Вычисляем ><ореn ><=>< ><[С-4,Е-5, ><= ><[S-4, ><А-5].>

<Вычисляем ><С-4; ><= ><[Н-3, ><Е-5, ><= ><[С-4, ><В-4, ><А-5].>

<Вычисляем ><Н-3; ><= ><[0-2, ><Р-3, ><Е-5, >

><= ><[Н-3, ><С-4, ><В-4, ><А-5].>

<Вычисляем ><0-2; ><= ><[Р-3, ><Е-5, >

><= ><[О-2, ><Н-3, ><С-4, ><В-4, ><А-5].>

<Вычисляем ><Р-3; ><решение ><найдено!>

<><Глава ><4. ><Эвристический ><поиск>< ><155>

><<>

<Рис. ><4.5. ><Эвристический ><поиск ><в ><гипотетическом ><про><странстве ><состояний. ><Состояния ><из ><списков ><и ><выделены>

<На ><рис. ><4.5 ><показано ><пространство ><после ><пятой ><итерации ><цикла ><Здесь ><>показаны< ><состояния, ><содержащиеся ><в ><списках ><и ><В ><сохраняется ><текущая ><граница ><поиска, ><а ><в ><- ><уже ><рассмотренные ><состояния. ><Заметьте, ><что ><граница ><по­><иска ><очень ><искривлена, ><отражая ><тем ><самым ><приспособленческую ><природу ><"жадного" ><>алгоритма< ><поиска.>

<"Жадный" ><алгоритм ><поиска ><всегда ><выбирает ><наиболее ><перспективное ><состояние ><в ><для ><продолжения. ><Однако, ><поскольку ><при ><выборе ><состояния ><используется ><>эвристика<, ><которая ><может ><оказаться ><ошибочной, ><алгоритм ><не ><отказывается ><от ><остальных ><состояний, ><и ><сохраняет ><их ><в ><списке ><В ><данном ><случае ><эвристика ><обеспечивает ><поиск ><вниз; ><этот ><путь ><оказывается ><ошибочным, ><но ><алгоритм ><в ><итоге ><возвращается ><к ><некоторому ><ранее ><сгенерированному ><"лучшему" ><состоянию ><в ><и ><затем ><>продолжает< ><поиск ><в ><другой ><части ><пространства. ><В ><примере ><на ><рис. ><4.4 ><после ><нахождения ><потом­><ков ><состояния ><В ><казалось, ><что ><они ><имеют ><плохие ><эвристические ><оценки, ><и ><поэтому ><по­><иск ><сместился ><к ><состоянию ><С. ><При ><этом ><потомки ><состояния ><В ><были ><сохранены ><в ><на ><случай, ><если ><алгоритму ><необходимо ><будет ><вернуться ><к ><ним ><позже. ><В ><функции ><как ><и ><в ><алгоритмах ><из ><главы ><3, ><список ><позволяет ><воз­><вращаться ><назад ><по ><ошибочному ><пути.>

<4.1.2. ><Функции ><эвристической ><оценки ><состояний>

<Рассмотрим ><эффективность ><нескольких ><различных ><эвристик ><для ><решения ><8-головоломки. ><На ><рис. ><4.6 ><показано ><начальное ><и ><целевое ><состояние ><для ><8-головоломки ><вместе ><с ><первыми ><тремя ><возможными ><состояниями, ><сгенерированными ><в ><процессе ><поиска.>

<Самая ><простая ><эвристика ><подсчитывает ><количество ><фишек, ><находящихся ><не ><на ><своих ><местах, ><в ><каждом ><состоянии, ><сравнивая ><его ><с ><целевым ><состоянием.>

<><156>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

<Рис. ><4.6. ><Начальное ><состояние, ><набор ><возможных ><пер><вых ><ходов ><и ><целевое ><состояние ><в ><игре ><"8-головоломка ><">

<Состояние ><с ><меньшим ><числом ><фишек, ><находящихся ><не ><на ><своих ><местах, ><расположено ><ближе ><к ><целевому ><состоянию, ><и ><поэтому ><будет ><рассмотрено ><первым.>

<Однако ><эта ><эвристика ><не ><использует ><всю ><имеющуюся ><информацию, ><потому ><что ><она ><не ><принимает ><во ><внимание ><расстояние, ><на ><которое ><фишки ><должны ><быть ><перемещены. ><"Лучшая" ><эвристика ><суммировала ><бы ><все ><расстояния ><между ><фишкой, ><находящейся ><не ><на ><своем ><месте, ><и ><полем, ><в ><которое ><она ><должна ><быть ><перемещена ><для ><достижения ><целевого ><состояния.>

<Обе ><эти ><эвристики ><можно ><критиковать ><за ><то, ><что ><они ><не ><учитывают ><трудности ><при ><перестановке ><фишек. ><Другими ><словами, ><если ><для ><достижения ><целевого ><состояния ><>необходимо< ><переставить ><две ><рядом ><стоящие ><фишки, ><то ><это ><потребует ><более ><двух ><ходов, ><так ><как ><для ><такой ><перестановки ><фишки ><должны ><"обойти" ><друг ><друга ><(рис. ><4.7).>

<>

<Рис. ><4.7. ><Целевое ><состояние ><и ><состояние ><с ><двумя ><перестановками: ><1 ><и ><2, ><5и6>

<Эвристика, ><принимающая ><во ><внимание ><этот ><факт, ><для ><каждой ><инверсии ><(когда ><для ><достижения ><целевого ><состояния ><необходимо ><поменять ><местами ><две ><рядом ><стоящие ><>фишки<) ><должна ><умножать ><эвристическое ><значение ><на ><малое ><число ><(например ><2). ><На ><рис. ><4.8>

<><Глава ><4. ><Эвристический ><поиск>

<157>

><<показан ><результат ><применения ><каждой ><из ><этих ><трех ><эвристик ><к ><трем ><потомкам, ><>изображенным< ><на ><рис. ><4.6.>

<На ><рис. ><4.8 ><показан ><результат ><применения ><оценивающих ><функций. ><Эвристика ><"суммы ><рас­><стояний", ><кажется, ><действительно ><дает ><более ><точную ><оценку ><затрат, ><чем ><простой ><подсчет ><чис­><ла ><фишек, ><находящихся ><не ><на ><своих ><местах. ><Эвристика ><перестановки ><фишек ><не ><может ><найти ><различий ><между ><этими ><состояниями, ><давая ><каждому ><из ><них ><оценку, ><равную ><нулю. ><Эвристика ><"суммы ><состояний" ><не ><приводит ><к ><решению, ><так ><как ><ни ><одно ><из ><этих ><состояний ><не ><содержит ><ни ><одной ><прямой ><инверсии. ><Четвертый ><вариант ><эвристики, ><преодолевающий ><ограничения, ><>накладываемые< ><на ><эвристику ><"перестановки ><фишек", ><- ><сложить ><расстояния ><между ><фишками, ><удвоив ><расстояния ><между ><элементами, ><которые ><должны ><быть ><взаимно ><переставлены.>

<Этот ><пример ><иллюстрирует, ><насколько ><трудно ><найти ><хорошую ><эвристику. ><Наша ><цель ><состоит ><в ><том, ><чтобы, ><используя ><ограниченную ><информацию, ><содержащуюся ><в ><описании ><отдельного ><состояния, ><все ><же ><сделать ><правильный ><выбор. ><Каждая ><из ><эвристик, ><>предложенных< ><выше, ><игнорирует ><некоторые ><критические ><элементы ><информации, ><и ><поэтому ><может ><быть ><улучшена. ><Разработка ><хорошей ><эвристики ><- ><это ><эмпирическая ><проблема, ><в ><решении ><которой ><помогают ><рассуждения ><и ><интуиция. ><Но ><все ><же ><решающий ><критерий ><оценки ><эвристики ><- ><это ><ее ><эффективность ><при ><решении ><практических ><задач.>

<Поскольку ><эвристика ><может ><быть ><ошибочной, ><существует ><вероятность, ><что ><алгоритм ><поиска ><может ><пойти ><по ><ложному ><пути. ><Эта ><проблема ><возникала ><при ><поиске ><в ><глубину, ><где ><подсчет ><глубины ><использовался ><для ><того, ><чтобы ><определить ><ложные ><пути. ><Эта ><идея ><может ><быть ><также ><применена ><в ><эвристическом ><поиске. ><Если ><два ><состояния ><имеют ><одинаковые ><или ><почти ><одинаковые ><эвристические ><значения, ><то ><предпочтительнее ><исследовать ><состояние, ><которое ><расположено ><ближе ><к ><корневому ><состоянию ><графа. ><Это ><состояние ><с ><большей ><>вероятностью< ><расположено ><на ><пути ><к ><цели. ><Расстояние ><от ><начального ><состояния ><к ><его ><потомкам ><может ><быть ><измерено ><путем ><вычисления ><уровня ><глубины ><для ><каждого ><состояния.>

<>

<Рис. ><4.8. ><Три ><возможных ><варианта ><эвристики ><в ><8-головоломке>

<><158>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Для ><начального ><состояния ><это ><значение ><равно ><0 ><и ><увеличивается ><на ><1 ><для ><каждого ><уровня ><поиска. ><Это ><позволяет ><записать ><фактическое ><число ><шагов, ><необходимых ><для ><>достижения< ><в ><процессе ><поиска ><из ><стартового ><состояния ><любого ><из ><его ><потомков. ><Это ><>значение< ><может ><быть ><добавлено ><к ><эвристической ><оценке ><каждого ><состояния ><для ><того, ><чтобы ><сместить ><поиск ><к ><наиболее ><подходящим ><состояниям.>

<Таким ><образом, ><оценивающая ><функция ><состоит ><из ><двух ><компонентов:>

<= ><+ >

<где ><- ><фактическая ><длина ><пути ><от ><произвольного ><состояния ><л ><к ><начальному, ><а ><(><п) ><- ><эвристическая ><оценка ><расстояния ><от ><состояния ><п ><к ><цели.>

<Например, ><в ><8-головоломке ><значением ><можно ><считать ><число ><фишек, ><>находящихся< ><не ><на ><своих ><местах. ><Если ><рассмотреть ><состояния, ><изображенные ><на ><рис. ><4.6, ><то ><значения ><для ><каждого ><из ><них ><будут ><равны ><6,4 ><и ><6 ><соответственно ><(рис. ><4.9).>

<На ><рис. ><4.10 ><показано ><значение ><для ><каждого ><состояния ><графа ><"жадного" ><>алгоритма< ><поиска ><для ><8-головоломки. ><Рядом ><с ><каждым ><состоянием ><указан ><его ><>эвристический< ><вес ><= ><+ ><Номер ><в ><верхней ><части ><состояния ><указывает ><порядок, ><в ><котором ><это ><состояние ><было ><взято ><из ><списка ><Некоторые ><состояния ><(h, ><и ><не ><пронумерованы, ><так ><как ><они ><оставались ><в ><списке ><на ><мо­><мент ><завершения ><алгоритма.>

<>

<Рис. ><4.9. ><Эвристика ><для ><состояний ><в ><игре ><"8-головоломка">

<><Глава ><4. ><Эвристический ><поиск 159>

<<Содержание ><списков ><и ><которые ><генерируют ><этот ><граф, ><приведено ><ниже.>

<= ><[a4]; ><= ><[ ><].>

<= ><[с4, ><= ><[a4].>

<= ><[е5, ><= ><[а4, ><с4].>

<= ><[f5, ><17]; ><= ><[a4, ><с4, ><е5].>

<= ><[f5, ><17]; ><= ><[a4, >

<= ><[f5, ><17]; ><= ><[а4, ><с4, ><е5, >

<= ><[m5, ><17]; ><= ><[а4, ><с4, ><е5, >

<Найдено ><решение ><т ><= ><цель!.>

<На ><3 ><шаге ><состояния ><е ><и ><имеют ><эвристическое ><значение, ><равное ><5. ><Состояние ><е ><>было< ><проверено ><первым, ><его ><потомками ><являются ><и i><. ><Хотя ><л ><является ><потомком ><е, ><для ><него ><число ><фишек, ><расположенных ><не ><на ><своих ><местах, ><соответствует ><состоянию ><при ><этом ><данное ><состояние ><находится ><на ><один ><уровень ><ниже ><в ><пространстве ><состояний. ><Мера ><глубины, ><заставляет ><алгоритм ><выбирать ><в ><качестве ><оценки ><на ><шаге ><4. ><Поэтому ><>алгоритм< ><возвращается ><к ><состоянию ><находящемуся ><на ><один ><уровень ><выше, ><и ><затем ><про­><должает ><двигаться ><к ><цели ><по ><другой ><ветке. ><Граф ><пространства ><состояний ><на ><этой ><стадии ><поиска ><показан ><на ><рис. ><4.11. ><Здесь ><закрашены ><области, ><в ><которых ><находятся ><состояния ><из ><списков ><и ><Обратите ><внимание ><на ><приспособленческую ><природу ><поиска ><до ><первого ><наилучшего ><совпадения.>

<В ><действительности ><компонент ><функции ><оценки ><придает ><нашему ><поиску ><>свойства< ><поиска ><в ><ширину. ><Он ><предотвращает ><возможность ><заблуждения ><из-за ><ошибочной ><оценки: ><если ><эвристика ><непрерывно ><возвращает ><"хорошие" ><оценки ><для ><состояний ><на ><>пути<, ><не ><ведущем ><к ><цели, ><то ><значение ><будет ><расти ><и ><доминировать ><над ><, ><возвращая ><>процедуру< ><поиска ><к ><кратчайшему ><пути. ><Это ><избавляет ><алгоритм ><от ><зацикливания. ><В ><>разделе< ><4.2 ><рассмотрены ><условия, ><при ><которых ><"жадный" ><алгоритм ><поиска ><с ><использованием ><функции ><оценки ><гарантирует ><выбор ><кратчайшего ><пути ><к ><цели.>

<Подведем ><итог.>

<Операции ><над ><состояниями ><позволяют ><генерировать ><потомков ><текущего ><состояния.>

<Каждое ><новое ><состояние ><проверяется ><на ><предмет ><того, ><встречалось ><ли ><оно ><раньше

><(т.е. ><находится ><ли ><оно ><в ><списках ><или ><Таким ><образом, ><>предотвращаются< ><циклы.>

<Каждому ><состоянию ><л ><соответствует ><значение ><, ><равное ><сумме ><его ><глубины ><в ><про­><странстве ><поиска ><и ><некоторой ><эвристической ><оценки ><расстояния ><от ><него ><до

><цели ><Другими ><словами, ><ведет ><алгоритм ><поиска ><к ><эвристически ><наиболее

><перспективным ><состояниям, ><в ><то ><время ><как ><значение ><удерживает ><алгоритм ><от

><упорного ><следования ><по ><неверному ><пути.>

<Состояния ><в ><списке ><сортируются ><в ><соответствии ><со ><значениями ><. ><Сохраняя ><все

><состояния ><в ><списке ><алгоритм ><сможет ><уберечь ><себя ><от ><неудачного ><завершения.>

<Эффективность ><алгоритма ><может ><быть ><увеличена ><за ><счет ><представления ><списков

><и ><в ><виде ><кучи ><(heap) ><или ><левостороннего ><дерева ><(leftist >

<"Жадный" ><алгоритм ><поиска- ><это ><общий ><алгоритм ><для ><эвристического ><поиска ><на ><любом ><графе ><пространства ><состояний ><(как ><и ><алгоритмы ><поиска ><в ><ширину ><или ><в ><глубину, ><рассмотренные ><ранее).>

<><160>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

<Рис. ><4.10. ><Пространство ><состояний, ><сгенерированное ><при ><эвристическом ><поиске ><на ><графе ><игры ><в ><"пятнашки">

<Этот ><алгоритм, ><в ><одинаковой ><степени ><применимый ><к ><поиску ><данных ><и ><поиску ><решения ><за><дачи, ><поддерживает ><различные ><функции ><оценки. ><Далее ><мы ><продолжим ><рассматривать ><>поведение< ><эвристического ><алгоритма ><поиска ><на ><других ><примерах ><(раздел ><4.2). ><Благодаря ><своей ><>универсальности< ><"жадный" ><алгоритм ><поиска ><может ><использоваться ><с ><различными ><эвристиками, ><начиная ><от ><субъективных ><оценок ><"хороших" ><состояний ><и ><заканчивая ><сложными ><критериями ><оценки ><состояний, ><ведущих ><к ><цели, ><на ><основе ><вероятностного ><подхода.>

<><Глава ><4. ><Эвристический ><поиск>

<161>

><<Важным ><примером ><этого ><подхода ><являются ><байесовские ><(Bayesian) ><статистические ><критерии ><(глава ><7).>

<>

<Рис. ><4.11. ><Вид ><списков ><и ><после ><третьей ><итерации ><эвристического ><поиска>

<Другой ><интересный ><подход ><к ><реализации ><эвристики ><- ><использовать ><меру ><доверия ><в ><экспертных ><системах ><для ><анализа ><результатов ><того ><или ><иного ><правила. ><Человек-эксперт, ><используя ><эвристику, ><обычно ><способен ><дать ><квалифицированную ><оценку ><степени ><>доверия< ><своим ><выводам. ><Экспертные ><системы ><используют ><меры ><доверия ><(confidence ><для ><выбора ><тех ><результатов, ><которые ><имеют ><наивысшую ><вероятность ><успеха. ><Состояния>

<><><162>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<с ><наиболее ><низкой ><мерой ><доверия ><могут ><быть ><полностью ><исключены ><из ><рассмотрения. ><Этот ><подход ><к ><эвристическому ><поиску ><будет ><рассмотрен ><в ><следующем ><разделе.>

<4.1.3. ><Эвристический ><поиск ><и ><экспертные ><системы>

<Простые ><игры ><типа ><"пятнашек" ><по ><ряду ><причин ><являются ><идеальными ><примерами ><для ><исследования ><поведения ><алгоритмов ><эвристического ><поиска.>

<Области ><поиска ><достаточно ><обширны, ><чтобы ><использовать ><эвристические ><упрощения.>

<Большинство ><игр ><достаточно ><сложны ><и ><допускают ><большое ><разнообразие ><>эвристических< ><оценок ><для ><сравнения ><и ><анализа.>

<Игры, ><как ><правило, ><описываются ><достаточно ><просто. ><Описание ><пространства ><со­

><стояний ><игровой ><доски ><может ><быть ><сделано ><явно. ><Это ><позволяет ><исследователям

><сосредоточиться ><на ><поведении ><эвристики, ><а ><не ><на ><проблеме ><описания ><задачи.>

<Поскольку ><каждый ><элемент ><пространства ><состояний ><имеет ><одно ><представление

><(описание ><доски), ><одна ><эвристика ><может ><применяться ><во ><всей ><области ><поиска. ><Это

><отличает ><алгоритмы ><эвристического ><поиска ><от ><систем ><типа ><финансового ><>советника<, ><где ><каждый ><элемент ><представляет ><собой ><подцель ><с ><собственным ><явным ><>представлением<.>

<Более ><реалистические ><проблемы ><затрудняют ><выполнение ><и ><анализ ><эвристического ><поиска, ><требуя ><сложной ><эвристики, ><которая ><имеет ><дело ><с ><различными ><ситуациями ><в ><>пространстве< ><состояний. ><Однако ><результаты, ><полученные ><в ><простых ><играх, ><могут ><быть ><ис­><пользованы ><при ><решении ><проблем, ><возникающих ><в ><экспертных ><системах, ><планировании, ><интеллектуальном ><управлении ><и ><машинном ><обучении. ><В ><отличие ><от ><игры ><в ><"пятнашки", ><в ><этих ><системах ><к ><каждому ><состоянию ><не ><может ><быть ><применена ><одна ><и ><та ><же ><эвристика. ><Эвристики, ><решающие ><специфические ><задачи, ><"зашиваются" ><в ><синтаксис ><и ><семантику ><соответствующих ><операторов ><решения ><данной ><задачи. ><На ><каждом ><шаге ><решения ><>определяется<, ><какую ><эвристику ><следует ><использовать. ><Операция ><(эвристика), ><которая ><должна ><быть ><применена ><к ><тому ><или ><иному ><состоянию ><в ><пространстве, ><определяется ><в ><процессе ><проверки ><соответствия ><шаблону.>

<Пример ><4.1.1. ><Модификация ><системы ><финансового ><советника>

<Эвристические ><критерии ><поиска ><традиционно ><используются ><при ><решении ><задач ><ИИ. ><Вернемся ><к ><задаче ><разработки ><финансового ><советника, ><рассмотренной ><в ><главах ><2 ><и ><3, ><где ><база ><знаний ><представляет ><собой ><набор ><логических ><заключений, ><принимающих ><значения ><"истина" ><или ><"ложь". ><В ><действительности ><эти ><правила ><эвристичны ><по ><своей ><природе. ><Например, ><одно ><из ><правил ><гласит, ><что ><человеку ><с ><достаточными ><сбережениями ><и ><>доходом< ><следует ><вложить ><свой ><капитал ><в ><акции:>

<^ >

<На ><самом ><деле ><такой ><человек ><предпочтет ><более ><безопасную ><комбинированную ><>стратегию< ><или ><вообще ><не ><будет ><трогать ><свои ><сбережения. ><Таким ><образом, ><данное ><правило ><эвристично, ><и ><при ><решении ><проблемы ><необходимо ><попытаться ><учесть ><эту ><>неопределенность<. ><Можно ><принимать ><во ><внимание ><дополнительные ><факторы, ><такие ><как ><возраст ><>инвестора<, ><его ><карьеру ><и ><другие ><вопросы. ><Однако ><все ><это ><существенно ><не ><влияет ><на ><>эвристическую< ><природу ><финансового ><совета.>

<><Глава ><4. ><Эвристический ><поиск>< ><163>

><<Один ><из ><путей ><решения ><данной ><проблемы ><в ><экспертных ><системах ><состоит ><в ><том, ><что><бы ><с ><каждым ><правилом ><вывода ><связать ><весовой ><коэффициент ><(называемый ><мерой ><>доверия< ><(confidence ><или ><фактором ><уверенности ><(certainty ><Это ><дает ><>возможность< ><измерить ><степень ><доверия ><к ><каждому ><такому ><выводу.>

<Каждое ><заключение ><связывают ><с ><мерой ><доверия, ><представляющей ><собой ><вещественное ><число ><из ><интервала ><[-1; ><1]. ><При ><этом ><1 ><(истина) ><соответствует ><полному ><доверию, ><а ><-1 ><(ложь) ><- ><недоверию. ><Значения ><из ><этого ><отрезка ><соответствуют ><степени ><доверия ><выводу. ><На­><пример, ><приведенному ><выше ><правилу ><можно ><дать ><оценку ><0,8, ><отражая, ><таким ><образом, ><малую ><вероятность ><того, ><что ><оно ><не ><верно. ><Остальным ><заключениям ><можно ><присвоить ><другие ><веса.>

<л ><= ><0,8. ><л ><= ><0,5. ><л ><= ><0,1.>

<Эти ><правила ><отражают ><следующую ><общую ><стратегию. ><Человеку ><с ><достаточными ><>сбережениями< ><и ><доходом ><настоятельно ><советуют ><вложить ><капитал ><в ><акции, ><но ><существует ><некоторая ><возможность ><(и ><комбинированная ><стратегия ><должна ><учитывать ><ее) ><того, ><что ><он ><может ><по-прежнему ><оставлять ><средства ><в ><банке. ><Эвристические ><алгоритмы ><поиска ><могут ><использовать ><эти ><факторы ><уверенности ><по-разному. ><Например, ><можно ><вычислять ><>результаты< ><применения ><всех ><правил ><с ><учетом ><степени ><доверия ><к ><ним. ><Такой ><полный ><перебор ><всех ><возможностей ><может ><быть ><полезен, ><например, ><в ><медицине. ><Или ><программа ><может ><возвращать ><только ><результат ><с ><наибольшим ><фактором ><уверенности, ><если ><остальные ><>решения< ><не ><представляют ><интереса. ><Это ><позволит ><ей ><игнорировать ><другие ><правила, ><>радикально< ><сужая ><область ><поиска. ><Можно ><также ><игнорировать ><правила ><с ><низкой ><мерой ><>доверия<, ><например, ><не ><выше ><0,2. ><Это ><позволит ><медленнее ><сужать ><пространство ><поиска.>

<При ><использовании ><меры ><доверия ><возникает ><ряд ><важных ><вопросов. ><Что ><понимается ><под ><"числовой ><мерой ><доверия"? ><Например, ><как ><рассчитать ><степень ><доверия, ><если ><один ><вывод ><ис><пользуется ><как ><предпосылка ><для ><других? ><Как ><объединять ><меры ><доверия, ><если ><к ><одному ><и ><тому ><же ><выводу ><можно ><прийти ><несколькими ><путями? ><Как ><назначать ><меру ><доверия ><>основополагающим< ><правилам? ><Эти ><проблемы ><более ><подробно ><будут ><обсуждаться ><в ><главе ><7.>

<4.2. ><Допустимость, ><монотонность ><и ><информированность>

<><Поведение ><эвристики ><можно ><оценивать ><по ><ряду ><параметров. ><Например, ><наряду ><с ><>решением< ><задачи ><может ><понадобиться ><алгоритм ><нахождения ><кратчайшего ><пути ><к ><нему. ><Это ><важно, ><когда ><каждый ><дополнительный ><шаг ><к ><цели ><имеет ><очень ><высокую ><стоимость, ><на­><пример, ><при ><планировании ><пути ><для ><автономного ><робота ><в ><опасной ><среде. ><Эвристика, ><>которая< ><находит ><самый ><короткий ><путь ><к ><цели, ><называется ><допустимой ><(admissible). ><В ><>других< ><приложениях ><кратчайший ><путь ><к ><решению ><может ><быть ><не ><так ><важен, ><как ><общая ><>эффективность< ><решения ><задачи.>

<Можно ><задать ><вопрос: ><существуют ><ли ><лучшие ><эвристики? ><И ><в ><каком ><смысле ><одна ><>эвристика< ><"лучше" ><другой? ><В ><этом ><состоит ><информированность ><(informedness) ><эвристики.>

<Можно ><ли ><гарантировать, ><что ><обнаруженное ><в ><процессе ><эвристического ><поиска ><со><стояние ><нельзя ><было ><найти ><по ><короткому ><пути ><от ><начального ><состояния? ><Это ><свойство ><называется ><монотонностью ><(monotonicity). ><Ответы ><на ><эти ><и ><другие ><вопросы, ><связанные ><с ><эффективностью ><эвристик, ><составляют ><содержание ><этого ><раздела.>

<><164>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<4.2.1. ><Мера ><допустимости>

<Алгоритм ><поиска ><называется ><допустимым, ><или ><приемлемым ><(admissible), ><если ><>гарантирует< ><нахождение ><кратчайшего ><пути ><к ><решению. ><Поиск ><в ><ширину ><является ><допустимой ><стратегией ><поиска. ><Поскольку ><сначала ><рассматриваются ><все ><состояния ><графа ><на ><уровне ><л ><и ><лишь ><затем ><состояния ><на ><уровне ><л+1, ><то ><целевые ><состояния ><будут ><найдены ><по ><>кратчайшему< ><из ><возможных ><путей. ><К ><сожалению, ><поиск ><в ><ширину ><часто ><слишком ><>неэффективен< ><при ><практическом ><использовании.>

<Используя ><функцию ><оценки ><введенную ><в ><предыдущем ><разделе, ><можно ><охарактеризовать ><класс ><допустимых ><эвристических ><стратегий ><поиска. ><Если ><л ><- ><узел ><графа ><пространства ><состояний, ><то ><представляет ><глубину, ><на ><которой ><это ><состояние ><было ><найдено, ><а ><л(л) ><- ><эвристическую ><оценку ><расстояния ><от ><узла ><л ><до ><цели. ><В ><этом ><смысле ><оценивает ><общую ><стоимость ><пути ><от ><начального ><состояния ><к ><целевому ><через ><узел ><л. ><При ><определении ><свойств ><допустимой ><эвристики ><определим ><функцию ><оценки ><Р ><так:>

<где ><- ><стоимость ><кратчайшего ><пути ><от ><начального ><узла ><к ><узлу ><а ><- ><фактическая ><стоимость ><кратчайшего ><пути ><от ><узла ><до ><цели. ><Отсюда ><следует, ><что ><- ><фактическая ><стоимость ><оптимального ><пути ><от ><начального ><узла ><до ><целевого ><через ><узел ><л.>

<В ><дальнейшем ><мы ><увидим, ><что ><при ><использовании ><функции ><с ><функцией ><оценки ><Р ><результирующая ><стратегия ><поиска ><будет ><допустимой. ><Поскольку ><та><кие ><"оракулы" ><как ><Р ><для ><большинства ><реальных ><проблем ><не ><существуют, ><будем ><исполь­><зовать ><функцию ><оценки ><как ><наиболее ><близкую ><к ><В ><алгоритме ><А ><- ><стоимость ><текущего ><пути ><к ><состоянию ><л ><является ><разумной ><заменой ><оценки ><но ><они ><не ><равны: ><Они ><равны ><только ><в ><том ><случае, ><если ><на ><графе ><найден ><оптимальный ><путь ><к >

<Аналогично ><заменим ><на ><- ><эвристическую ><оценку ><минимальной ><стоимо><сти ><достижения ><целевого ><состояния ><из ><узла ><л. ><Как ><правило, ><вычислить ><невозможно, ><но ><достаточно ><часто ><можно ><определить, ><действительно ><ли ><эвристическая ><оценка ><ог­><раничена ><сверху, ><т.е. ><действительно ><ли ><(n) ><не ><превосходит ><фактической ><стоимо­><сти ><кратчайшего ><пути ><Если ><алгоритм ><использует ><функцию ><оценки ><в ><которой ><то ><он ><называется ><алгоритмом ><А*.>

<ОПРЕДЕЛЕНИЕ>

<АЛГОРИТМ ><А, ><ДОПУСТИМОСТЬ, ><АЛГОРИТМ ><А*>

<Рассмотрим ><функцию ><оценки ><(n) ><= ><(n) ><+ ><(n), ><где ><- ><любое ><состояние, ><достижимое ><в ><процессе ><поиска, ><(n) ><- ><стоимость ><пути ><из ><начального ><состояния ><к ><узлу ><л, ><(n) ><- ><эвристическая ><оценка ><стоимости ><пути ><от ><л ><к ><цели.>

<Если >< >< ><эта >< >< ><функция >< >< ><оценки >< >< ><используется >< >< ><в >< >< ><алгоритме >< >< ><(раздел ><4.1), ><результирующий ><алгоритм ><называется ><алгоритмом ><А. ><Поисковый ><алгоритм ><является ><допустимым, ><если ><для ><любого ><графа ><он ><всегда ><выби­><рает ><оптимальный ><путь ><к ><решению.>

<Если ><в ><алгоритме ><А ><используется ><функция ><оценки, ><в ><которой ><значение ><л(л) ><меньше ><или ><равно ><стоимости ><минимального ><пути ><от ><л ><до ><цели, ><такой ><алгоритм ><поиска ><назы><вается ><алгоритмом ><А* ><(произносится ><"А ><со ><звездочкой"). ><Теперь ><можно ><сформулировать ><свойство ><алгоритмов ><А*. ><Все ><алгоритмы ><А* ><допустимы.>

<><Глава ><4. ><Эвристический ><поиск>< ><165>

><<Допустимость ><алгоритмов ><А* ><является ><теоремой, ><которую ><читателю ><предлагается ><до><казать ><в ><рамках ><упражнений ><в ><конце ><главы ><(см. ><также ><[Nilsson, ><1980], ><с. ><76-78). ><Теорема ><гласит, ><что ><любой ><алгоритм ><А* ><(т.е. ><алгоритм, ><использующий ><такую ><эвристику ><при ><которой ><для ><всех ><гарантирует ><нахождение ><минимального ><пути ><от ><л ><до ><це­><ли, ><если ><такой ><путь ><вообще ><существует.>

<Заметим, ><что ><поиск ><в ><ширину ><может ><быть ><охарактеризован ><как ><алгоритм ><А*, ><в ><кото><ром ><= ><д(п)+0. ><Решение ><о ><рассмотрении ><каждого ><состояния ><принимается, ><>исключительно< ><с ><учетом ><его ><расстояния ><от ><начального ><состояния. ><В ><подразделе ><4.2.3 ><будет ><пока­><зано, ><что ><множество ><узлов, ><рассматриваемых ><алгоритмом ><А*, ><- ><это ><подмножество ><со­><стояний, ><рассматриваемых ><при ><поиске ><в ><ширину.>

<Примерами ><алгоритмов ><А* ><являются ><некоторые ><эвристики, ><применяемые ><для ><игры ><в ><"пятнашки". ><Для ><этой ><задачи ><невозможно ><вычислить ><значение ><но ><можно ><показать, ><что ><эвристика ><ограничена ><сверху ><фактической ><стоимостью ><кратчайшего ><пути ><к ><цели.>

<Например, ><число ><фишек, ><расположенных ><не ><на ><месте, ><меньше ><или ><равно ><числу ><шагов, ><требуемых ><для ><их ><перемещения ><в ><целевую ><позицию. ><Таким ><образом, ><такая ><эвристика ><>допустима< ><и ><гарантирует ><нахождение ><оптимального ><(или ><кратчайшего) ><пути ><решения. ><Сумма ><прямых ><расстояний ><фишек, ><находящихся ><не ><на ><своих ><местах, ><до ><их ><целевой ><>позиции< ><также ><меньше ><или ><равна ><минимальному ><фактическому ><пути ><их ><перемещения ><в ><>целевое< ><состояние. ><Использование ><малых ><множителей ><для ><прямых ><перестановок ><фишек ><>является< ><допустимой ><эвристикой.>

<Такой ><подход ><к ><доказательству ><допустимости ><эвристик ><может ><применяться ><в ><>любых< ><задачах ><эвристического ><поиска. ><Даже ><если ><не ><всегда ><можно ><вычислить ><фактиче­><скую ><стоимость ><кратчайшего ><пути ><к ><цели, ><довольно ><часто ><удается ><доказать, ><что ><эв­><ристика ><ограничена ><сверху ><этим ><самым ><значением. ><Если ><этот ><факт ><будет ><доказан, ><то ><результирующий ><поиск ><будет ><ограничен ><сверху ><кратчайшим ><путем ><к ><цели ><в ><случае ><существования ><такого ><пути.>

<4.2.2. ><Монотонность>

<Напомним, ><что ><определение ><алгоритмов ><А* ><не ><требует, ><чтобы ><было ><равно ><Это ><означает, ><что ><допустимая ><эвристика ><может ><первоначально ><достигать ><"нецелевых" ><состояний, ><следуя ><по ><субоптимальному ><пути, ><но ><в ><конечном ><счете ><алгоритм ><найдет ><>оптимальный< ><путь ><ко ><всем ><состояниям, ><лежащим ><на ><пути ><к ><цели. ><Естественно ><спросить, ><существует ><ли ><эвристика, ><которая ><является ><"локально ><допустимой", ><т.е. ><позволяет ><>последовательно< ><находить ><кратчайший ><путь ><к ><каждому ><состоянию, ><которое ><встречается ><в ><про­><цессе ><поиска. ><Это ><свойство ><называется ><монотонностью ><(monotonicity).>

<ОПРЕДЕЛЕНИЕ ><МОНОТОННОСТЬ ><Эвристическая ><функция ><л ><монотонна, ><если>

<1.>< ><Для ><всех ><состояний ><л, ><и ><л><;><, ><где ><л><;>< ><- ><потомок ><л„

><- ><><) ><><><)>