Управляющие системы и машины, №2, 2016, статья 1
DOI: https://doi.org/10.15407/usim.2016.02.005
Тимофієва Н.К. Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач. Управляющие системы и машины. 2016. № 2. C. 5-21, 27 .
УДК 519.816
Тимофеева Надежда Костантиновна, д.т.н., вед.н.с.,
Международный научно-учебный центр информационных технологий и систем НАН и МОН Украины, просп. Глушкова, 40, Киев 03187, Украина, E-mail: tymnad@gmail.com
Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешимых задач
На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных
на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных методом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего соседа и «жадного» алгоритма зависит от структуры входных данных.
Загрузить полный текст в PDF (на украинском и русском).
Ключевые слова: комбинаторная оптимизация, комбинаторная конфигурация, целевая функция, задача коммивояжера, метод структурно-алфавитного поиска, метод ближайшего соседа, «жадный» алгоритм
Поступила 15.03.2016
