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.
To jest problem komiwojażera, więcej znajdziesz w internecie:
https://www.google.pl/search?client=opera&q=problem+komiwojażera+algorytm&sourceid=opera&ie=UTF-8&oe=UTF-8#q=problem+komiwoja%C5%BCera+algorytm+c%2B%2B
https://www.google.pl/search?client=opera&q=problem+komiwojażera+algorytm&sourceid=opera&ie=UTF-8&oe=UTF-8
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.
Tak, tu chodzi o najkrotsza sciezke w grafie, chociaz to moze byc jakas modyfikacja, bo jednak nazwa funkcji to komiwojazer :)
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.
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).
