40 ответов в теме

[Dfire]

Можно ли где-то взять список всех солнечных систем + инфу о том какие из них соединены?

И мне!

ХМЛ какую нибудь....

[Vulpinari]

А что карта в игре уже не катит? она прекрасно составляет маршрут. И его всегда можно подкорректировать.

[Dfire]

А что карта в игре уже не катит? она прекрасно составляет маршрут. И его всегда можно подкорректировать.

хочу прогу для себя нарисовать... по 2-3 точкам что-бы строила возможый маршрут противника...

[Jack van Hellsing]

http://forum.eve-ru....showtopic=19071
дамп базы ЕА, в патче пару джампов добавили, так что системы-переходы там должны быть.

[Sparkling Lord]

А что карта в игре уже не катит? она прекрасно составляет маршрут. И его всегда можно подкорректировать.

А для капитала тоже? Так что не достаточно!

Сообщение отредактировал Sparkling Lord: 07 August 2008 - 22:49

[St!ff]

Вся инфа содержится в датадампе, правда, в сыром виде. те системы и джампы между ними.

ЗЫ а какой в этом всем смысл?

[Sparkling Lord]

В принципе EveMap меня устроил, только интерфейс там не совсем удобный. Через полчаса я его освоил, но ИМХО некоторые простые вещи там отсутствуют.

На вопрос "зачем" ответ прост: планирование. Иногда это важно иногда мешает, но у меня возникла такая необходимость.

[St!ff]

На вопрос "зачем" ответ прост: планирование. Иногда это важно иногда мешает, но у меня возникла такая необходимость.

Это слишком расплывчатая формулировка.
Я же не ради праздного любопытства интересуюсь этим ;)

ЗЫ а какие вещи отсутствуют?

[Pointer]

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

[Фибер]

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

Все это есть в самой еве. Составляешь маршрутв режиме карты (Ф10) путем добавления нужных тебе систем (Адд вей поинт). Переходишь на владку автопилот. Там есть кнопка оптимизировать маршрут.

[Pointer]

Все это есть в самой еве. Составляешь маршрутв режиме карты (Ф10) путем добавления нужных тебе систем (Адд вей поинт). Переходишь на владку автопилот. Там есть кнопка оптимизировать маршрут.

Действительно есть и работает, спасибо!

[C. N.]

Только это не задача коммивояжёра, если посмотреть со строгой точки зрения. Через одну и ту же систему автопилот может проходить несколько раз; он ищет именно кратчайший путь, который будет проходить через все вейпоинты. Да и если опять же быть строгим, то задача коммивояжёра требует, чтобы коммивояжёр вернулся в ту систему, из которой начал. Да и алгоритм там, 99,99 % даю, — просто алгоритм Дейкстры (судя по скорости работы и предупреждению в туториале).
А вообще да, Optimize Path — хорошая штука, если вейпоинтов хотя бы больше трёх. С одним-двумя чаще всего автопилот сразу же выбирает оптимальный путь.

[ubersheva]

Угу, пробовал я как-то облететь регион с помощью optimize path. добавил вейпойнты по всем системам с помощью "my assets" на карте, вышло десятка 2-3. Ткнул кнопку optimize и сидел ждал минут 15. Собственно ева сама предупреждение показывает - для количества вейпойнтов больше 12 оптимизация может занять огромное количество времени. Еще бы, задача комивояжера не имеет решения кроме полного рекурсивного перебора, насколько я помню.
Так что я забил на это и облетаю вручную - на глаз разбил регион на несколько несвязанных частей и каждую облетаю отдельно, выставляя set destination.

[Dfire]

...Еще бы, задача комивояжера не имеет решения кроме полного рекурсивного перебора, насколько я помню....

Имеет решение, причем оптимальное,и без полного рек. перебора. =)

[Shaeto]

видел решение для карты метро, стеклянная пластинка с нанесенной схемой, на станциях контактные площадки, прикасаешься пальцами к двум любым станциям загорается оптимальный маршрут.

вопрос - как сделано ? ни одного транзистора не пострадало насколько я помню.

решение в курсе физики за восьмой класс.

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

[DarkPhoenix]

Мы на системной анализе ее проходили...

Обошлись без рекурсивного перебора :о ну, там есть похожий метод, да, но полным рекурсивным перебором его врядли можно назвать.

[RLeonis]

Задача комвояжера является NP-полной, её не получится решить за разумное время (если граф большой), вообщем решается приближенными методами.

P.S. Чуть не забыл : "Так-то!"

Сообщение отредактировал RLeonis: 10 July 2009 - 21:53

[C. N.]

Абсолютно точные решения за t времени обычно никому не нужны, если можно получить решение, которое хуже идеального на 10 %, за t ∕ 100 хотя бы. Хотя бы метод ветвей и границ или те же генетические алгоритмы в руки и поехали. Полным перебором её будут решать разве что на «уроках информатики» и для доказательства нереальной крутости только что выдуманного метода её решения.

2 Shaeto
Начнём с того, что это не задача коммивояжёра, а задача нахождения кратчайшего пути между двумя точками (кстати, в Еве тоже как раз эта задача). А закончим тем, что я тоже могу станции соединить проводками с лампочками, а на самих станциях поставить ёмкостные реле, замыкающие станции с источником тока. И естественно ток будет течь по маршруту наименьшего сопротивления, зажигая лампочки или что там на своём пути. И да, даже в этом случае она решается всё же с помощью good old Dijkstra’s algorithm (но довольно быстро, вива ля скорость света).

Сообщение отредактировал C. N.: 11 July 2009 - 11:57

[Shaeto]

не утверждал в своем посте что нахождение пути по наименьшему сопротивлению и есть решение стартопиковской задачи, но как зарядка для ума вполне, и, как одно из решений подзадачи тоже. готовых алгоритмов много но вдруг кто-то задумавшись прозреет и мы увидим новый алгоритм имени "Форум-Юзер-Вулгарис" ?

[RLeonis]

Абсолютно точные решения за t времени обычно никому не нужны, если можно получить решение, которое хуже идеального на 10 %, за t ∕ 100 хотя бы. Хотя бы метод ветвей и границ или те же генетические алгоритмы в руки и поехали.

ну ваще есть быстрые алгоритмы - "с ошибкой не более чем в 2а раза" +)) А если граф большой (а он большой) и помимо обычных данные есть еще "дополнительные условия" (сс систем, avoid list) то это будет ооочень долго, тем более генетическим алгоритмом, если требуется приближение к "оптимальному". Ну собственно про это и говорят комрады )))