Prosty algorytm rozwiązjuący komiwojażera

0

Jest jakiś niezbyt zaawansowany algorytm rozwiązujący problem komiwojażera? Mam coś takiego:

Napisz program, który umożliwi znalezienie najkrótszej drogi, którą trzeba przejść aby „odwiedzić” wszystkie punkty z podanych przez użytkownika Użytkownik decyduje o tym ile punktów chce podać (max 10). Każdy punkt to dwie współrzędne (x,y).

Z tego co czytałem, to jest to jedno z prostszych poleceń jeżeli chodzi o ten problem.. ale nie mam pomysłu za bardzo jak można to rozwiązać.. Jedyne co przychodzi mi do głowy, to porównanie pierwszego punktu z każdym innym- przejście do najbliższego i znowu porównanie z każdym kolejnym...

2

Ale czy punkty mają utworzyć cykl hamiltona? Tzn czy możemy wejść do każdego punktu tylko raz? Bo jeśli nie ma takiego ograniczenia to to nie jest komiwojażer ;]
Jeśli jednak ograniczenie istnieje to algorytm który podałeś jest błędny bo algorytm zachłanny wcale nie jest poprawny dla komiwojażera, co łatwo udowodnić ;]
Algorytm dokładny którego ci potrzeba to algorytm wykładniczy - lepszego nie znajdziesz.

0

Shalom- Z tego co nauczyciel w bardzo zresztą lakoniczny sposób wytłumaczył to, jest to problem komiwojażera i mamy odwiedzić wszystkie punkty raz wracając na końcu do pierwszego. To co podałem, to jedynie mój wymysł na który wczoraj w nocy wpadłem, nawet nie wiedziałem, że nazywa się on algorytmem zachłannym ( dobrze wiedzieć)..
lepszego=prostszego ? Nie jestem zaawansowany bym implementował jakieś właśnie nowoczesne algorytmy, dlatego pytam czy może jest coś prostrszego. Tutaj jest max 10 pkt do przebycia, a jeżeli było by ich np 5 to zmienia to coś?

0

@Greku każdy algorytm który poprzez osiągnięcie kolejnych lokalnych minimów/maksimów próbuje osiągnąć minimum/maksimum globalne - tak się nazywa.

0

No ok, to już coś. A jakaś podpowiedź jak to rozwiązać za pomocą owgo algorytmu ? Z terminem i tak sie nie wyrobie już, ale może w wolnym czasie spróbowałbym to napisać dla siebie. Swoją drogą to nie przesada po połowie semestru taki problem rozwiązać w ciągu tyg? ( nie tylko to zad oczywiście na liście było)

Jeżeli chodzi jeszcze o ten algorytm zachłanny, z tego co czytałem, to dla kilku punktów powinien działać w miarę dobrze i nie zajmować wieków. Czy problem jego polega na błędnych obliczeniach?

0

Algorytmy zachłanne są bardzo szybkie i dają zwykle dobre rezultaty.
Algorytm zachłanny może, ale nie musi znaleźć najkrótszej drogi. Nie wiem czy dobrze pamiętam, ale ten algorytm zachłanny dla problemu komiwojażera chyba gwarantuje, że znaleziona ścieżka nie będzie więcej niż x razy dłuższa od najkrótszej (chyba 2x, ale musisz poszukać, bo pamięć zawodna jest, a nie mam czasu tego wyprowadzać).

Dokładnie problem komiwojażera można rozwiązać np. metodą branch-and-bound:
http://www.academic.marist.edu/~jzbv/algorithms/Branch%20and%20Bound.htm
Złożoność jest wykładnicza, ale i tak znacznie lepsza niż przy naiwnej enumeracji wszystkich możliwości. Dla n=10 zadziała bez problemu.

1

Dla n = 10 to i chamska rekurencja z powrotami zadziała bo przecież 2^n to będzie raptem 1024 przypadki ;] Wystarczy zrobić takiego niby-dfsa i zapisywać sobie maksymalną osiągniętą sumę wag na ścieżce

Swoją drogą to nie przesada po połowie semestru taki problem rozwiązać w ciągu tyg

hahahaha :D :D
Przykład zadań z 15-20 minutowych kartkówek które pisało się "za moich czasów" (połowa 1 semestru studiów). To tak żebyś miał na czym poćwiczyć:

Na liczbach naturalnych określono 3 rodzaje przekształceń:
a:=a+1
a:=3*a
a:=a div 2 (tylko jeżeli liczba a jest parzysta)
Napisać w program, który rozstrzyga czy jest mozliwe przekształcenie liczby a w b w serii
przekształceń o długości nie większej od n, warości a,b,n nalezy wczytać z klawiatury,
na przykład dla danych a=13 b=11 n=5 odpowiedz brzmi tak bo
13->14->7->21->22->11
dla danych a=13, b=6, n=5 odpowiedź brzmi nie

masz tablicę integerów od 1 do max, gdzie integery są wagami ciężarków i nie powtarzają się. Ciężarki można kłaść na obu szalkach wagi
a) napisz funkcję sprawdzającą, czy da się odważyć dany ciężar
b) napisz funkcję zwracającą z ilu ciężarków minimalnie można odważyć (oczywiście bez korzystania z poprzedniego, bo byłoby to nieefektywne)

Mamy tablice 1..max wypełnioną liczbami pierwszymi (różnymi i nie po kolei!). Podajemy jako parametr tablicę i przedział szukanych iloczynów. Funkcja zwraca ile liczb utworzonych przez iloczyny liczb z tablicy zawiera się w naszym przedziale

0

Dobra wymiękam , niezłę te kartkówki mieliście :P

1 użytkowników online, w tym zalogowanych: 0, gości: 1