These forums have been archived and are now read-only.

The new forums are live and can be found at https://forums.eveonline.com/

Идеи и предложения

 
  • Topic is locked indefinitely.
Previous page123Next page
 

Поиск решения для оптимизации маршрутов более 10 пунктов...

First post
Author
Previous Topic Next Topic
Amelita Robiros
Republic Military School
Minmatar Republic
#21 - 2013-09-18 18:23:46 UTC  |  Edited by: CCP Vesna Prishla
BT-Volodya wrote:
У меня всё гораздо быстрее. Сделай массив на 20 точек маршрута, как показано в примере, и я тебе своими мозгами, без всяких программ максимум за 1 час (ну, возможно больше) составлю кротчайший маршрут.

Нарушение правил общения не форуме — CCP Vesna Prishla

У меня есть серьезный недостаток - я терпеть не могу идиотов.

Elegbara
White Wolf Enterprises
#22 - 2013-09-18 21:03:05 UTC
BT-Volodya wrote:
[quote=Elegbara]Алгоритм на пальцах разжеван в тексте, уж там-то всё элементарно. Сначала спрашиваем у всех пар-точек длину связей, в прыжках (на 6 точек их всего 21), затем сортируем полученные массивы как в колонке №3
Для n узлов у нас n(n+1)/2 пар. Для 6 их всего 21, для 20 их будет 210. Дальше сортировка. Откуда у нас изначально взяты эти массивы? Каков размер каждого массива? Умножаем n(n+1)/2 на время сортировки такого массива (еще вопрос в том, сколько места в памяти такие массивы будут занимать - возможно мы не сможем их хранить и их придется создавать динамически - это может занять даже больше времени, чем сортировка). Наконец осталось проверить, что выбранный маршрут действительно является оптимальным и улучшить его нельзя.

Короче. Дайте алгоритм составления такого массива и я попробую что-то сваять. Компилить ничего не собираюсь - буду писать на питоне. Исходники выложу на гитхабе.

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#23 - 2013-09-19 11:38:17 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
(1) Для n узлов у нас n(n+1)/2 пар. Для 6 их всего 21, для 20 их будет 210. Дальше сортировка. (2)Откуда у нас изначально взяты эти массивы? (3)Каков размер каждого массива? Умножаем n(n+1)/2 на время сортировки такого массива (еще вопрос в том, сколько места в памяти такие массивы будут занимать - возможно мы не сможем их хранить и их придется создавать динамически - это может занять даже больше времени, чем сортировка). (4)Наконец осталось проверить, что выбранный маршрут действительно является оптимальным и улучшить его нельзя.

(5)Короче. Дайте алгоритм составления такого массива и я попробую что-то сваять. Компилить ничего не собираюсь - буду писать на питоне. Исходники выложу на гитхабе.
(1) - Не проверял про 210, а так всё правильно - это очень мало для современного CPU. Smile
(2) - Эти массивы должна сгенерировать игра, перебрав все(210) пары - игра же умеет рисовать линию из пункта "A" в пункт "B", с учетом требований безопасности.
(3) - Размер массива на 20 пар-точек примерно такой (Pascal/Delphi): array of Word [00h..D1h,00h..02h] = 1260 байт. Извени конечно, но беспокоиться о времени сортировки такого ничтожного массива просто смешно.
(4) - Проскочим 20 циклов по массиву из 210 значений, составляя 20 вариантов из самых коротких пар-прыжков какие только есть в массиве, это самые первые значения для каждой пары. Выбери из 20 вариантов самый короткий маршрут и будь счастлив, что всего за 1 секунду получил такой замечательный результа��. Ну а если тебе хочется просчитать этот массив более подробно, то так и быть, пускай будет галочка в настройках автопилота "полный анализ маршрута", для особо "пунктуальных" пилотов...
(5) - Я боюсь произносить название языка, на котором я напишу эту процедуру - CMD.EXE Lol... Массив, для региона "Verge Vendor", я составлю и отсортирую вручную, используя Excel. Я заложу 20 точек маршрута, из системы "Jufvitte*"... На всё на это, я надеюсь, у меня уйдет около 48 часов работы (у меня дела в EVE, и не только)...

P.S.
Про шум из курятника лучше промолчу...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#24 - 2013-09-19 13:34:24 UTC
Когда я спросил про размер массива, меня интересовало не столько место в памяти, сколько количество записей.
1260 байт можно сортировать сколько угодно, меня интересует оценка времени работы для n точек.

На всякий случай - время не в секундах, а в формулах оценки сложности.
Еще на всякий случай - пример. Для n точек количество различных пар равно O(n^2).

Дайте нормальный алгоритм, пусть даже в псевдокоде, я постараюсь его понять. Тот алгоритм, который приведен ранее, оперирует каким-то загадочным массивом, я до сих пор не пойму, откуда такой массив берется (кроме как пишется руками на бумажке).

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#25 - 2013-09-20 07:40:50 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
Когда я спросил про размер массива, меня интересовало не столько место в памяти, сколько количество записей.
1260 байт можно сортировать сколько угодно, меня интересует оценка времени работы для n точек.

На всякий случай - время не в секундах, а в формулах оценки сложности.
Еще на всякий случай - пример. Для n точек количество различных пар равно O(n^2).

Дайте нормальный алгоритм, пусть даже в псевдокоде, я постараюсь его понять. Тот алгоритм, который приведен ранее, оперирует каким-то загадочным массивом, я до сих пор не пойму, откуда такой массив берется (кроме как пишется руками на бумажке).
Давай так, я изложу этот алгоритм в скрипте для X3:AP - там есть карта с секторами, уменьшенное подобие EVE, есть функции вычисления расстояния между парами, множество возможностей по передаче параметров, а так же есть автопилот и всё необходимое для рабочего примера...

И вот ещё что, массивы могут выглядедь как угодно, это не имеет ни какого значения. Так же как везде, у массива действует общее правило - указатель(идентификатор) на область памяти, и структура смещения с шагом под размер записей в массиве. И в моём массиве нет ни чего сверх нового и нестандартного - я же с программистом беседую, так? Blink

Кстати, напиши какими языками ты владеешь? Если знашь Pascal/Delphi, Assembler, CMD, AutoHotKey, X3:R/TC/AP - я бы мог попробовать набросать приблизительный код, только без отладки и проверок на ошибки, так как нечем компилировать. Но сначала я напишу рабочий скрипт для X3:R/TC/AP...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#26 - 2013-09-20 13:57:55 UTC
Что такое X3:AP?

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

Знаю С, перл, джаву, джаваскрит, в последнее время питон потихоньку. Еще баш, сед, авк, но это наверно поможет мало. Что-то могу понять в хаскелле.

Ассемблер это круто конечно, но "со словарем" могу и в нем разобраться.

Но мне бы хватило псевдокода.

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#27 - 2013-09-21 01:03:39 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
Что такое X3:AP?
"X3: Albion Prelude"

Вот редактор скриптов:
X3TC - External Script Editor
Новые скриптовые команды. Справочник от 16.01.2009.
Если осмотреться на форуме, то не трудно понять, что это и с чем его едят...

Вот сам скрипт, работает бысро, без ошибок - ставь игру, копируй скрипт в папку "...\X3TC\scripts\*.xml", или "...\X3AP\addon\scripts\*.xml".
http://www.elite-games.ru/conference/viewtopic.php?p=2985962#2985962

Данный скрипт просчитывает только 1 уровень оптимизации, при этом он значительно сокращает маршрут, менее чем за 1 секунду - я запускал более 20 точек маршрута, с более чем 230 прыжков растояние уменьшилось до 91 прыжка. В настоящее время, EVE даже и не мечтает о таких результатах. Если немного поколдовать над "умной глубиной" оптимизации, то можно значительно повысить сжатие маршрута, за счёт незначительного увеличения времени работы процедуры - за 10 секунд можно было бы просчитать глубину оптимизации примерно 10-15 уровней, при количестве более 20 точек маршрута. Можно сделать глубину оптимизации настраиваемой, со значениями от 1 до, например 10, или 20, возможно вообще без ограничения, на усмотрение пилота. Если кому-то интересно посмотреть на более впечатляющие результаты, за несколько секунд, то я могу улучшить свой скрипт до полной функциональности. (Одно не понятно, кто будет копать для меня руду?)

P.S.
Из перечисленных языков, писал только на Javascript (в HTML) - сразу говорю, это не вариант.

Модераторам:
Пожалуйста не убивайте, просто по другому не получается ни как...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#28 - 2013-09-21 07:29:24 UTC
Джаваскрипт это всегда вариант. Особенно если не привязываться к HTML.

Но уж псевдокодом-то можно?

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#29 - 2013-09-21 09:24:44 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
Джаваскрипт это всегда вариант. Особенно если не привязываться к HTML.

Но уж псевдокодом-то можно?
Э-э-э, всевдокодом, чего-чего?

Поставь игру, увидешь своими глазами хоть, за что сражаюсь... Blink
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#30 - 2013-09-21 12:26:23 UTC
BT-Volodya wrote:
Э-э-э, всевдокодом, чего-чего?
псевдокод (на русской вики написана какая-то чушь)

BT-Volodya wrote:
Поставь игру, увидешь своими глазами хоть, за что сражаюсь...
Хм, купить что ли... на хамбл бандл оно сейчас в продаже, заявлена совместимость с линуксом.

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#31 - 2013-09-21 13:31:57 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
BT-Volodya wrote:
Э-э-э, всевдокодом, чего-чего?
псевдокод (на русской вики написана какая-то чушь)

BT-Volodya wrote:
Поставь игру, увидешь своими глазами хоть, за что сражаюсь...
Хм, купить что ли... на хамбл бандл оно сейчас в продаже, заявлена совместимость с линуксом.
Ты в какой стране живешь? Возьми пробник на 30 дней, если есть, сохраненку скину, что бы не терять время на открытие карты. Хотя что я несу - карту можно открыть несколькими строчками в скрипте... Lol

Короче на паскале если что набросаю, только без компиляции...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#32 - 2013-09-21 17:32:58 UTC
Ок, жду хотя бы паскаля.

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#33 - 2013-09-22 13:35:39 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
Ок, жду хотя бы паскаля.
Не жди, ставь игру и смотри что я предлагаю. Или бери скрипт-редактор и справочник комманд, и извлекай алгоритм оптимизации. Или не мороч мне голову, что ты якобы сильно заинтересован в решении этой проблемы - у меня есть дела, их ни кто за меня не сделает. Я доказал, всем способным это увидеть, что смогу решить проблему оптимизации маршрута, в домашних условиях "на коленке". Теперь пришло время поработать программистам CCP. Алгоритм есть, рабочий скрипт есть, результаты есть, программисты есть, время есть, зарплата есть, проблема тоже есть - препятствий для решения проблемы оптимизации маршрутов в EVE online, нет!

Модераторам:
Проблема решена, тема закрыта. Если программистам CCP потебуется моя помощь - я всегда на связи...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#34 - 2013-09-22 19:52:08 UTC
BT-Volodya wrote:
Я доказал, всем способным это увидеть, что смогу решить проблему оптимизации маршрута, в домашних условиях "на коленке".
Я не способен увидеть решение задачи коммивояжера в высказывании вида "пусть у меня есть все подготовленные данные, тогда я могу сразу указать всем на оптимальный маршрут"

Ставить еще одну игру ко всем тем, в которые у меня нет времени играть, я не собираюсь.

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#35 - 2013-09-22 20:28:37 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
BT-Volodya wrote:
Я доказал, всем способным это увидеть, что смогу решить проблему оптимизации маршрута, в домашних условиях "на коленке".
Я не способен увидеть решение задачи коммивояжера в высказывании вида "пусть у меня есть все подготовленные данные, тогда я могу сразу указать всем на оптимальный маршрут"

Ставить еще одну игру ко всем тем, в которые у меня нет времени играть, я не собираюсь.
Не играй, есть скрипт-редактор и справочник - алгоритм на любом языке остается алгоритмом...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#36 - 2013-09-22 21:49:32 UTC
BT-Volodya wrote:
алгоритм на любом языке остается алгоритмом...
Там какой-то адский xml, это оно?

Open your eyes. And awaken.
BT-Volodya
TOPMO3A
#37 - 2013-09-22 22:12:43 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
Там какой-то адский xml, это оно?
Да! Lol Редактор скриптов его видит так же как игра.

Вот текстовая копия скрипта - в принципе редактор не обязателен...
Человек это - "Космическая пчёлка"...
Elegbara
White Wolf Enterprises
#38 - 2013-09-23 05:07:09 UTC  |  Edited by: Elegbara
vk.com wrote:
This document is available only to its owner.

И заранее - я когда пытался xml открывать, там какие-то значочки вместо русских букв. Можно сразу по-английски или в юникоде? (я конечно могу сам сконвертить, если что)

Open your eyes. And awaken.
Demonos 555
Lunam-Corp
#39 - 2013-09-23 08:00:48 UTC  |  Edited by: Demonos 555
По мучал я маршруты, и понял, что проблема не 20 и более точек маршрута, а в наличии 12 и более СМЕЖНЫХ точек в маршруте.


А что алгоритм? Их два всего:
1. Определение расстояния между точками маршрута. (Оно у нас не известно изначально)
2. Решение стандартной транспортной задачи (или оптимизированной транспортной задачи), где расстояния между пунктами это количество прыжков (из алгоритма 1)


Я бы одно решение предложил: галочку "игнорировать смежные точки". На сколько я понимаю, система при расчете думает, что смежные точки нужны (что нужно пусть строить так, что бы через эти точки проходить при движении из А в Б, Б в В и т.п.). А если мне такая смежная точка нафиг не нужна, то зачем системе напрягаться?
BT-Volodya
TOPMO3A
#40 - 2013-09-23 12:39:46 UTC  |  Edited by: BT-Volodya
Elegbara wrote:
vk.com wrote:
This document is available only to its owner.

И заранее - я когда пытался xml открывать, там какие-то значочки вместо русских букв. Можно сразу по-английски или в юникоде? (я конечно могу сам сконвертить, если что)
Извиняюсь, уже исправил настройку доступа. Если это в "процедуре" SCRIPT.System, то там есть те же константы на Английском - замени Русские кракозябры на транслит, если очень надо, всеравно это только визуализация для менюшек в игре...
Demonos 555 wrote:
По мучал я маршруты, и понял, что проблема не 20 и более точек маршрута, а в наличии 12 и более СМЕЖНЫХ точек в маршруте.
И кому они нужны, эти смежные точки? Это явно не правильно, с точки зрения планирования маршрута. Если нам надо избежать опасные сектора, то эту задачу надо решать при вычислении расстояния между парой-точек, а не в основном алгоритме. Если мы хотим заскакивать во все системы по пути - так они и так все по пути. Если нам надо выяснить самый короткий маршрут, то это не означает, что надо проверять все варианты по порядку. В общем у меня к разоаботчикам очень много "расстрельных" вопросов...

P.S.
Ни кто бы и не подумал, пока не начнут копаться во всём этом дерьме...
Человек это - "Космическая пчёлка"...
Previous page123Next page