SLY_G Dec 6 2016 at 16:27

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

6 min

20K

Popular science

Translation

+33

Comments 13

febb Dec 6 2016 at 19:00

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

safinaskar Dec 6 2016 at 22:06

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

miksoft Dec 7 2016 at 09:14

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

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

arheops Dec 7 2016 at 11:50

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

Deosis Dec 7 2016 at 12:17

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

miksoft Dec 7 2016 at 14:16

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

arheops Dec 7 2016 at 14:45

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

miksoft Dec 7 2016 at 15:57

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

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

arheops Dec 7 2016 at 16:07

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

miksoft Dec 7 2016 at 16:13

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

arheops Dec 8 2016 at 01:30

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

miksoft Dec 8 2016 at 14:40

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

arheops Dec 8 2016 at 14:46

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

Show the best of all time