Задача коммивояжера

Добрый день, уважаемые разрабочтики!

Решил я полетать по куче станций, составил список из 16 пунктов, нажал оптимизировать. Вижу предупреждение. Думаю ладно, подожду, тут же всего ничего. Прошло 5 минут, 10 минут. Игра не откликается. Перезапустил. Вижу что маршрут немного оптимизировался. Снизил до 14 точек. Да, мгновенно всё нашлось. И откуда взялось такое ограничение? Может я баг словил, что пришлось ждать более 10 минут. Хотя слышал истории, что можно и день прождать.

Ладно, может я что-то не знаю. Решил нагуглить. Взял первую попавшуюся библиотеку на питоне. Вбил ТЫСЯЧУ точек и… за 6 секунд нашелся маршрут!!!

Как так выходит? Объясните пожалуйста!

P.S.: та самая библиотека - https://github.com/dmishin/tsp-solver
P.P.S.: на самом деле у компа не одно ядро
P.P.P.S.: а ещё лучше нагрузить GPU

1 Like

Просто есть трюизм, что идиосинкразия клиента к оптимизации маршрута - это прямая адикция от вашей конгруэнтности. Советую провести не две оптимизации маршрута для чистоты эксперимента, а минимум 3-4 по правилу трех С. Если это не решит проблему, то создайте официальную петицию в поддержку. К сожалению, фанфест закончился и ссп уже не ответят на Ваш вопрос. Ждите следующий. А пока можно собрать команду единомышленников в одну корпу. Куда вступать?

И еще, азработчики могут ответить только на англоязычной ветке этого форума, а могут и не ответить (только прочитать), что вероятнее всего.

Попробуй еще спросить на иврукоме, может быть повезет и ответит опытный игрок.

Именно что не знаешь.

В питоьей библиотеке первое же слово в описании “Suboptimal”. Это значит что она ищет короткое, но не гарантированно самое лучшее решение. Т.е. даже для маршрута из 3-4 точек можно подобрать такие значения чтобы расстояний, чтобы алгоритм библиотеки сломался.

А ЕВА ищет самый оптимальный маршрут (чтобы не было “ко-ко-ко, мне пришлось сделать на 2 прыжка больше, дизлайк, отписка”). Ищет полным перебором.

А вообще у задачи поиса пути в еве сложность (n-1)! / 2 . Проще говоря добавляя 15 точку в путь ты увеличиваешь время поиска пути в 14 раз. И игра об этом тебя честно предупреждает.

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

Также если вы интересуетесь торговлей вот тут описана ещё одна проблема с которой вы столкнётесь Торговый интерфейс. Торговля

Это всё известно мне. Такие задачи не решают перебором, есть куча эвристик, одну из которых и привел в пример. Лучше пусть будет хоть какая-то оптимизация маршрута, чем никакой.

На самом деле было бы логичнее всего скажем до 10-11 искать решать полным перебором, а если больше - то предупреждать пользователя и искать при помощи быстрого алгоритма. Но “вам так не будэ” (с) От ССР мы такого не дождемся.

1 Like

Да, я это и имел ввиду. На самом деле это изичная задачка, ничего не стоит. Не знаю что не так с CCP.
:C

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.