Документы о проблеме коммивояжера (TSP)

Question

Я ищу относительно (после 2000) новые статьи о TSP. Все бумаги, которые я нашел, были довольно трудными и нуждались в высоком уровне математические навыки. Я ищу документы, которые легко читать для тех, кто имеет простые математические знания колледжа и хорошо Знание программирования на Java и C реализация TSP с этими языками).

Любые советы будут высоко оценены.

---

(редактировать)

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

Я нашел несколько работ, основанных на методах Лин-Кернигана, которые казались нормальными ...

Answer 1

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

У Дэвида С. Джонсона и соавторов есть несколько статей, которые мне нравятся: http://www2.research.att.com/~dsj/papers.html, в частности, № 1 и № 3 в разделе «Задача коммивояжера»..

Answer 2

Вот что вы можете сделать:

1) Изучите главу 11 «Управляемый локальный поиск» и главу 12 «Итеративный локальный поиск из Справочника по метаэвристике» (2010), каждый из которых имеет раздел, описывающий, как GLS и ILS предназначены для TSP. И ILS, и GLS интересны и довольно просты в реализации.

2) Проверьте этот документ: «Управляемый локальный поиск и его применение к проблеме коммивояжера»

3) Найдите код Ruby для этих алгоритмов здесь и перепишите его на Java

Answer 3

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

http://www2.isye.gatech.edu/~jjb/mow/mow.html