Существует важное различие между точными алгоритмами и эвристиками .Точный алгоритм гарантированно найдет точное оптимальное решение.Эвристики нет, но она предназначена для быстрой работы.
DP - точный алгоритм, по крайней мере, как он обычно используется.Есть алгоритмы DP для TSP.Таким образом, эти алгоритмы решат проблему точно .
ТСП не может быть решена точно с использованием жадных методов, поэтому любой жадный метод является эвристическим.Следовательно, по определению DP всегда найдет лучшее (или не худшее) возможное решение, чем жадная эвристическая воля, для любого случая TSP.
Обратите внимание, однако, что DP не является доминирующим подходом для решения TSP.Существует много других алгоритмов, которые намного эффективнее.В некоторых оригинальных документах по TSP использовался DP, и он часто формулируется как иллюстративный пример, но это не тот способ, которым TSP обычно решаются на практике.
Чтобы исправить что-то в OP:
Я знаю, что с точки зрения оптимального решения для решения задач TSP используются жадные алгоритмы, но он становится более сложным и занимает экспоненциальное время, когда число вершин (т.е. городов) очень велико.
Greedy эвристика иногда используются для решения TSP.(У них есть имена, такие как ближайший сосед, самая дешевая вставка и т. Д.) По мере увеличения числа вершин время выполнения этих эвристик также увеличивается, но оно не увеличивается в геометрической прогрессии.Большинство этих эвристик имеют время выполнения с полиномиальной сложностью низкого порядка, например O (n ^ 2).
С другой стороны, поскольку TSP является NP-сложным, все известные точные алгоритмы будет иметь сложность в худшем случае, которая будет экспоненциальной по количеству вершин.(Обратите внимание, что я говорю сложность наихудшего случая - фактическое время выполнения может быть вполне разумным для многих случаев, но только экспоненциальным в худшем случае.)