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

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

Понятно, что такое состояние не всегда существует (см разд 2.2.3), и в этом случае можно выбрать какое угодно состояние Очевидно, условие (5.4) довольно сильное, поскольку оно сводится к применению критерия ко всем а-срезам нечетких интервалов

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

Здесь используются обозначения из разд 3.2 1 В критериях и берутся строгие неравенства со знаком вместо нестрогих со знаком чтобы обеспечить согласованность с результатами этого раздела Отметим, что если функции принадлежности непрерывны, то эта модификация ничего не меняет.

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

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

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

в виде , где - фиксированный порог.

Замечание Другой вариант обобщения методов поиска на древовидных структурах получается, если видоизменить формулу построения оценочной функции (5 1) Характеристики алгоритмов А и А опираются наряду с другими положениями на предположение об аддитивности оценочных функций Однако при этом используются отнюдь не все свойства операции сложения, а лишь монотонность, ассоциативность и существование нейтрального элемента Таким образом, свойства данных алгоритмов можно сохранить за счет сохранения требуемой алгебраической структуры при построении обобщенной оценочной функции. Так, например алгебраическая структура сохранится, если заменить формулу (5.1) на или в более общем случае, если заменить операцию сложения в формуле (5 1) любой треугольной нормой или конормой (см гл 3) Такие обобщенные алгоритмы А исследованы в работе [20] Они приобретают особый интерес, когда оценочная функция характеризует степень неопределенности, относящуюся к достижимости некоторого состояния в графе поиска, причем правила комбинирования таких степеней неопределенности не обязательно аддитивны (см также статью [15])