Еще раз о решении задачи коммивояжера

Предложена процедура построения оптимизированных по длине гамильтоновых циклов во взвешенных графах методом поэтапного выделения и наращивания линейных участков путей минимизированной длины. Процедура позволяет обрабатывать как неориентированные, так и ориентированные графы, т.е. решать симметричные и несимметричные задачи коммивояжера.
На каждом этапе процедуры (начиная с первого этапа) обрабатываются подграфы исходного графа задачи, сложность которых уменьшается при переходах от этапа к этапу. Выделение и наращивание линейных участков путей являются простейшими операциями по обнаружению вершин степени 2 с возможным удалением некоторых ребер (дуг) подграфа.
Эти характеристики процедуры (поэтапное уменьшение сложности обрабатываемых подграфов и исключительная простота операций выделения и наращивания линейных участков путей) позволяют надеяться на высокую эффективность применения процедуры для решения задач коммивояжера большой размерности.