Управляющие системы и машины, №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
