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)
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.
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.
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ś
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.
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.
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 :)
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...