Уважаемые знатоки, недавно передо мной встала задача, необходимо написать программу которая бы решала задачу коммивояжера методом Эйлера. Упоминания об этом методе я нашел разве что в "Программирование в алгоритмах" С. Окулова, но и там метод описан очень сухо и непонятно. 

Дан пяти-вершинный неориентированный граф, где каждая вершина соединена с каждой. Известны веса ребер. 



Не мог бы кто-нибудь описать алгоритм решения задачи методом Эйлера?

Заранее очень благодарен.   

Интересно, первый раз слышу про алгоритм Эйлера (хотя не факт, что Эйлер - действительно автор этого алгоритма  ).

Ну а описание в Окулове мне показалось нормальным. Находим минимальное остовное дерево (т.е. набор из n-1 рёбер наименьшего суммарного веса, который связывает все вершины). Потом там написано, что строим эйлеров цикл в этом остовном дереве, а затем из эйлерова цикла удаляем повторы вершин, и останется результат. Ну этот шаг можно представить проще: просто запускаем обход в глубину на остовном дереве, и каждый раз, когда мы приходим в какую-то новую вершину, добавляем её в ответ.

По Окулову определенная роль отводится неравенству треугольников. Вот основной момент мне не понятный. 

Наличие у графа этого свойства (что d[i][j] + d[j][k] >= d[i][k]) говорит о том, что алгоритм Эйлера даст "достаточно хороший" ответ, т.е. не более чем в 2 раза дороже, чем оптимальный гамильтонов путь (на то он и приближенный алгоритм).

Откуда это следует?

С одной стороны, стоимость минимального каркаса < стоимости оптимального гамильтонова пути (действительно, гамильтонов путь - это цикл; удаляя из него любое ребро, мы будем получать каркас, который никак не может быть дешевле минимального каркаса).

С другой стороны, какой ответ находит алгоритм Эйлера - он берёт из каркаса каждое ребро дважды, а потом некоторые рёбра удаляет, заменяя их "срезками" (скажем, в дереве-цепочке 1-2-3 можно оставить рёбра 1-2, 2-3, 3-1, т.е. рёбра 3-2 и 2-1 заменились одной "срезкой" 3-1). Из неравенства треугольников следует, что после "срезок" стоимость пути никак не может увеличиться. Таким образом, стоимость пути-результата алгоритма Эйлера не выше, чем 2 * стоимость минимального каркаса.

Итого по двум этим неравенствам получаем, что алгоритм Эйлера найдёт путь не более чем в 2 раза худший, чем оптимальный.

maxdiver, благодарю, очень толково и доходчиво. 
70% программы уже реализовано. 
Еще раз большое спасибо. 
Вопрос закрыт