Некий купец задумал хитрый план, с помощью которого хочет увеличить свою прибыль. Купец подумал, что он смог бы продать больше товара, если бы смог посетить $%n$% городов по самому короткому пути (затратив на дорогу наименьшее кол-во времени), так чтобы побывать в каждом городе лишь раз и вернутся в точку отправления. Опишите самый быстрый алгоритм, по которому купец бы смог выполнить свой коварный план.

задан 6 Июн '15 1:32

изменен 6 Июн '15 12:58

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

А какие данные имеются насчёт расстояний между городами? Есть ли тут отличие от обычной задачи коммивояжёра?

(6 Июн '15 1:53) falcao

@falcao Нет, это я изучаю сейчас http://en.wikipedia.org/wiki/Travelling_salesman_problem вот хотел бы узнать чего-нибудь нового ))

(6 Июн '15 1:56) void_pointer

А что тут можно сказать нового? Это во многом открытая проблема. Ясно, что самого быстрого алгоритма никто не знает. Есть медленные алгоритмы, дающие оптимальное решение, и есть приближённые, дающие решение быстро, но с некоторым коэффициентом. Скажем, легко получить решение за время $%O(n^3)$%, стоимость которого не больше $%2C$%, где $%C$% -- оптимальное значение. Можно снизить $%2$% до $%3/2$%.

(6 Июн '15 2:15) falcao

@falcao А что вы можете сказать по подову эвристических и приближенных алгоритмов? С какой погрешностью в зависимости от кол-во городов они решают данную проблемму? Допустим, мы снизим кол-во городов до 10000. Возьмем за начальную точку любой город наугад из данных 10000. Построим MST, применив, скажем, алгоритм Прима. Далее пройдемся по этому дереву, помечая вершины согласно времени их посещения в порядке (preorder). Помеченные вершины обеденяем с помощью цикла Гамильтона. Это и есть тривиальное решение проблеммы для взятой нами точки отправления. В чем плюсы и минусы данного метода?

(6 Июн '15 2:29) void_pointer

@void_pointer: я примерно этот способ и имел в виду, только брал за основу алгоритм Краскала. Строим поддерево минимального веса, потом обходим его, и спрямляем пути. При грубой оценке как раз и получается 2C, хотя можно её улучшить. На евклидовой плоскости это достаточно хорошо работает, потому что если возникнет самопересекающаяся ломаная, то её длину можно далее уменьшать. В итоге получается что-то ещё более близкое к оптимальному значению.

(6 Июн '15 2:40) falcao

@falcao Данный метод не оптимальный, потому что, возможно, найдется вершина (точка отправления), из которой мы получим дерево с суммарным расстоянием меньше, чем из изначально проверенной вершиной? А что если запустить данный алгоритм из каждой вершинны, используя для ускорения кластеры и паралельное программирование. Затем результат каждого потока запишем в массив, отсортируем и найдем тот, который дал лучший результат? Разве это будет не оптимальным решением проблеммы?

(6 Июн '15 3:05) void_pointer

@void_pointer: никто и не утверждает, что рассматриваемый метод оптимален -- говорится лишь то, что он ошибается в "константное" число раз -- в отличие, скажем, от "жадного" алгоритма, который может ошибиться не в 2 раза, а в 100. Запуск алгоритма по отдельности для каждой вершины -- это известная вещь. Я не помню, чьим именем он называется. Там даже достаточно "жадный" алгоритм применять -- получается константное отличие от оптимального решения. То, что оптимальное математическое решение на данный момент никому не известно -- это как бы общепринято (а то сразу получилось бы P=NP).

(6 Июн '15 3:20) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×145
×39

задан
6 Июн '15 1:32

показан
236 раз

обновлен
6 Июн '15 3:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru