5.1.3. ЭВРИСТИЧЕСКИЙ ПОИСК С НЕТОЧНЫМИ ОЦЕНКАМИ

Теперь предположим, что в силу неполного знания данных по решаемой задаче стоимости, входящие в оценочную функцию можно определить лишь в виде интервалов. Тогда оценки получаются по правилам интервального анализа (см. гл. 2) Чтобы приспособить алгоритмы типа А или А к случаю оценивания состояний, описываемых в виде интервалов, надо ответить на три вопроса.

Какова стратегия выбора состояния для раскрытия?

Каков критерий останова процедуры?

Каков результат, полученный при таком останове?

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

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

где — операция взятия минимума, расширенная на случай нечетких интервалов по принципу обобщения (см. гл 2). Операция позволяет определить интуитивно достаточный и менее сильный, чем критерий выбора Критерии выбора естественным образом упорядочиваются по их силе:

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

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

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

Пример. Рассмотрим нашу задачу о коммивояжере при неточных значениях стоимостей, е. когда, к примеру, неточно известны протяженности маршрутов между городами. Соответствующие данные приведены на рис. 5.2, а.

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

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

Интервалы приведены на рис. 5.2, б На рис. 5 2, в изображена древовидная структура, раскрываемая с помощью последовательности из пяти критериев выбора состояний — . В остальном берутся те же условия, что и на рис 5 1, в Отметим, что за критерий останова выбирается Алгоритм строит такой же гамильтонов путь, что и ранее (потомок состояния 9), несмотря на неточность Это конечное состояние, безусловно, удовлетворяет критерию по стоимости [8, 16], что получается в результате выполнения расширенной операции над десятью состояниями, пригодными к раскрытию Отметим, что если для прекращения поиска воспользоваться критерием то будут раскрыты девять вершин В случае анализа задачи о коммивояжере выбор по критерию (соответственно очевидно, сводится к выполнению алгоритма с коэффициентами С (соответственно ), т. е. приводится к случаю точных данных В частности, если полученные для каждого из указанных критериев выбора оптимальные решения соответствуют (по меньшей мере) одному и тому же гамильтонову пути, то этот гамильтонов путь оптимален в смысле критерия и строится с помощью алгоритма А, расширенного на случай неточных данных, если только критерий принимается за критерий останова Это и происходит в нашем примере Отметим, что в данном примере решения, оптимального в смысле удовлетворения критерия не существует (дочерние состояния для вершин 16 и 9 — конечные состояния, не сравнимые по критерию