Problem komiwojażera z danymi z macierzy

Question

Cześć :D

Nie mogę wpaść na pomysł jak stworzyć funkcje do obliczania problemu komiwojażera metodą brute force, która będzie pobierala dane z macierzy NxN podanej jako tablica dwuwymiarowa. Wiem jak zrobić algorytm taki dla np. macierzy 3x3 czy 4x4 ale nie mogę wpaść na sposób unwiersalny dla jakiekolwiek podanej przez użytkownika macierzy.

przykładowa macierz:

 0 20 30 31 28 40
30  0 10 14 20 44
40 20  0 10 22 50
41 24 20  0 14 42
38 30 32 24  0 28
50 54 60 52 38  0

Answer 1

Ta macierz nie może być jakakolwiek. Jeśli to macierz sąsiedztwa z kosztami polaczen to musi być kwadratowa i mieć zera na przekątnej.

Zrób zatem walidacje tego co podaje użytkownik i jak poda macierz niekwadratową lub z niezerowymi wartosciami na przekatnej to wyrzuc blad

Comments

Mam już wczytywanie macierzy z pliku jaki wybierze użytkownik. Bardziej mi chodzi jak się zabrać za to żeby potem obliczyć najkrótszą drogę używajać brute force. Nie chcę kodu ale bardziej jakiejś pomocy jak to ugryźć.

Być może źle się wyraziłem w pytaniu. chodzi mi o to jak stworzyc uniwersalną funkcję do obliczenia najkrótszej drogi(tzn ze bede mogl podac jakąkolwiek poprawną macierz i z niej wyliczyć drogę)

Pozdrawiam :D

---

Skoro umiesz zrobić dla 3x3 i 4x4 to jaki masz problem z np 10x10?

---

Chcę stworzyć uniwersalną funkcję obliczania problemu. w jakiś sposób będę musiał zapamiętywać odcinki chyba prawda ?

---

Jeśli to ma być brute force to jedyne co potrzebujesz to generować wszystkie permutacje sciezek pomiedzy dwoma wybranymi punktami i dla każdej z nich policzyć sume.

Generowanie permutacji nie jest banalne, jeśli pisałbyś w jakimś np pythonie to miałbyś to od strzała:

itertools.permutation(range(n))

 

---

Własnie wiem, że w pythonie jest gotowa funkcja do tworzenia permutacji. Chciałbym stworzyć coś takiego w javie ale nie mogę znaleźć niczego ciekawego co by mi pomogło zrozumieć jak to zrobić. Na stackoverflow tez nic nie znalazłem :<

---

Mając np macierz 4x4 i zaczynając od wierzcholka 1 będę miał 6 róznych mozliwosci:

1-2-3-4-1

1-2-4-3-1

1-3-2-4-1

1-3-4-2-1

1-4-3-2-1

1-4-2-3-1

Zastanawia mnie czy byłaby możliwość żeby przekonwertować tabele NxN na listę i wpisać tam wartości (koszty przejsc miedzy miastami) np do listy. Potem może bym wartości z tych list dodal i wybrał tą o najmniejszym koszcie. Myślisz ze to dobry pomysł ?

---

Możesz wygenerować permutacje bez implementacji algorytmu. Sciagnij google guava gdzie masz taką statyczną metode dla dowolnej kolekcji:

static <E> Collection<List<E>>

permutations(Collection<E> elements) Returns a Collection of all the permutations of the specified Collection.

Answer 2

Rozumiem, że w tej macierzy zapisane są odległości. Korzystaj z tego może jak z bazy danych, tzn. niech ta macierz służy tylko do odczytu odległości i nic więcej. Mając macierz np. 3x3, stwórz sobie prostą listę, czy tablicę jednowymiarową z indeksami symbolizujące miasta, a jednocześnie będą to indeksy macierzy sąsiedztwa:

int [] nodes = new int[3];

for(int i = 0; i < nodes.length; i++)
   nodes[i] = i;

Teraz tylko musisz wykorzystać powyższą tablicę do generowania wszystkich kombinacji, scieżek.

Samą odległość mając ścieżkę w postaci np {0, 1, 2, 0} obliczyć jest już bardzo prosto.

int[][] distances = {{0, 5, 10},
                     {5, 0, 4},
                     {10, 4, 0}};

int [] tspProposition = {0, 1, 2, 0};
int distance = 0;

for(int i = 0; i < tspProposition.length -1; i++)
{
    int x = tspProposition[i];
    int y = tspProposition[i + 1];
    distance += distances[x][y];
}
System.out.println(distance);