Forum Gry Hobby Sprzęt Rozmawiamy Archiwum Regulamin

Forum: Algorytm do obliczania najkrótszej trasy w C++

19.01.2016 20:01
dexapini9
📄
1
dexapini9
116
veritas odium parit
Image

Algorytm do obliczania najkrótszej trasy w C++

Cześć. Mam do was prośbę i zarazem pytanie. Mam do wykonania taki program, który obliczy najkrótszą trasę z punktu A do np. X i po drodze będzie "jechał" jak najkrótszą trasą, mijając punkty B, C, D itd. Liczba punktów nie jest ważna, lecz istotne jest, by program znajdował najkrótsze odległości między punktami i nimi podążał (nie może 2 razy przejeżdżać przez dany punkt). Kolega tłumaczył mi jak to zrobić, ale nadal mam z tym problem --------->

Prośba jest taka: czy ktoś z was mógłby mi w komentarzu podać przykładową funkcję z algorytmem odnośnie tego, co do góry napisałem? Nie musi być to nic wybitnego, jedynie "prosta" funkcja, za pomocą której mógłbym obliczać takie rzeczy. Bardzo proszę o pomoc.

19.01.2016 21:25
2
odpowiedz
3 odpowiedzi
MOD
182
Generał
20.01.2016 10:26
2.1
poltar
175
Senator

Studia skonczylem dawno temu i pisanie niepotrzebnych nikomu algorytmow jest juz dawno za mna - ale to co zapamietalem to fakt, ze w problemie komiwojazera trzeba uwzglednic odwiedzenie WSZYSTKICH punktow podrozy. Do tego nalezy konczyc trase w punkcie wyjscia. Nie jest to algorytm znajdujacy najkrotsza trase.

20.01.2016 10:45
nagytow
2.2
nagytow
146
Firestarter

Tak, tu chodzi o najkrotsza sciezke w grafie, chociaz to moze byc jakas modyfikacja, bo jednak nazwa funkcji to komiwojazer :)

20.01.2016 10:48
2.3
Likfidator
120
Senator

Autor źle opisał zadanie. Na screenie wyraźnie widać, że to komiwojażer. Zobaczcie tylko parametry funkcji Salesman, tylko zbiór punktów i wyjściowa trasa. Nie ma mowy o punkcie wejścia i wyjścia.

19.01.2016 21:26
Tlaocetl
3
odpowiedz
Tlaocetl
196
Ocenzurowano

Prosta funkcja.... HAHAHA! :)

19.01.2016 23:00
4
odpowiedz
Andrewlee
161
Crossroads

Ogólnie standardowe rozwiązanie opiera się na tym, że obliczasz i zapisujesz rozwiązania mniejszych podproblemów. Np. jeżeli masz węzły A, B, C, D to najpierw obliczasz drogi między dwoma węzłami - np. A->B, A->C i A->D. W następnym kroku obliczasz drogi pomiędzy trzema węzłami korzystając z poprzednio obliczonych pomiędzy dwoma i dodając odległość do aktualnie rozpatrywanego trzeciego węzła. Zapisujesz odległości dla trzech węzłów. I tak dalej.
Oczywiście w miarę wzrostu liczby węzłów liczba tych podproblemów staje się bardzo, bardzo duża i dlatego problemy tego typu zajmują komputerowi dużo czasu do rozwiązania (problemy NP-zupełne).

Forum: Algorytm do obliczania najkrótszej trasy w C++