• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem komiwojażera z danymi z macierzy

Aruba Cloud - Virtual Private Server VPS
0 głosów
1,665 wizyt
pytanie zadane 20 października 2018 w Java przez Kamyyylo Początkujący (460 p.)
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

2 odpowiedzi

0 głosów
odpowiedź 20 października 2018 przez RafalS VIP (122,820 p.)
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
komentarz 20 października 2018 przez Kamyyylo Początkujący (460 p.)
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
komentarz 20 października 2018 przez RafalS VIP (122,820 p.)
Skoro umiesz zrobić dla 3x3 i 4x4 to jaki masz problem z np 10x10?
komentarz 20 października 2018 przez Kamyyylo Początkujący (460 p.)
Chcę stworzyć uniwersalną funkcję obliczania problemu. w jakiś sposób będę musiał zapamiętywać odcinki chyba prawda ?
komentarz 20 października 2018 przez RafalS VIP (122,820 p.)

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))

 

komentarz 20 października 2018 przez Kamyyylo Początkujący (460 p.)
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 :<
komentarz 20 października 2018 przez Kamyyylo Początkujący (460 p.)
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ł ?
komentarz 21 października 2018 przez RafalS VIP (122,820 p.)
edycja 21 października 2018 przez RafalS

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.

0 głosów
odpowiedź 21 października 2018 przez mbabane Szeryf (79,260 p.)

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);

Podobne pytania

0 głosów
2 odpowiedzi 458 wizyt
pytanie zadane 19 stycznia 2021 w Java przez MarKor Nowicjusz (180 p.)
0 głosów
1 odpowiedź 702 wizyt
pytanie zadane 3 stycznia 2020 w C i C++ przez Programmingc100 Bywalec (2,620 p.)
0 głosów
1 odpowiedź 815 wizyt

93,329 zapytań

142,323 odpowiedzi

322,400 komentarzy

62,662 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...