[PORADNIK] Jak planować trasę czyli problem komiwojażera w kosmosie

[maqinus]

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:

Spoiler

Kod:

Sol
LAWD 26
53 Aquarii
LAWD 13
HIP 40977
18 Camelopardalis
Jackson's Lighthouse
Beta Sculptoris
Rukbat
HIP 34707
HIP 23692
Lalande 25224
c2 Centauri
p Puppis
HIP 57814
HIP 69328
25 Iota Ophiuchi

Otwieramy nowy arkusz Excela i kopiujemy naszą listę:

Spoiler

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"

Spoiler

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:

Spoiler

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:

Spoiler

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ę:

Spoiler

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

Spoiler

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

Spoiler

Teraz jesteśmy gotowi do wyciągania danych. Wybieramy komórkę D2 i wpisujemy nowo utworzoną funkcję:

Kod:

=FILTERJSON(C2;"coords";"x")

Spoiler

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.

Spoiler

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:

Spoiler

Na wstążce wybieramy Narzędzia główne > Edytowanie > Znajdź i zaznacz > Przejdź do specialnie

Po czym wybieramy tylko widoczne komórki.

Spoiler

Kopiujemy po czym wklejamy jako wartości w arkuszu Temp

Spoiler

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

Spoiler

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:

Spoiler

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)

Spoiler

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

Spoiler

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ć:

Spoiler

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:

Spoiler

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

Spoiler

Ustawienie ograniczeń wygląda tak:

Spoiler

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

Spoiler

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.