4/ 19 Das Brückenproblem (kurze Rekapitulation) Ausgangspunkt der Betrachtungen ist das bekannte Brückenproblem: Gesucht ist ein nicht bekannter Zielpunkt auf zwei Halbgeraden. Startpunkt  :  s Zielpunkt  :  t Halbgeraden  :  m_n Suchtiefe  :  f_j Kosten (optimal)  :  K_OPT      Kosten (der Strategie)  :  K_S Hierbei bezeichnen die Kosten die Weglänge Abb. 1 Zur Lösung dieses Problems haben wir im wesentlichen zwei Ansätze gehabt: 1. inkrementelle Suchtiefenvergrößerung     (unberücksichtigt) 2. exponentielle Suchtiefenvergrößerung Mit der exponentiellen Suchtiefenvergrößerung von f_j = 2ⁿ haben wir die (optimale) 9-Kompetitivität für das allgemeine Brückenproblem bewiesen.                                                                          m₁                                                     s                                        m₂       t