13.4.1. Эвристические оценки и алгоритм поиска

13.4.1. Эвристические оценки и алгоритм поиска

Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И/ИЛИ-дерева, не руководствуясь при этом какими-либо эвристиками. Для сложных задач подобные процедуры весьма не эффективны из-за большой комбинаторной сложности пространства поиска. В связи с этим возникает необходимость в эвристическом управлении поиском, направленном на уменьшение комбинаторной сложности за счет исключения бесполезных альтернатив. Управление эвристиками, излагаемое в настоящем разделе, будет основано на численных эвристических оценках "трудности" задач, входящих в состав И/ИЛИ-графа. Программу, которую мы составим, можно рассматривать как обобщение программы поиска с предпочтением в пространстве состояний гл. 12.

Начнем с того, что сформулируем критерий оптимальности, основанный на стоимостях дуг И/ИЛИ-графа. Во-первых, мы расширим наше представление И/ИЛИ-графов, дополнив его стоимостями дуг. Например, И/ИЛИ-граф рис. 13.4 можно представить следующими предложениями:

а ---> или : [b/1, с/3].

b ---> и : [d/1, e/1].

с ---> и : [f/2, g/1].

e ---> или : [h/6].

f ---> или : [h/2, i/3].

цель( d). цель( g). цель( h).

Стоимость решающего дерева мы определим как сумму стоимостей его дуг. Цель оптимизации - найти решающее дерево минимальной стоимости. Как и раньше, иллюстрацией служит рис. 13.4.

Будет полезным определить стоимость вершины И/ИЛИ-графа как стоимость оптимального решающего дерева для этой вершины. Стоимость вершины, определенная таким образом, соответствует "трудности" соответствующей задачи.

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

Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция h для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата — корня этого дерева?

Рис. 13.9. Получение оценки H трудности задач И/ИЛИ-графа.

Обозначим через H(В) оценку трудности вершины В. Для самой верхней вершины текущего дерева поиска H(В) просто совпадает с h(В). С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение h, поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

 

где с(В, Вi) — стоимость дуги, ведущей из В в Вi. Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу В, нам нужно решить только одну из ее задач-преемников. Трудность И-вершины В можно приближенно оценить так:

 

Будем называть H-оценку внутренней вершины "возвращенной" (backed-up) оценкой.

Более практичной с точки зрения использования в нашей программе поиска является другая величина F, которую можно определить в терминах H следующим образом. Пусть В1 — вершина-предшественник вершины В в дереве поиска, причем стоимость дуги, ведущей из В1 в В, равна с(В1, В), тогда положим

F( B) = с( В1, В) + H( В)

Пусть В1 — родительская вершина вершины В, а В1В2, … — ее дочерние вершины, тогда, в соответствии с определениями F и H, имеем

 

,  если В — ИЛИ-вершина

 

,  если В — И-вершина

Хотя стартовая вершина А и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить h равным 0 для всех вершин И/ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна  F(A).

На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И/ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины — стартовой вершины  а, далее дерево постепенно "растет" до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд "мгновенных снимков", сделанных в процессе роста дерева поиска. Для простоты мы предположим, что h = 0 для всех вершин. Числа, приписанные вершинам на рис. 13.10 — это их F-оценки (разумеется, по мере накопления информации в процессе поиска они изменяются). Ниже даются некоторые пояснительные замечания к рис. 13.10.

После распространения поиска из первоначального дерева (снимок А) получается дерево В. Вершина а — это ИЛИ-вершина, поэтому мы имеем два решающих дерева-кандидата: b и с. Поскольку F( b) = 1 < 3 = F( c), для продолжения поиска выбирается альтернатива b. Насколько далеко может зайти процесс роста поддерева b? Этот процесс может продолжаться до тех пор, пока не произойдет одно из двух событий:

(1) F-оценка вершины b станет больше, чем  F-оценка ее конкурента с, или

(2) обнаружится, что найдено решающее дерево.

В связи с этим, начиная просмотр поддерева-кандидата b, мы устанавливаем верхнюю границу для F( b): F( b) ? 3 = F( c). Сначала порождаются преемники d и e вершины b (снимок С),после чего F-оценка b возрастает до 3. Так как это значение не превосходит верхнюю границу, рост дерева-кандидата с корнем в b продолжается. Вершина d оказывается целевой вершиной, а после распространения поиска из вершины e на один шаг получаем дерево, показанное на снимке D. В этот момент выясняется, что F( b) = 9 > 3,  и рост дерева b прекращается. В результате процесс поиска не успевает "осознать", что h — это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу  с.  Поскольку в этот момент F( b) = 9, устанавливается верхняя граница для  F( c),  равная 9. Дерево-кандидат с корнем  с   наращивается (с учетом установленного ограничения) до тех пор, пока не возникает ситуация, показанная на снимке  E.  Теперь процесс поиска обнаруживает, что найдено решающее дерево (включающее в себя целевые вершины h и g), на чем поиск заканчивается. Заметьте, что в качестве результата процесс поиска выдает наиболее дешевое из двух возможных решающих деревьев, а именно решающее дерево рис. 13.4(с).

Рис. 13.10. Трассировка процесса поиска с предпочтением в И/ИЛИ-графе (h = 0) при решении задачи рис. 13.4. 

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Алгоритм поиска дубликатов

Из книги автора

Алгоритм поиска дубликатов В переводе с английского shingle означает «гонт». Яснее не стало? Гонт – это кровельный материал, а точнее, небольшие дощечки с пазами и выступами, которые собираются в один лист. Применительно к поисковым системам шинглы – это алгоритм для поиска


Стремление к точности оценки

Из книги автора

Стремление к точности оценки Разработчики тоже попадают в ловушку точности. Они знают, что должны выдать оценку системы, и часто думают, что их оценка должна быть точной. Ничего подобного!Во-первых, даже с идеальной информацией в ваших оценках будет наблюдаться огромный


10 Оценки

Из книги автора

10 Оценки Оценка – одно из самых простых, но при этом самых рискованных задач, с которыми сталкиваются профессиональные разработчики. От оценки напрямую зависит коммерческая ценность проекта. От нее зависят наши репутации. Неверные оценки становятся причиной наших


Алгоритм поиска прав

Из книги автора

Алгоритм поиска прав Теперь, когда мы определили все типы прав и различные способы, которыми пользователь может их получить, рассмотрим алгоритм поиска и попытаемся понять, как фактически происходит предоставление прав.Поиск прав всегда осуществляется в строго


8. Проблема оценки эффективности рекламных и PR-кампаний

Из книги автора

8. Проблема оценки эффективности рекламных и PR-кампаний Один из наиболее проблемных вопросов продвижения интернет-ресурсов – оценка эффективности рекламных кампаний, а также отдельных рекламных технологий. Как правило, единственным критерием эффективности ошибочно


4.1. Методы внутренней и внешней оценки производственного процесса

Из книги автора

4.1. Методы внутренней и внешней оценки производственного процесса Внутренние оценки нацелены на выявление приоритетных направлений усовершенствования производственного процесса организации. Группы внутренней оценки руководствуются СММ для выявления таких


7.5. Применение профессиональной оценки

Из книги автора

7.5. Применение профессиональной оценки Чтобы обеспечить полный набор принципов, применяемых к самым различным ситуациям, в некоторых ключевых практиках изначально заложена возможность гибкой трактовки. В ключевых практиках используются такие размытые фразы, как


9.7. Экспертные оценки

Из книги автора

9.7. Экспертные оценки Группа ключевых процессов для уровня 3: определенный уровеньЦель группы ключевых процессов «Экспертные оценки» заключается в эффективном устранении дефектов в промежуточных программных продуктах на ранних стадиях разработки. Важным следствием


Экспертные оценки

Из книги автора

Экспертные оценки Цель 1. Планирование работ по проведению экспертных оценок.Цель 2. Выявление и устранение дефектов в промежуточных программных


Критерии оценки программиста

Из книги автора

Критерии оценки программиста Увлеченность новыми технологиями. 0 – не желаете узнавать ничего нового, 5 – регулярно читаете статьи о современных средствах разработки, 10 – регулярно применяете все новинки в своей области программирования.Общение с себе подобными. 0 – Вы


5.3.2.3 Определение критерия оценки

Из книги автора

5.3.2.3 Определение критерия оценки Для определения качества продукции результаты оценивания различных характеристик должны быть подытожены. Оценщик должен подготовить для этого процедуры, используя, например, таблицы решений или средние взвешенные. Процедура обычно


Эвристические анализаторы кода

Из книги автора

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


8. Компьютерные игры и плохие оценки

Из книги автора

8. Компьютерные игры и плохие оценки Игровая приставка (или карманная игровая консоль) — один из самых распространенных подарков для детей. Речь идет о рынке с миллиардным оборотом, где всемирно известные фирмы, такие как Sony, Nintendo или Microsoft, буквально сражаются за


Вопросы для оценки наличия интернет-зависимости

Из книги автора

Вопросы для оценки наличия интернет-зависимости 1. Как часто вам бывает трудно закончить сеанс пользования Интернетом, если вы вышли в Сеть?2. Как часто вы продолжаете пользоваться Интернетом, хотя, собственно говоря, хотели закончить сеанс?3. Как часто вам говорят другие