Рассматривается актуальная задача коммивояжера, состоящая в нахождении в обыкновенном взвешенном графе гамильтонова пути наименьшего, где вес цикла определяется как сумма весов, входящих в него ребер. Предлагается новый алгоритм определения кратчайших гамильтоновых циклов, который не гарантирует нахождения точного решения, но предположительно является более быстрым, чем существующие. Выводится соответствие кратчайшего гамильтонова цикла в самом графе гамильтонову циклу в структуре клик графа. Доказывается эффективность развала структуры до одного цикла на основе процедуры А.
Бібліографічний опис для цитування:
Листровой С.В.
Определение кратчайших гамильтоновых циклов в неориентированном графе / С.В. Листровой,
В.А. Пудов,
В.В. Калачева
// Системи обробки інформації. – 2006. – № 5(54). – С. 155-160.
ENG
