Előbb egy kis száraz elmélet az útvonalkeresésről.
Az egyik legrövidebbút-kereső megoldás a Dijkstra-algoritmus. Arra való, hogy egy gráfban egy kiinduló pontból megtalálja a legrövidebb utat az összes többi pontba vagy egy konkrét célpontba vezető legrövidebb utat.
Így működik egy gráfon:
- a kezdőpont távolsága 0, minden másé végtelen
- mindig kiválasztja a jelenleg legközelebbi még fel nem dolgozott csúcsot
- megnézi a szomszédait, és ha rajta keresztül rövidebb út adódik, frissíti a távolságukat
Mindezt addig ismétli, amíg minden szükséges pontot feldolgoz.
Fontos feltételek:
- nem negatív élköltségekkel működik helyesen
- negatív súlyokra nem ezt használják
Tegyük fel, hogy A-ból szeretnénk D-be eljutni:
A lehetséges utak:
- A -> B -> D = 4 + 1 = 5
- A -> C -> D = 1 + 5 = 6
- A -> C -> B -> D = 1 + 2 + 1 = 4A Dijkstra algoritmus ezt fogja megtalálni legrövidebb útnak:
azaz
A -> C -> B -> D, összköltség: 4A lépések röviden:
Indulás: A = 0, minden más = végtelen
A-ból: B = 4, C = 1
A legkisebb a C, onnan: B = 3, D = 6
A legkisebb a B, onnan: D = 4
Kész: a legrövidebb út D-ig 4De hogy jön ez mindahhoz, amit csinálunk?
Van egy szoftverünk, amit a saját munkánk elvégzéséhez fejlesztünk - Zorka kisunokám a KUKUGYA nevet adta neki, így mi is így hivatkozunk rá ezek után. Ebben az alkalmazásban az épület alaprajzán tervezzük többek között az egyes villamos eszközök elhelyezését is. Az elosztót és villamos végpontokat a kezdetek óta össze tudtuk benne vonalakkal kötni - így kalkuláltuk a vezetékutak hosszát.
A kézi vezetékút rajzolással több probléma is van:
- sokszor ugyanazon az útvonalon kell több vezetékutat rajzolni, amitől egyre átláthatatlanabb lesz a terv
- komplexebb projekteknél érdemes lenne a legoptimálisabb útvonalhosszal tervezni, hogy kábelt spóroljunk az ügyfélnek, ha a körülmények ezt lehetővé teszik
Ennek feloldására született az auto routing, amihez a fent nagyon röviden elmagyarázott Dijkstra algoritmust használtuk. Az autorouting a kiválasztott eszköz és elosztó között úgy keresi meg az optimális utat, hogy az eszköztől indulva eljut a legközelebbi falig, majd a falak mentén a legrövidebb úton elmegy a kívánt elosztóba:
Néha előforul, hogy az automatikus routingnak "fogni kell a kezét", mert bizonyos szakaszokat elkerül / más irányokba viszi az útvonalat, mint ami a valóságban lehetséges. Erre találtuk ki a guided routingot. A guided routing az autorouting által megtalált potenciális szegmens végpontokat ajánlja fel a felhasználónak, aki egyesével választhat és lépésről lépésre irányíthatja az algoritmust. A guided routing része az is, hogy ha az útvonal már "irányba áll", azaz a hátralevő részt már megcsinálhatná automatikusan a szoftver, akkor egy billentyű lenyomásával kérhetjük és az útvonalat onnantól az autorouting fejezi be.
További problémát tud jelenteni az, hogy több vezetékút kétféleképpen egyezhet meg azonos típusú kábelek esetén:
- két kábel indul az elosztóból, részben hasonló útvonalat bejárva
- egy kábel indul az elosztóból, majd egy ponton elágazva két vagy több külön kábel lesz belőle
A második eset tud némi kalamajkát okozni: egyrészt látnunk kellene, hogy meddig közös a kábelszakasz, másrészt a szükséges kábelhosszt számoló algoritmusnak is így kellene kalkulálnia. Erre találtuk ki a szülő-gyerek kábeleket.
Az elosztóból induló kábel mindig szülő. Az azonos típusú másik kábel a szülőbe gyerekként csatlakozhat - ilyen esetben a szülő és a gyerek kábel is saját egyedi azonosítót kap, valamint a gyerek kábelt kiválasztva a szoftver másképpen jelöli a szülő szakaszt:
Az alkalmazás online dokumentációként működve mutatja a tervezett kábeleket, valamint a tervekből generált project bookban vezetékutanként külön oldalt generál a telepítést végzőknek.