Problem chińskiego listonosza

[devitto]

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.

AU

49faf33eb91aeed0gen.jpg (35.96 KiB) Przejrzano 151 razy

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

[kruszewski]

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ę.