Худший случай эвристики ближайшего соседа для симметричных TSP

Question

Я применил эвристику ближайшего соседа для решения симметричных задач TSP. Мне было интересно, существует ли какая-либо связь между решением, найденным эвристикой и оптимальным решением?

Можем ли мы сказать теоретически, насколько выше длина маршрута в худшем случае?

Answer 1

В книге «В погоне за путешествующим продавцом» (Кук) упоминается, что: ближайший сосед никогда не сделает хуже, чем 1 + log(n)/2, а стоимость оптимального (что, в свою очередь, связано с бумагой).

Это отличная книга, описывающая и другие эвристические конструкции.