# Задача коммивояжера **URL:** \ **Category:** Технические вопросы\ **Created:** [April 14, 2018, 9:53pm UTC](https://forums.eveonline.com/t/topic/69738 "2018-04-14T21:53:11Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Fox\_Fantastic](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/fox_fantastic/32/511081_2.png) [@Fox\_Fantastic](https://forums.eveonline.com/u/Fox_Fantastic)\ **Post date:** [April 14, 2018, 9:53pm UTC](https://forums.eveonline.com/t/topic/69738/1 "2018-04-14T21:53:11Z")
Добрый день, уважаемые разрабочтики! Решил я полетать по куче станций, составил список из 16 пунктов, нажал оптимизировать. Вижу предупреждение. Думаю ладно, подожду, тут же всего ничего. Прошло 5 минут, 10 минут. Игра не откликается. Перезапустил. Вижу что маршрут немного оптимизировался. Снизил до 14 точек. Да, мгновенно всё нашлось. И откуда взялось такое ограничение? Может я баг словил, что пришлось ждать более 10 минут. Хотя слышал истории, что можно и день прождать. Ладно, может я что-то не знаю. Решил нагуглить. Взял первую попавшуюся библиотеку на питоне. Вбил ТЫСЯЧУ точек и… за 6 секунд нашелся маршрут!!! Как так выходит? Объясните пожалуйста! P.S.: та самая библиотека - [https://github.com/dmishin/tsp-solver](https://github.com/dmishin/tsp-solver) P.P.S.: на самом деле у компа не одно ядро P.P.P.S.: а ещё лучше нагрузить GPU ---
**Author:** ![Old\_Miner\_Ecilopp](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/old_miner_ecilopp/32/67175_2.png) [@Old\_Miner\_Ecilopp](https://forums.eveonline.com/u/Old_Miner_Ecilopp)\ **Post date:** [April 15, 2018, 4:14am UTC](https://forums.eveonline.com/t/topic/69738/2 "2018-04-15T04:14:05Z")
Просто есть трюизм, что идиосинкразия клиента к оптимизации маршрута - это прямая адикция от вашей конгруэнтности. Советую провести не две оптимизации маршрута для чистоты эксперимента, а минимум 3-4 по правилу трех С. Если это не решит проблему, то создайте официальную петицию в поддержку. К сожалению, фанфест закончился и ссп уже не ответят на Ваш вопрос. Ждите следующий. А пока можно собрать команду единомышленников в одну корпу. Куда вступать? ---
**Author:** ![Old\_Miner\_Ecilopp](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/old_miner_ecilopp/32/67175_2.png) [@Old\_Miner\_Ecilopp](https://forums.eveonline.com/u/Old_Miner_Ecilopp)\ **Post date:** [April 15, 2018, 7:10am UTC](https://forums.eveonline.com/t/topic/69738/3 "2018-04-15T07:10:57Z")
И еще, азработчики могут ответить только на англоязычной ветке этого форума, а могут и не ответить (только прочитать), что вероятнее всего. Попробуй еще спросить на иврукоме, может быть повезет и ответит опытный игрок. ---
**Author:** ![Phrynohyas\_Tig-Rah](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/phrynohyas_tig-rah/32/420039_2.png) [@Phrynohyas\_Tig-Rah](https://forums.eveonline.com/u/Phrynohyas_Tig-Rah)\ **Post date:** [April 15, 2018, 11:18am UTC](https://forums.eveonline.com/t/topic/69738/4 "2018-04-15T11:18:47Z")
> [@Fox\_Fantastic](#): > > Ладно, может я что-то не знаю. Именно что не знаешь. В питоьей библиотеке первое же слово в описании “Suboptimal”. Это значит что она ищет короткое, но не гарантированно самое лучшее решение. Т.е. даже для маршрута из 3-4 точек можно подобрать такие значения чтобы расстояний, чтобы алгоритм библиотеки сломался. А ЕВА ищет самый оптимальный маршрут (чтобы не было “ко-ко-ко, мне пришлось сделать на 2 прыжка больше, дизлайк, отписка”). Ищет полным перебором. А вообще у задачи поиса пути в еве сложность (n-1)! / 2 . Проще говоря добавляя 15 точку в путь ты увеличиваешь время поиска пути в 14 раз. И игра об этом тебя честно предупреждает. ---
**Author:** ![Vlad\_Veter](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/vlad_veter/32/224871_2.png) [@Vlad\_Veter](https://forums.eveonline.com/u/Vlad_Veter)\ **Post date:** [April 15, 2018, 5:33pm UTC](https://forums.eveonline.com/t/topic/69738/5 "2018-04-15T17:33:51Z")
Больше десяти точек и не прокладываю именно по этой причине. Но вот ещё что неплохо бы донести до разработчиков, прокладку маршрута проводить через клавиатурный модификатор, а не парится с контекстным меню. Также если вы интересуетесь торговлей вот тут описана ещё одна проблема с которой вы столкнётесь [Торговый интерфейс. Торговля](https://forums.eveonline.com/t/topic/62604) ---
**Author:** ![Fox\_Fantastic](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/fox_fantastic/32/511081_2.png) [@Fox\_Fantastic](https://forums.eveonline.com/u/Fox_Fantastic)\ **Post date:** [April 16, 2018, 4:19pm UTC](https://forums.eveonline.com/t/topic/69738/6 "2018-04-16T16:19:15Z")
Это всё известно мне. Такие задачи не решают перебором, есть куча эвристик, одну из которых и привел в пример. Лучше пусть будет хоть какая-то оптимизация маршрута, чем никакой. ---
**Author:** ![Phrynohyas\_Tig-Rah](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/phrynohyas_tig-rah/32/420039_2.png) [@Phrynohyas\_Tig-Rah](https://forums.eveonline.com/u/Phrynohyas_Tig-Rah)\ **Post date:** [April 16, 2018, 5:04pm UTC](https://forums.eveonline.com/t/topic/69738/7 "2018-04-16T17:04:30Z")
На самом деле было бы логичнее всего скажем до 10-11 искать решать полным перебором, а если больше - то предупреждать пользователя и искать при помощи быстрого алгоритма. Но “вам так не будэ” (с) От ССР мы такого не дождемся. ---
**Author:** ![Fox\_Fantastic](https://sea1.discourse-cdn.com/eveonline/user_avatar/forums.eveonline.com/fox_fantastic/32/511081_2.png) [@Fox\_Fantastic](https://forums.eveonline.com/u/Fox_Fantastic)\ **Post date:** [April 17, 2018, 9:43pm UTC](https://forums.eveonline.com/t/topic/69738/8 "2018-04-17T21:43:04Z")
Да, я это и имел ввиду. На самом деле это изичная задачка, ничего не стоит. Не знаю что не так с CCP. :C ---
**Author:** ![system](https://global.discourse-cdn.com/eveonline/original/3X/4/1/41ec4921cbaca7a6f9ea556e7cc20018461eae5e.png) [@system](https://forums.eveonline.com/u/system)\ **Post date:** [July 16, 2018, 9:43pm UTC](https://forums.eveonline.com/t/topic/69738/9 "2018-07-16T21:43:10Z")
Closed on July 16, 2018, 9:43pm UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.