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

Здравствуйте!

В настоящий момент, пока я пишу этот пост, производится расчёт оптимального маршрута по 20 точкам внутри одного региона - наверно мне придется завершить процесс в менеджере задач.

Я не верю, что эту процедуру невозможно оптимизировать и сделать её работу быстрее, ну хотя бы в 100 раз.

В общем камень брошен, надеюсь "с гор сойдёт лавина" алгоритмов, или хотя бы какое-то конструктивное обсуждение проблемы. Я программист, кто-то математик или может быть даже транспортный логист - в CCP, я надеюсь, тоже есть компетентные специалисты, так что вместе мы смоли бы решить эту задачу.

Вообще-то, карта EVE глючит и зависает, при том что сама игра ещё продолжает работать - работы по оптимизации не мало...

Представляю первый вариант решения задачи, всё оказалось очень просто:
EVE-AutoPilot.RAR

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

Редактор скриптов X3:R/TC/AP:
X3TC - External Script Editor
Новые скриптовые команды. Справочник от 16.01.2009.

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

Например:

В каждой системе массив с подсказками. Например список ближайших систем.

Регион "Verge Vendor*", созвездие "Kiartanne*", система "Jufvitte*".
0: Ячейка массива с информацией о системе.
1..X: Ячейки массива с укзателем на массив соседней системы.

Знак : - обозначает начало константы/переменной, или массива.
Знак ^ - обозначает константу/переменную указатель на объект.

Jufvitte*: (0:(0:("Jufvitte*"), 1:(Kiartanne^), 2:(Verge_Vendor^), 3:(+0.5), ...), 1:(Ouelletta^), 2:(Ansalle^), 3:(Scheenins^), 4:(Amygnon^))
Ouelletta*: (0:(0:("Ouelletta*"), 1:(Woenckee^), 2:(Verge_Vendor^), 3:(+0.4), ...), 1:(Jufvitte^), 2:(Melmaniel^), 3:(Loes^))
Ansalle*: (0:(0:("Ansalle*"), 1:(Kiartanne^), 2:(Verge_Vendor^), 3:(+0.6), ...), 1:(Jufvitte^), 2:(Gisleres^))
Scheenins*: (0:(0:("Scheenins*"), 1:(Kiartanne^), 2:(Verge_Vendor^), 3:(+0.5), ...), 1:(Vay^), 2:(Jufvitte^))
Amygnon*: (0:(0:("Amygnon*"), 1:(Kiartanne^), 2:(Verge_Vendor^), 3:(+0.6), ...), 1:(Jufvitte^))

Записи в списках могут быть структурированными, то есть не только идентификаторы систем, но и куча другой полезной информации. Структура массива может отличаться, в зависмости от применяемых приемов обработки, на вкус программиста (пока что для начала так). В результате мы имеем потенциальную "сетку" с неограниченной дальностью прыжков - дальность может быть бесконечной.
...
А-а-а, блин, весь этот теоретический трёп без конкретных данных ни чего не значит - нужно сначала список систем создать, что бы начать моделировать алгоритм. то что я тут ниже хотел выкинуть, это вооще полная фигня. Не буду мозги пудрить, ни себе, ни людям, надо сперва составить базу данных в заданном формате, хотя бы одного региона (Verge_Vendor). Может быть у кого нибудь есть массивчик готовый?

Тема почищена от некоструктива, оффтопа и флуда. Напоминаю о соблюдении правил официального форума

Он мне для колдовства очень нужен. В голове не хватает оперативки, придётся делать классическим методом. Кстати, если бы получить массив всей галактики в формате представленном ниже, то можно было бы работать сразу по всей галактике.

Вот я сам только что состряпал массив региона - для вычислений пока нужны только 1, 2 и 3 столбцы, остальные пока предлагаю не трогать. Число "0" указывает на системы соседнего региона.

VergeVendor.csv
1;4;+0.9;Adallier;Anwyns;Verge Vendor;Alentene
2;0,0,12;+0.6;Aidart;Anwyns;Verge Vendor;Stacmon,Avaux,Cistuvaert
3;42,4,43;+0.9;Alenia;Anwyns;Verge Vendor;Tourier,Alentene,Vaere
4;36,3,29,12,43,1;+0.9;Alentene;Anwyns;Verge Vendor;Scolluzer,Alenia,Merolles,Cistuvaert,Vaere,Adallier
5;0,9,39;+0.4;Amoderia;Aideron;Verge Vendor;Pemene,Arraron,Stou
6;24;+0.6;Amygnon;Kiartanne;Verge Vendor;Jufvitte
7;27,11;+0.8;Annelle;Ancbeu;Verge Vendor;Masalle,Chesiette
8;24,2;+0.6;Ansalle;Kiartanne;Verge Vendor;Jufvitte,Gisleres
9;0,5,10,39;+0.5;Arraron;Aideron;Verge Vendor;Attyn,Amoderia,Chantrousse,Stou
10;0,9,32,41;+0.6;Chantrousse;Aideron;Verge Vendor;Ourapheh,Arraron,Osmomonne,Tierijev
11;7,35;+0.6;Chesiette;Ancbeu;Verge Vendor;Annelle,Reblier
12;19,4,2;+1.0;Cistuvaert;Anwyns;Verge Vendor;Eletta,Alentene,Aidart
13;43;+0.9;Channace;Anwyns;Verge Vendor;Eletta
14;19;+0.9;Clacille;Obray;Verge Vendor;Eletta
15;38,27;+0.7;Claulenne;Ancbeu;Verge Vendor;Sortet,Masalle
16;26;+0.8;Clellinon;Obray;Verge Vendor;Luse
17;28;+0.2;Costolle;Woenckee;Verge Vendor;Melmaniel,Muetralle
18;26,34;+0.8;Ekuenbiron;Obray;Verge Vendor;Luse,Raneilles
19;12,26,44,14;+0.9;Eletta;Obray;Verge Vendor;Cistuvaert,Luse,Vay,Clacille
20;21,4;+0.9;Ellmay;Kiartanne;Verge Vendor;Gisleres,Theruesse
21;36,8,20;+0.8;Gisleres;Kiartanne;Verge Vendor;Scolluzer,Ansalle,Ellmay
22;30,34,23;+0.4;Hevrice;Obray;Verge Vendor;Muetralle,Raneilles,Jovainnon
23;0,22;+0.3;Jovainnon;Obray;Verge Vendor;Aeschee,Hevrice
24;33,8,37,6;+0.5;Jufvitte;Kiartanne;Verge Vendor;Ouelletta,Ansalle,Scheenins,Amygnon
25;0,33;+0.3;Loes;Woenckee;Verge Vendor;Agoze,Ouelletta
26;19,18,44,16;+0.9;Luse;Obray;Verge Vendor;Eletta,Ekuenbiron,Vay,Clellinon
27;15,7;+0.8;Masalle;Ancbeu;Verge Vendor;Claulenne,Annelle
28;31,33,17;+0.3;Melmaniel;Woenckee;Verge Vendor;Murethand,Ouelletta,Costolle
29;0,42,4;+0.9;Merolles;Anwyns;Verge Vendor;Tar,Tourier,Alentene
30;22,17;+0.2;Muetralle;Woenckee;Verge Vendor;Hevrice,Costolle
31;0,0,28;+0.3;Murethand;Woenckee;Verge Vendor;Mesybier,Indregulle,Melmaniel
32;36,10,41;+0.8;Osmomonne;Aideron;Verge Vendor;Scolluzer,Chantrousse,Tierijev
33;24,28,25;+0.4;Ouelletta;Woenckee;Verge Vendor;Jufvitte,Melmaniel,Loes
34;18,44,22;+0.6;Raneilles;Obray;Verge Vendor;Ekuenbiron,Vay,Hevrice
35;0,11;+0.4;Reblier;Ancbeu;Verge Vendor;6-CZ49,Chesiette
36;4,21,32,38;+0.5;Scolluzer;Ancbeu;Verge Vendor;Alentene,Gisleres,Osmomonne,Sortet
37;44,24;+0.8;Scheenins;Kiartanne;Verge Vendor;Vay,Jufvitte
38;36,15;+0.8;Sortet;Ancbeu;Verge Vendor;Scolluzer,Claulenne
39;5,34;+0.5;Stou;Aideron;Verge Vendor;Amoderia,Arraron
40;20;+0.9;Theruesse;Kiartanne;Verge Vendor;Ellmay
41;0,0,10,32;+0.8;Tierijev;Aideron;Verge Vendor;Tannolen,Derririntel,Chantrousse,Osmomonne
42;0,0,3,29,13;+0.9;Tourier;Anwyns;Verge Vendor;Yulai,Diaderi,Alenia,Merolles,Channace
43;3,4;+0.8;Vaere;Anwyns;Verge Vendor;Alenia,Alentene
44;37,19,26,34;+0.8;Vay;Obray;Verge Vendor;Scheenins,Eletta,Luse,Raneilles

Исправил ошибки в массиве...

Самые обычные настройки, и галочек стоит только на "черный список" и "0.5-1.0", но и это можно убрать - не принципиально, так как меня интересовал именно расчёт пути по региону VergeVendor, для планового скана секторов на аномалии. Задяча элементарна, но игра зависает и ни в какую не хочет считать путь.

Список прост уже есть, пожалуйста, выберай 12-44 сисем и вперёд, старт желательно в Jufvitte*, и только в хайсеке...

Посмотрел "алгоритм". По-моему это обычный жадный алгоритм. Где оценка скорости работы (мне кажется, О(n!))?

Готов еще раз посмотреть, если будет выложено в более удобоваримом виде. Рарник где-то там - неудобно. Гугл-докс?

Да-да. И к счастью для меня "Яндекс.Диск" умеет сам раскрывать рар-архив, а то я понятия не имею, чем такое открывать. И даже браузер понял кодировку.

drive.google.com Что за ВКонтакте...
Ок, знаю, даже регистрировался.
В виде программы. И считать количество итераций. И перебрать все возможные варианты входных данных, чтобы честно посчитать количество операций. Я может быть не смогу придумать контрпример, но возможно такой существует.

Если программу писать не хочется - давайте алгоритм, я напишу программу.

Нет, Divide&Conquer. Старая, давно.