Problem Komiwojażera - możliwe ścieżki

Question

Hejka,

Mam taki problem, że chciałbym stworzyć jakiś zbiór, w którym przechowywałbym wszystkie możliwe ścieżki z Komiwojażera aby potem znaleźć tą najlepszą, wiem, że istnieją inne lepsze algorytmy ale ja bym chciał wykonać właśnie ten. I np dla pięciu miast była by to ilość 5! czyli 120 różnych ścieżek ale nie mam pojęcia jak mógłbym to zaimplementować w Javie. Prosiłbym o jakieś podpowiedzi, a najlepiej tylko słowne :P

Z góry dzięki :)

Answer 1

A jak aktualnie twoj program wygląda w javie :)?

Comments

Nie wygląda, bo nie mam pojęcia nawet jak zacząć, chciałem zrobić tablicę główną gdzie by się znajdowało 18 miast zapisane w następujący sposób [0, 1, 2, 3, ... 15, 16, 17] i chciałem zrobić aby mi ten program wypisywał wszystkie możliwe niepowtarzające się kombinacje z tej tablicy.

Czyli

1)  [0, 1, 2, 3, ... 15, 16, 17]

2)  [1, 0, 2, 3, ... 15, 16, 17]

itd.

I jeśli dobrze rozumiem matematykę to byłby jakiś algorytm n! ?

---

Nie ma algorytmu n!, n! to złożoność.  Tutaj nikt za Ciebie programu nie napisze, ewentualnie pomoże, doradzi.
Zacznij od napisania samego algorytmu - masz google, masz tyle materiałów, że wystarczy pseudokod.
https://eduinf.waw.pl/inf/alg/001_search/0140.php

Answer 2

Jeżeli miast masz 18 to życia ci nie starczy żeby to policzyć...

Zastanów się nad jakąś metaheurystyką do rozwiązania tego. Najlepiej się nadają algorytmy genetyczne albo algorytmy mrówkowe.