Ciklično routanje po grafu ali nekaj podobnega

Imam tako situacijo.
Vzamimo zemljevid in iz njega zgradimo graf ulic. Križišče je vozlišče, uteži povezav so razdalje med križišči. Za vsako vozlišče vem še geografsko širino in dolžino.
Iz izhodiščnega vozlišča želim poiskati vse poti, ki se vrnejo nazaj v izhodišče. Pri tem lahko postavljam dodatne omejitve, npr:
- pot mora iti skozi nekaj izbranih vozlišč
- dolžina poti mora biti čim bližja izbrani
- nočem subciklov, razen degeneriranih v krajše vračanje po isti poti
- iz izhodišča želim krenit v dano smer (S, J, V, Z)
- nočem nazaj v izhodišče ampak v poljubno vozlišče
- in podobno...

Kakšna ideja, kako se zadeve lotit elegantno? Na pamet mi najprej pade nekaj (na grobo) v stilu A*, s hevristiko, ki rine v želeno smer in zavrača neperspektivna kandidatna vozlišča.

To je sicer res, ampak Hamiltonovi cikli na podgrafih so dejansko prestrog kriterij za pogoje in so samo podmnožica meni interesantnih rešitev.
Praktično rabim suboptimalne rešitve, itak so dodatni pogoji 'mehki' in sploh ni nujno, da jih je mogoče eksaktno izpolnit.

Zadeva bo praktično uporabna, če bo delovala na poprečnem PC-ju v skoraj realtime na nekaj deset tisoč vozliščih.

> Iz izhodiščnega vozlišča želim poiskati vse poti, ki se vrnejo nazaj v izhodišče.
Če iščeš vse poti (brez podciklov, tako da jih ni neskončno) potem brezveze A*. Iščeš pač po drevesu rešitev v globino, širino, kakorkoli ti paše, dokler celega ne preiščeš.

> - dolžina poti mora biti čim bližja izbrani
To je sedaj povsem drug primer, kjer bi kakšen sistem lokalne optimizacije prišel prav, npr. postaviš random rešitev in jo potem po odsekih popravljaš da se približaš tvoji iskani dolžini.

> - pot mora iti skozi nekaj izbranih vozlišč
Potem razdeliš problem na podprobleme ko iščeš poti med posameznimi podanimi vozlišči

Ker imaš toliko različnih omejitev je težko kaj smiselnega izbrati, kar bi se v vseh primerih razumno obnašalo. Jaz bi morda poskusil takole. Gradnja poti od starta do cilja in hkrati od cilja do starta (naključna ali po A* ali kako drugače). Ko se poti srečata imaš rešitev. Potem to rešitev optimiraš ali pa poiščeš nove, odvisno od izbranih omejitev. Če imaš podana obvezna vozljišča potem hkrati gradiš poti iz vseh obveznih vozlišč v vsa druga obvezna vozlišča. Tiste poti, ki se prve srečajo obdržiš, ostale zavržeš. Seveda pri pogoju da je obveznih vozlišč malo, drugače bo to boom v kompleksnosti. Če imaš podano željeno dolžino poti lahko prvo dobljeno pot potem spreminjaš po odsekih (med obveznimi vozlišči). Za cikle skrbiš med gradnjo. Za željeno smer skrbiš takisto med gradnjo (recimo da ti A* poti bližje vozlišču, ki gredo v napačno smer slabo oceni). In podobno...

Hvala vsem, nekaj novih idej je padlo.

- dolžina poti mora biti čim bližja izbrani
- nočem nazaj v izhodišče ampak v poljubno vozlišče

Ce upostevas alineji, potem temu problemu recemo problem minimalnega vpetja drevesa (Minimal Spanning Tree), ce se pravilno razumeva. Problem ni NP-poln.