Autor Wątek: Heurystyka do problemu chińskiego listonosza  (Przeczytany 1289 razy)

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

# Sierpień 28, 2013, 20:13:11
Witam :-)

Próbuję wymyślić jakąś prostą heurystykę do problemu chińskiego listonosza.
Wiem że istnieje dobry algorytm rozwiązujący ten problem w czasie wielomianowym,
natomiast mimo wszystko jestem ciekawy jaką można by wymyślić do tego problemu
prostą heurystykę. Jak do tej pory odrzuciłem próbkowanie losowe jako zbyt mało
wydajne, natomiast aktualnie rozważam skorzystanie z podejścia hill-climning.
Natknąłem się jednak na problem z transformacją tymczasowego rozwiązania w jakiegoś
obiecującego sąsiada z przestrzeni rozwiązań. Jeżeli ktoś wymyśliłby jakąś względnie prostą
heurystykę będę wdzięczny za podzielenie się nią ze mną :-)

EDIT:
Graf jest ważony, nieskierowany.

Z góry dzięki,
Buyuk.



EDIT2 :
@Krzysiek K.: Dzięki za pomysł :-)
« Ostatnia zmiana: Październik 26, 2013, 19:55:34 wysłana przez Buyuk »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +1
# Sierpień 29, 2013, 00:22:09
Skoro ma być prosta, możesz spróbować tak:
1. Znajdujesz wszystkie punkty, które mają nieparzystą liczbę sąsiadów.
2. Wyznaczasz odległości najkrótszych ścieżek między nimi.
3. Zachłannie wybierasz najkrótszą ścieżkę z wyznaczonych i zapamiętujesz.
4. Powtarzasz krok 3, za każdym razem pomijając punkty które są już punktami końcowymi jakiejś wybranej ścieżki.
5. Znajdujesz cykl Eulera w grafie wyjściowym po uwzględnieniu dodatkowych ścieżek.