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

Версия 17:37, 20 декабря 2012

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