Mautproblem

Das Mautproblem (englisch: Turnpike problem) ist eine Fragestellung in der theoretischen Informatik. Man habe eine Multimenge mit allen Entfernungen zwischen den Ein- und Ausfahrten einer Autobahn. Lässt sich die Lage der Ausfahrten aus diesen Entfernungen konstruieren?

Etwas formaler: Es seien $0= x_0 < x_1 < \ldots < x_n$ positive Zahlenwerte (die Lage der Ausfahrten beginnend bei Kilometer 0) und A eine $n \times n$-Matrix mit A_i,j = | x_i − x_j | , welche also zu jedem Ausfahrtpaar die Entfernung angibt. Die Werte $A_{i,j}, 1 \leq i < j \leq n$, seien so sortiert in einem Feld F (der Multimenge) gegeben. Gesucht sind daraus die Werte x_k.

Per Backtracking kann eine Lösung für das Problem gefunden werden, indem zunächst immer der größte noch in F vorhandene Entfernungswert genommen wird. Getestet wird die Lage der neuen Ausfahrt rekursiv einmal mit der Position, die um diese Entfernung von der derzeit am meisten links liegenden Ausfahrt entfernt ist. Führt dieser Zweig nicht zum Ziel wird man die Position von der am meisten rechts liegenden Ausfahrt versuchen. Unter der jeweils angenommenen Position wird geschaut, ob die neu entstehenden Entfernungen, zwischen den bestehenden und der neuen Ausfahrt, auch in F vorkommen. Ist dies nicht der Fall, war dieser Rekursionszweig ein Irrweg und es wird in der Rekursion zurückgegangen.

Die Komplexität ist dabei im schlechtesten Fall allerdings exponentiell, in den meisten Fällen nach empirischen Untersuchungen jedoch deutlich besser.

Trivialerweise kann man umgekehrt von der Entfernungsmartix A in $\mathcal{O}(n^2)$ zu den Werten x_k kommen.