Специалисты по информатике идут нехожеными дорогами

[febb]

Интересно, когда-нибудь художественный фильм Travelling Salesman 2012 (Задача коммивояжёра) переведут на русский язык? Очень хочется посмотреть и узнать в чем там дело :-)

[safinaskar]

Мне кажется, нет. Я купил их фильмец, посмотрел. Недавно они прислали мыло, в котором написали, что у них всё плохо и срочно нужны положительные оценки на imdb. Так что вряд ли когда-нибудь переведут. Достань субтитры, если есть и гугл транслейтом переведи.

[miksoft]

Самый короткий путь через все 13 509 городов США, население которых превышает 500 человек (по данным 1998 года)

Вот интересно, эта величина сильно меняется по мере развития дорожной сети?

[arheops]

Данная задача НЕ учитывает дорожную сеть. Только табличное расстояние между городами.

[Deosis]

Если в городе с населением 499 человек родится ребенок и этот город понадобится добавить в маршрут, то насколько изменится кратчайший путь?

[miksoft]

Увеличится на величину не более удвоенного пути от этого города до ближайшего к нему, полагаю.

[arheops]

Вам прийдется пересчитать ВСЕ. Может уменьшится, может увеличится. Врядли на ваш вопрос можно дать правильный ответ(доказать теорему).

[miksoft]

Может уменьшится

Уменьшиться не может, имхо.

[arheops]

Может. Решение то не оптимальное, а «не более чем на 40% больше оптимального». Может получится, что эта точка приводит алгоритм к более оптимальному решению.

[miksoft]

Вопрос, от которого идет обсуждение, был «насколько изменится кратчайший путь?»
Кратчайший уменьшиться не может.

[arheops]

Путь «через 13 509 городов США» не является кратчайшим. Он именно получен по алгоритму, который находит суб-оптимальный маршрут.

[miksoft]

А что тогда означают слова «Самый короткий»?

[arheops]

Никто не знает «самый короткий» путь в задаче комивояжора с такими данными. Даже суперкомпьютер не справится. В данном случае был использован алгоритм Кристофидеса, который дает приближенное значение «не более чем на 50% длинее».