3.13. КРИТЕРИИ КАЧЕСТВА РАБОТЫ МЕТОДОВ ПЕРЕБОРА

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

Один из таких критериев называется целенаправленностью. Целенаправленность Р перебора позволяет узнать, в какой мере перебор идет в направлении цели, а не ведется по нежелательным направлениям. Она просто определяется как

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

Значения величин целенаправленности для некоторых примеров перебора, использованных в настоящей главе, приведены в табл. 3.1.

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

длинным. (Как правило, увеличение длины пути решения приводит к тому, что Т увеличивается еще быстрее.)

Таблица 3.1 (см. скан) Целенаправленность и фактор эффективного ветвления для различных примеров

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

и

Величина В не может быть выписана как явная функция от и Т, но на рис. 3.10 представлена диаграмма, показывающая зависимость В от 7 при различных значениях Величина В, близкая к единице, соответствует перебору, который весьма точно направлен прямо к цели и очень мало ответвляется на другие направления. С другой стороны, кустообразный граф перебора характеризуется высоким значением В.

Значения В для наших примеров перебора были вычислены с помощью диаграммы, изображенной на рис. 3.10, и приведены вместе со значениями целенаправленности в табл. 3.1. Целенаправленность связана с В и длиной пути формулой На рис. 3.11 показано изменение целенаправленности с длиной пути при различных значениях В.

В той мере, в какой В мало зависит от длины пути, эта величина может быть использована для предсказания того, сколько вершин было быпостроено при переборе той или иной длины. Например, из табл. 3.1 видно, что при для игры в восемь получается величина В, равная 1,08. Попытаемся

(кликните для просмотра скана)

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

Рис. 3.11. Зависимость Р от для различных значений Р

Из рис. 3.10 мы видим, что тридцатишаговая задача, при условии что фактор ветвления остается неизменным, потребовала бы построения около 120 вершин. (Эта оценка, между прочим, - не противоречит экспериментальным результатам Дорана и Мичи (1966), охватывающим больше примеров задач такого типа.)