• 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

VPS Starter Arubacloud
0 głosów
1,410 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,300 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 372 wizyt
pytanie zadane 19 stycznia 2021 w Java przez MarKor Nowicjusz (180 p.)
0 głosów
1 odpowiedź 635 wizyt
pytanie zadane 3 stycznia 2020 w C i C++ przez Programmingc100 Bywalec (2,620 p.)
0 głosów
1 odpowiedź 625 wizyt

92,782 zapytań

141,712 odpowiedzi

320,590 komentarzy

62,114 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.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...