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

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

Object Storage Arubacloud
0 głosów
349 wizyt
pytanie zadane 19 stycznia 2021 w Java przez MarKor Nowicjusz (180 p.)
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 :)

2 odpowiedzi

+1 głos
odpowiedź 19 stycznia 2021 przez Wiciorny Ekspert (271,430 p.)
A jak aktualnie twoj program wygląda w javie :)?
komentarz 19 stycznia 2021 przez MarKor Nowicjusz (180 p.)
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! ?
komentarz 19 stycznia 2021 przez Wiciorny Ekspert (271,430 p.)
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
0 głosów
odpowiedź 20 stycznia 2021 przez manjaro Nałogowiec (37,390 p.)
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.

Podobne pytania

0 głosów
2 odpowiedzi 1,382 wizyt
pytanie zadane 20 października 2018 w Java przez Kamyyylo Początkujący (460 p.)
0 głosów
1 odpowiedź 621 wizyt
pytanie zadane 3 stycznia 2020 w C i C++ przez Programmingc100 Bywalec (2,620 p.)
0 głosów
1 odpowiedź 608 wizyt

92,654 zapytań

141,543 odpowiedzi

319,954 komentarzy

62,022 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...