Оценка качества эвристических алгоритмов, Эмиль Юрьевич Орехов und Юрий Васильевич Орехов

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