Algorytm obejścia całego miasta (coś jak w labiryncie)

0

Koledzy, potrzebuję Waszej pomocy. Czy znacie jakiś prosty algorytm na to, aby osoba, która weszła do miasta obeszła wszystkie ścieżki? Prosty w sensie powiedzenia człowiekowi, podobnie jak w prostym labiryncie: "trzymaj się cały czas prawej strony". Akurat to nie zdaje egzaminu, bo w przypadku pętli możemy się kręcić i kręcić.
Aby nie być gołosłownym, odpalcie mapy.google.pl i wpiszcie: Przylep, lubuskie
Zobaczycie mapę miejscowości. Jest główna droga. Wchodzą dwie osoby, które mają za zadanie obejść cały teren. Jednak z lewej strony drogi, druga z prawej. Czy można im w jakiś prosty sposób przekazać, jak mają się poruszać? Cel jest jeden: obejść teren. Jeśli przejdą dwa razy tą samą drogą, to nic się nie stanie.
Tylko proszę nie mówcie mi: "poczytaj o teorii grafów, metody ich przeszukiwania". Takie rzeczy implementowałem na studiach. Tu jest przykład praktyczny, który z akademickim ma jednak mało wspólnego.
EDIT:
Wiem, już problem nazywa się to problemem chińskiego listonosza (ang. Chinese postman problem - CPP)

0

Guzik prawda. Problem chiskiego listonosza jest NP-zupełny bo szuka minimalnej ścieżki, a ty mówisz że ci to obojętne. Możesz puścić po grafie DFS/BFS i z tego odczytać sobie ścieżkę, ale minimalna to ona nie będzie.

0

Tak, już zauważyłem, że mi to lotto. Problem jest innego typu: co powiedzieć człowiekowi, który wchodzi do miasta? Mam mu dać kartkę, długopis i powiedzieć przeszukaj sobie graf?
ps. Kiedyś miałem taką książkę, jak poruszać się w terenie, po labiryncie. Był tam taki prosty algorytm z kamykami/cukierkami, ale nie pamiętaj już konkretów.

0

No wiesz, słownomuzyczny opis DFS'a jest raczej dość trywialny:

  • idziesz na pałę (tzn na przykład na każdym rozwidleniu wybierasz pierwszą drogę w prawo) tak daleko jak się tylko da, zaznaczając które ścieżki już przeszedłeś
  • jak droga się skończy lub gdzieś już byłeś (tzn jedyna droga którą możesz iść już była widziana) to wycofujesz się aż do miejsca gdzie jest droga na której nie byłeś
0

Mi to jednak "smierdzi" problemem leniwego listonosza. Bez sensu, ze gosc pojdzie na drugi koniec miejscowosci, jak pod nosem ma jeszcze nieodwiedzone sciezki. Z drugiej strony, program zna wagi wiercholkow, a czlowiek nie wie, gdzie jest i ktora trasa jest optymalna.
Wydaje mi sie, ze rozsadnym rozwiazaniem bedzie po porostu wydrukowanie planu i wytlumaczenie, jak ma isc (ew. wklepac dane do kompa i znalezc optymalna sciezke). Trzeba jedynie dopilnowac, aby byl to ten sam czlowiek, bo proces uczenia pojdzie w komin.

0

Nie no oczywiście że lepiej wyliczyć optymalną drogę, ale pytałeś o prosty algorytm który można podać komuś kto dostaje mapę. Zdecyduj się! No i weź pod uwagę że skoro to problem NP-zupelny to optymalny algorytm będzie wykładniczy i dla większej mapy życia ci braknie zanim to się policzy.

0

Spokojnie, ja doceniam Twoja pomoc. Po prostu od razu na biezaco pisze moze przemyslenia. Co do liczenia itd. to jak juz pisalem. Miejscowosci nie sa duze i jest to problem czysto praktyczny, a nie akademicki :)

3

zastanawiam się co to za problem "praktyczny nie akademicki", gdzie nieważna jest optymalizacja.
według mnie nie ma on nic wspólnego z praktyką. to jak sortowanie przez wstawianie. robi co trzeba tylko dłużej.
jak dla mnie to nie jest praktyka, a czysto akademickie zagadnienie...

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