Ocena wątku:
  • 0 głosów - średnia: 0
  • 1
  • 2
  • 3
  • 4
  • 5
PORADNIK Jak planować trasę czyli problem komiwojażera w kosmosie
#1
Czy zdarzyło Wam się kiedyś, że chcieliście odwiedzić kilka systemów, które były rozrzucone w różnych częściach galaktyki? Rajd nowym statkiem po inżynierach lub skanowanie najcenniejszych układów do podbicia rangi odkrywcy? W jaki sposób wybrać kolejność, by zrobić to po najbardziej optymalnej (czyli najkrótszej) trasie? W tym poradniku pokażę Wam jak to sobie można policzyć.

W tym celu będziemy potrzebować kilku narzędzi:

Microsoft Excel + dodatek Solver
Niestety musi być oryginalny Excel, zamienniki w postaci OpenOffice lub LibreOffice nie obsługują algorytmów ewolucyjnych w ich odpowiednikach Solvera, a to jest nam niezbędne. Jeśli jeszcze nie macie zainstalowanego dodatku Solver to tutaj znajdziecie opis jak to zrobić link.

Źródło danych o położeniu systemów (wszystkim znany EDSM)

Zestaw makr VBA do obsługi JSON (teoretycznie tą część możemy pominąć, i wartości można wpisywać ręcznie, tylko po co skoro można to zautomatyzować). Link tutaj. Ściągamy plik o nazwie JsonConverter.bas

Do tego wszystkiego potrzebujemy jeszcze listę systemów, które chcemy odwiedzić. Na potrzeby tego poradnika, skorzystamy z listy interesujących gwiazd oddalonych maks 250ly od Sol czyli:

Otwieramy nowy arkusz Excela i kopiujemy naszą listę:


Teraz, to co musimy zrobić to policzyć odległości między tymi wszystkimi gwiazdami. Jak to zrobić? Musimy znać ich współrzędne, a jak już je poznamy możemy obliczyć odległości. Współrzędne są dostępne na EDSM a dostaniemy się do nich za pomocą oficjalnego API. W tym celu w kolumnie B musimy sformułować pytania w formie linka. Dla komórki B2 będzie wyglądało to tak:
Kod:
="https://www.edsm.net/api-v1/system?systemName="&A2&"&showCoordinates=1"


Następnie przeciągamy komórki do końca listy. Teraz w kolumnie C posłużymy się funkcją WEBSERVICE, która pobierze nam dane z EDSM. W tym celu w komórce C2 wpiszemy:
Kod:
=WEBSERVICE(B2)
Powinniśmy uzyskać taki efekt:


I oczywiście przeciągamy komórkę do końca listy.
Ok mamy dane ze współrzędnymi ale teraz przydałoby się wyciągnąć je do osobnej komórki. Niestety standardowa formuła Excela, która służy do wyciągania takich danych uzyskanych funkcją WEBSERVICE czyli FILTERXML, jak sama nazwa wskazuje służy do obsługi danych przesłanych w formacie XML, a my dostaliśmy wynik w JSON. Można oczywiście wyciąć te dane ręcznie, lub nawet jakimś zestawem standardowych formuł, ale po co się męczyć, użyjemy makra VBA. W tym celu odpalamy edytor kombinacją klawiszy ALT+F11. Ukaże nam się takie okienko:


By całość zadziałała musimy zrobić kilka rzeczy:

Włączyć Microsoft Scripting Runtime. W tym celu wybieramy w edytorze menu Tools > References... Pojawi się okienko w którym zaznaczamy odpowiednią opcję:

Teraz musimy załadować ściągnięty wcześniej plik .bas poprzez wybór menu File > Import file...


Teraz na końcu musimy dopisać jeszcze jedną funkcję:
Kod:
Function FILTERJSON(Json As String, ParamArray path()) As Variant
 Dim jsonObj, res As Object
 Set jsonObj = JsonConverter.ParseJson(Json)
 Set res = jsonObj
 Dim i As Integer
 For i = LBound(path) To UBound(path)
   If TypeOf res(path(i)) Is Object  Then
      Set res = res(path(i))
   Else
       FILTERJSON = res(path(i))
       Exit Function
   End If
 Next i
 FILTERJSON = res
End Function


Teraz jesteśmy gotowi do wyciągania danych. Wybieramy komórkę D2 i wpisujemy nowo utworzoną funkcję:
Kod:
=FILTERJSON(C2;"coords";"x")




Przeciągamy w dół by uzupełnić listę, a następnie postępujemy analogicznie w kolumnach E i F zamieniając wartość x odpowiednio na y i z.


Teraz możemy przejść do tworzenia tablicy. W tym celu utworzymy dwa nowe arkusze, które nazwałem Temp i Matrix.
Następnie w pierwszym arkuszu (nazwanym Systems) ukrywamy kolumnę B i C, po czym zaznaczamy zakres danych:


Na wstążce wybieramy Narzędzia główne > Edytowanie > Znajdź i zaznacz > Przejdź do specialnie
Po czym wybieramy tylko widoczne komórki.


Kopiujemy po czym wklejamy jako wartości w arkuszu Temp


Następnie kopiujemy zakres z arkusza Temp po czym przechodzimy do arkusza Matrix gdzie stajemy na komórce B4 i wklejamy zawartość


Następnie ponownie wracamy do Temp, kopiujemy cały zakres, wracamy do Matrix, stajemy na E1 i wklejamy z transpozycją. Powinniśmy uzyskać następujący efekt:


Teraz w arkuszu Matrix musimy:
W kolumnie A musimy ponumerować systemy.
Obliczyć odległości między systemami. W tym celu skorzystamy z klasycznego wzoru na obliczanie odległości między współrzędnymi do którego dodamy jeszcze jeden wymiar. Wybieramy komórkę F5 i wpisujemy:
Kod:
=PIERWIASTEK(($C5-F$2)^2+($D5-F$3)^2+($E5-F$4)^2)


Przeciągamy w dół i do prawej by uzyskać następujący efekt:


Matryca gotowa, teraz trzeba z niej skorzystać.
Tworzymy jeszcze jeden arkusz, który nazwałem Solver
W kolumnie A kopiujemy numerację z Matrix, po czym na końcu dodajemy jeszcze jedną komórkę o wartości 1

W komórce B1 wpisujemy formułę
Kod:
=INDEKS(Matrix!$F$5:$V$21;A1;A2)


W komórce C1 wpisujemy formułę
Kod:
=WYSZUKAJ.PIONOWO(A1;Matrix!$A$5:$B$21;2;0)

Tak to powinno wyglądać:


Przeciągamy komórki w dół ale tylko do przedostatniego wiersza. Ostatni wiersz (w którym wcześniej wstawiliśmy 1 w kolumnie A) pozostaje bez formuł.
W komórce F1 sumujemy zawartość kolumny B za pomocą funkcji:

Kod:
=SUMA(B1:B17)

Całość powinna wyglądać tak:


Przechodzimy do dodatku Solver (znajdziecie go w wstążce Dane)
Ustawiamy parametry:


Kod:
Ustaw cel: $F$1
Na: Min
Przez zmienianie komórek zmiennych: $A$1:$A$17
Podlegających ograniczeniom: $A$1:$A$17 = Wszystkie inne
Wybierz metodę rozwiązywania: Ewolucyjna



Ustawienie ograniczeń wygląda tak:


Dajemy ok, następnie rozwiąż i po kilkudziesięciu sekundach powinniśmy uzyskać efekt:


I gotowe, mamy listę w jakiej kolejności odwiedzać systemy (czytamy od dołu do góry).

Plik z przykładu do ściągnięcia tutaj (zip).
Lub do podglądu online tutaj.
[Obrazek: 218711.png]
Odpowiedz
#2
To jest niesamowite. Naprawdę.
Osobiście korzystam z tego planera https://www.spansh.co.uk/tourist
Podajesz kilka systemów które MUSZĄ być w bazie edsm, zasięg statku i gotowe Wink

Polecam zajrzeć do sekcji https://www.spansh.co.uk/thanks
Jest tam jeden taki...
[Obrazek: 102165.png]
Odpowiedz
#3
Spansh jest ok, tylko nie optymalizuje dobrze tras. Z testów, które zrobiłem to ustawia je w jakiejś kolejności ale dosyć słabym algorytmem.
Wg moich testów trasę:
Ustawia tak, że trzeba zrobić 57kLY a Solver daje tylko 35kLY. To jest jakieś 350 skoków mniej moim eksploracyjnym Aspem.

Samo narzędzie jest dosyć proste, ten "algorytm optymalizacyjny" to dzisiaj chyba element każdego kursu Excel+Solver i jest powszechnie wykorzystywany w logistyce.
Największą rzeźbą było wyciągnięcie danych z EDSM by nie klepać ręcznie współrzędnych systemów. Ogólnie od jakiegoś czasu bawię się API EDSM, jak wyczaruje jeszcze jakieś ciekawostki to będę publikował.
[Obrazek: 218711.png]
Odpowiedz
#4
Jak dla mnie to trochę skomplikowane i nie zawszę muszę lecieć po optymalnej trasie, ale rep się należy. Bardzo dobrze opisany poradnik Smile.
Odpowiedz
#5
A może da się to jakoś zaimplementować do Bigos Managera? @Ryczypior @Kethrax
Odpowiedz
#6
Jako, że jestem z natury leniwy, nie chciało by mi się z każdym razem przechodzić przez te wszystkie procedury. w związku z powyższym pozwoliłem sobie nieco zautomatyzować propozycję @maqinusa. Oto efekt moich działań. Trzeba to, rzecz jasna pobrać i odpalić w Excelu (min. 2013, bo wcześniejsze chyba nie maja funkcji "WEBSERVICE" )  W założeniu wystarczy wkleić, bądź wpisać z palca listę systemów i nacisnąć "PLANUJ". Arkusze "MATRIX" i "SOLVER" powinny wypełnić się automatycznie. Potem wystarczy już tylko uzbroić się w cierpliwość i kliknąć przycisk "SOLVER" w arkuszu o tej samej nazwie i poczekać na wynik. Zapraszam do testowania i szukania moich pomyłek  Smile  Tongue. Nie usuwajcie tylko niczego w wierszu 5 w zakładce "SYSTEMS", bo w tym wierszu  formuły się nie uzupełniają.
Fortuna toczy się kołem. Pod kołem to pojąłem.
A kiedy strzyżesz owieczki, opowiadaj im bajeczki.
[Obrazek: 34417.png]
Odpowiedz
#7
@SEBA312
Bardzo fajne rozwiązanie. Jako powiedzmy zawodowy i leniwy z natury trener Excela wolę dać wędkę niż rybę z nadzieją, że czegoś nauczę i ktoś coś zrobi za mnie, to proszę sprawdziło się Smile

@Mathias Shallowgrave
Implementacja tego algorytmu do innych narzędzi będzie dosyć trudna, o ile nawet niemożliwa. Solver w Excelu to jest dosyć niepozorne ale potężne narzędzie, algorytmy ewolucyjne do dzisiaj są nieodwzorowane chociażby w projektach odpowiedników w Open/Libre Office co już samo w sobie świadczy o poziomie skomplikowania zagadnienia.
[Obrazek: 218711.png]
Odpowiedz


Podobne wątki
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  [PORADNIK] Jolly Roger czyli sprawiedliwość społeczna Yautja 16 8,114 05.04.2020, 21:28 UTC
Ostatni post: TRAWA
  [PORADNIK] Farmienie RAW minerałów [SZOK][ZOBACZ JAK] Pichonek 53 39,015 04.04.2020, 20:59 UTC
Ostatni post: Shavorz
  Dwa monitory w jednym - czyli jak mieć podgląd do zwiniętej ED radekcz 1 847 08.02.2020, 18:22 UTC
Ostatni post: USSER-PL
  [PORADNIK] Jak zdobyć Guardian Module Blueprint Segment Scarlet Yuri 33 22,828 14.01.2020, 17:00 UTC
Ostatni post: SETHDESTRUCTOR
  [PORADNIK] Jak zdobyć Guardian Weapon Blueprint Segment Scarlet Yuri 15 18,339 28.10.2019, 15:56 UTC
Ostatni post: Scarlet Yuri



Użytkownicy przeglądający ten wątek: 1 gości