Путешествующий продавец: Как можно предварительно обработать график?

Question

Скажем, мы хотим вычислить TSP для данного полного графа G с V вершинами и E ребрами (под полным я подразумеваю: каждая вершина связана с любой другой вершиной).

---

Я постараюсь снова задать вопрос. Надеюсь, в этот раз я все сделаю правильно. Моя цель проста:
Для этого полного графа G, как отфильтровать некоторые ребра, которых, вероятно, не будет в графе?

Answer 1

Реализация Лин-Кернигана Келдом Хельсгауном измеряет качество ребра e как [минимальная стоимость 1 дерева, включая e] - [минимальная стоимость 1 дерева] (чем ниже, тем лучше),См. Раздел 4.1.

Answer 2

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