Cześć,
piszę z pytaniem o pomoc.
Na zajęciach dane nam zadanie "do próby samodzielnego rozwiązania" - brzmi ono następująco:
Na rysunku przedstawiony jest układ korytarzy labiryntu wraz z czasem potrzebnym do przejścia kolejnych korytarzy. Korzystając z algorytmu dla problemu chińskiego listonosza, zaplanować trasę przejścia wszystkich korytarzy labiryntu w jak najkrótszym czasie - do labiryntu wchodzi się wejściem oznaczonym s, a opuszczamy t. W odpowiedzi podać wyznaczoną drogę otwartą oraz całkowity czas drogi.
I tutaj pojawia się kilka wątpliwości - po zapoznaniu się z tym czym jest problem chińskiego listonosza, nie potrafię dojść do tego jak znaleźć odpowiednią drogę która rozpoczyna się i kończy w dwóch różnych punktach.
Oczywiście początkowo znalazłem wierzchołki które mają nieparzystą liczbę połączeń - były to wierzchołki s, a, g, h, t, e.
Wiem też że trzeba następnie znaleźć jak najkrótsze drogi pomiędzy ww. punktami i zdublować najkrótszą drogę (tylko właśnie - czy jeśli najkrótszą drogą pomiędzy wierzchołkami s i e będzie droga sce, a między s i t będzie droga scet, to czy odcinki sc i se będą podwojone czy potrojone?).
No i w końcu - co dalej? Właściwie nie mam pomysłu i za każdym podejściem mam inny pomysł na to zadanie, a ostatecznie na końcu dochodzę do wniosku że zawsze robię to źle.
Jak się za to zabrać, tak najbardziej łopatologicznie? Z góry dziękuję za pomoc
Problem chińskiego listonosza
-
- Użytkownik
- Posty: 6882
- Rejestracja: 7 gru 2010, o 16:50
- Płeć: Mężczyzna
- Lokalizacja: Staszów
- Podziękował: 50 razy
- Pomógł: 1112 razy
Re: Problem chińskiego listonosza
Jeżeli
ulice są jednakowej długości to może tak?
\(\displaystyle{ 18 + 3 = 21}\)
Pan kerajs w lisćie do mnie zauważa to, czego nie dostrzegłem zasugerowany równbocznością rozkładu ulic, że jest to najszybsza trasa. Dziękuję za tę uwagę.
ulice są jednakowej długości to może tak?
\(\displaystyle{ 18 + 3 = 21}\)
Pan kerajs w lisćie do mnie zauważa to, czego nie dostrzegłem zasugerowany równbocznością rozkładu ulic, że jest to najszybsza trasa. Dziękuję za tę uwagę.