Mautproblem

Das Mautproblem (englisch: Turnpike problem) ist ein Problem 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 ${\displaystyle 0=x_{0}<x_{1}<\ldots <x_{n}}$ positive Zahlenwerte (die Lage der Ausfahrten beginnend bei Kilometer 0) und ${\displaystyle A}$ eine ${\displaystyle n\times n}$-Matrix mit ${\displaystyle A_{i,j}=|x_{i}-x_{j}|}$, welche also zu jedem Ausfahrtpaar die Entfernung angibt. Die Werte ${\displaystyle A_{i,j},1\leq i<j\leq n}$, seien so sortiert in einem Feld ${\displaystyle F}$ (der Multimenge) gegeben. Gesucht sind daraus die Werte ${\displaystyle x_{k}}$.

Per Backtracking kann eine Lösung für das Problem gefunden werden, indem zunächst immer der größte noch in ${\displaystyle 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 ${\displaystyle 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 den Werten ${\displaystyle x_{k}}$ in ${\displaystyle {\mathcal {O}}(n^{2})}$ zur Entfernungsmatrix ${\displaystyle A}$ kommen.