Советы коммивояжера - PullRequest
Новая
       16

Советы коммивояжера

1 голос
/ 27 февраля 2012

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

Любые советы, чтобы начать оптимизацию этого процесса или алгоритмы? Мой текущий алгоритм является базовым алгоритмом возврата.

Мой график удовлетворяет всем типичным условиям в графике TSP (без направленного, симметричного, conex) ...

Спасибо

1 Ответ

3 голосов
/ 27 февраля 2012

Если ваша метрика удовлетворяет неравенству треугольника, я могу предложить вам поискать алгоритм Christofides.У него есть гарантия быть в оптимальном решении.ИМО сложная часть алгоритма Christofides - это идеальное соответствие.Если вы не заботитесь о гарантии, вы можете найти Google TSP Solver.Он использует Ant Colony Optimization для большого маршрута.Если вы хотите действительно быстрого решения и меньшей точности, вы можете найти кривую монстра, например, кривую Гильберта или кривую Мура.

...