Несложно о сложности. Примеры алгоритмов/Задачи/tsp-greedy-bad

Материал из DISCOPAL
Перейти к: навигация, поиск

Докажите, что жадный алгоритм в задаче коммивояжера, т.е. алгоритм стартующий с некоторой вершины и пытающийся добавлять наиболее дешевые ребра к еще непосещенным вершинам, не гарантирует нахождение оптимального решения.