Аннотация:
Рассмотрены задачи оптимизации на графах с интервальными параметрами, обоснованы соответствующие экспоненциальные и полиномиальные оценки их вычислительной сложности. Для выделенного подкласса полиномиально разрешимых задач предложены 2 алгоритма: нахождение оптимального решения и нахождение субоптимального решения. Установлены достаточные условия статистической эффективности алгоритма нахождения субоптимального решения. Библ. 23.
Ключевые слова:задачи дискретной оптимизации, задачи с интервальными параметрами, полиномиальная разрешимость задач, приближенные алгоритмы.
УДК:519.626
Поступила в редакцию: 27.02.2007 Исправленный вариант: 04.12.2009
Полный текст:
PDF файл (236 kB)