1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 5(54)'2006
  5. Визначення найкоротших гамільтонових циклів в неорієнтованому графі

Визначення найкоротших гамільтонових циклів в неорієнтованому графі

С.В. Лістровий, В.А. Пудов, В.В. Калачова
Анотації на мовах:

Розглядається актуальне завдання комівояжера, що полягає в знаходженні в звичайному зваженому графі гамільтонова шляху найменшого, де вага циклу визначається як сума ваг вхідних в нього ребер. Пропонується новий алгоритм визначення найкоротших гамільтонових циклів, який не гарантує знаходження точного рішення, але імовірно є швидшим, ніж існуючу. Виводиться відповідність найкоротшого гамільтонова циклу в самому графі гамільтонову циклу в структурі клік графа. Доводиться ефективність розвалу структури до одного циклу на основі процедури А.