GDUS-Bounding

Die Strategie der GDUS (Goal-directed-unidirectional-search),  auch unter dem Namen $\cal{A}^*$-Algorithmus  bekannt, kommt aus dem Bereich des Maschinenlernens und des VLSI-Designs. Sie versucht, Information zu verwenden, um die Berechung eines kürzesten Pfades zielgerichteter zu einem Zielknoten t zu gestalten. Dies geschieht mit Hilfe einer unteren Schranke $l(q\to t)$. Zuerst definiert man die Kosten einer Kante (q,r) wie folgt neu:

$$c'(q,r) := c(q,r) - l(q\to t) + l(r\to t)$$

wobei $l(q\to r)$ eine untere Schranke für die Kosten $c(q\to^* r)$ eines kürzesten Pfades von q nach r ist. Wenn l() die Konsistenz-Bedingung erfüllt:

$$c(q,r) +l(r\to t) \geq l(q\to t), \ \forall (q,r)\in E$$

dann kann man zeigen, daß die Umgewichtung der Kantenkosten nichts am optimalen Pfad ändert und die Kantengewichte immer noch positiv sind, also immer noch Dijkstras Algorithmus angewandt werden kann. Wir werden $L(q\to t)$ als untere Schranke benutzen. L erfüllt die Konsistenz-Bedingung:

 

$$c(q,r)+L(r\to t) \sum_{1\leq i< j\leq k} (c(A^*(\sigma^r_i,\sigma^r_j)) + d(a_{i,*},a_{j,*})$$ =

$$\geq \sum_{1\leq i< j\leq k} (c(A^*(\sigma^q_i,\sigma^q_j))$$

$$L(q\to t)$$ =

Man kann sich vorstellen, daß eine bessere untere Schranke die Suche zielgerichteter zu t macht. Im Extremfall, wenn L scharf ist, so wird aus der priority queue immer nur der nächste Knoten auf einem optimalen Pfad extrahiert. Im anderen Extremfall, wenn L=0, haben wir genau den Fall des Standard-Boundings. Wir wenden nun Standard-Bounding auf den Grid-Graph mit umdefinierten Kantengewichten an. Mit den neuen Kantengewichten hat ein kürzester Pfad von s nach q die Kosten $c'(s\to^* q)=c(s\to^* q)+L(q\to t) -L(s\to t)$. Da der Wert $L(s\to t)$ eine vorberechnete Konstante ist, lassen wir ihn weg und fügen einen Nachbarknoten r mit dem Wert $\mbox{{\sc Prio}}_q(r)$ in die priority queue Q ein, wobei

   $$\mbox{{\sc Prio}}_q(r) := c(s\to^* q) + c(q,r) + L(r\to t)$$

Wenn wir nun das Standard-Bounding anwenden, so müssen wir nicht immer einen Knoten r in Q einfügen, nämlich genau dann dann nicht wenn

$$\mbox{{\sc Prio}}_q(r) > U$$

wobei U eine obere Schranke für $c(s\to^* t)$. Die Argumentation ist wie oben, da $\mbox{{\sc Prio}}_q(r)$ eine untere Schranke für den Wert eines kürzesten Pfades von s nach t durch q und r ist.

Dies schließt nicht aus, daß r eventuell später in Q eingefügt wird, wenn es von einem anderen Nachbarknoten q' aus besucht wird. Wenn r jedoch nie in Q eingefügt wird, d.h., wenn $\mbox{{\sc Prio}}(r):= \min_{(q,r)\in E} \ \mbox{{\sc Prio}}_q(r) > U$, dann nennen wir r U-ungültig, anderenfalls U-gültig. Der folgende Satz wurde unabhängig von Lermen in [Ler97] und Horton und Lawler in [Hor97] bewiesen.

Satz 12   CL-Ungültigkeit impliziert U-Ungültigkeit.

Beweis:

$$\begin{eqnarray*}\mbox{CL}_{i,j}(q) & = & c(A^*(\alpha^q_i,\alpha^q_j)) + c(A^*... ...c(s\to^* q) + L(q\to t) \\ & =: & \mbox{{\sc Prio}}(q) \\ \end{eqnarray*}$$

Wenn also CL _i,j(q)>U für alle i,j dann ist auch PRIO(q)>U, das heißt q ist insbesondere U-ungültig, wenn es CL-ungültig ist.