12. Útkeresés

Autopalya hierarchiak

$G_0$ az input es majd sorba fel fogunk egyre kisebb grafokat epeiteni, a csucsoknak egy-egy reszahlmaza egyre kisebb halmazon. Tehat felepitjuk valahogyan a $G_0,G_2,\dots$ grafokat ugy hogy $V_0\supset V_1\supset V_2\supset \cdots \supset V_l$ ahol $|V_l\approx \sqrt{|V_0|}|$, ahol $V_i$ a $G_i$ graf csucshalmaza.

$G_1^{\prime }=(V_0,E_1^{\prime })$ ahol $E_1^{\prime }$ az autopalya elek halmaza.
Azt mondjuk, hogy $uv$ autopalya el ha

1. Letezik $s,t\in V_0$ ugy hogy a legrovidebb $s\to t$ ut atmegyen az $uv$ elen
2. $v$ nincs kozel $s$-hez
3. $u$ nincs kozel $t$-hez

Megj.: Figyeljuk meg, hogy ha csak 1.-et tennenk fel akkor majdnem minden el autopalya el lenne, a zsakutcakon kivul.

Megj.: Az, hogy $v$ es $s$ kozel vannak az itt ugy van definialva, hogy elinditunk egy Dijkstra algoritmust $s$-bol es ha $k$ lepes utan (ahol $k$ egy elore rogzitett konstans) elerjuk $v$-t akkor kozel vannak, kulonben nem.

$V_1$-et a kovetkezo keppen kapjuk:

1. Kitoroljuk az izolalt csucsokat es zsakutcak vegeit.
2. Osszehuzzuk a $2$ foku csucsokat, amit azt jelenti, hogy ha van $u$ csucs amibol ket ut megy $c_1$ es $c_2$ sulyokkal akkor ahelyett egy $c_1+c_2$ sulyo utat allitunk elo es kitoroljuk $u$-t.

Igy megkapjuk a $G_1$ grafot. Ezt az eljarast iteralva megkapjuk az algoritmust.

Igy megkaptuk a $G_1,G_2,\dots$ grafokat amelyek egyre kevesebb csucsokat tartalmznak. Ha $G_i$-ben elerunk egy autopalya csocsot akkor $G_{i+1}$-be fellepunk $0$ koltseggel es ott is folytatjuk a keresest.

Tranzit csucsok

Legyen $T\subseteq V$ a tranzit csucsok halmaza. Minden $v$-hez $A(v)$ hozzarendelt tranzit csucsok halmaza.

Kell: Minden $s,t$-re nem nem lokalis csucsokra, letezik $a\in A(s)$ es $b\in A(t)$ ugy, hogy a legrovidebb $s\to t$ ut atmegy ezeken.

Peldaul lehet $T=\bigcup A(v)$

Eltaroljuk $\forall u,v\in T$ $d(u,v)$ es $\forall v\in V$ $A(v)$ elemeit es $d(v,a)$

Osszehuzasi hierarchiak

Góbor Dániel 2013 Bsc. szakdolgozat, 2015 Msc. szakdolgozat

Elofeldolgozas: Adott $v$ csucsot szeretnenk osszehuzni. $\forall u,w$ csucsra, melyek szomszedai $v$-nek, megnezzuk a legrodivedebb $u\to w$ ut hosszatt, amely nem hasznalja $v$-t, legyen ez $d_{G-v}(u,w)$.

$v$ osszehuzasa:

• Ha $d_{G-v}\le c(uv)+c(vw)$ akkor nyugodtan kitorolhetjuk $v$-t.
• Kulonben hozzunk letre egy uj $uw$ elt, aminek a sulya legyen $c(uw)=c(uv)+c(vu)$.

FOR i = 1..n
	choose vertex v_i and collapse it

$\tilde{G}=(V,\tilde{E})$ $\forall$ regi es behuzott el
$G_{\uparrow }=(V,E_{\uparrow })$ ahol $v_i{v}_j\in E_{\uparrow }$ ha $i<j$ es $v_i{v}_j\in \tilde{E}$
$G_{\downarrow }=(V,E_{\downarrow })$ ahol $v_i{v}_j\in E_{\downarrow }$ ha $i>j$ es $v_i{v}_j\in \tilde{E}$

Igy az eredeti grafot szetszedtuk ket aciklikus grafra.

Legyen $P$ $\tilde{G}$-ben egy olyan legrovidebb $s\to t$ ut, ami a legrovidebb keresett elbol all.

All1.: $P$-ben nem lehet olyan hogy hatra utan elore el jon.

pelda: Nem lehet olyan hogy $v_8$-bol elmegyunk $v_6$-ba es utana $v_9$-be.

All2.: $P$-ben legfeljebb egyszer johet elore utan hatra.

pelda: Legfeljebb egyszer lehet olyan hogy $v_6$-bol elmegyunk $v_9$-ba es utana $v_8$-be.

All3.:

$$d(s,t)=\underset{u}{\min }(d_{\uparrow }(s,u)+d_{\downarrow }(u,t))$$

$\forall u$ duplan vegl. kesz, $d_{\min }$

Leallhatunk, ha vegl. $w$: $d_{\uparrow }(s,w)>d_{\min }$