Mautproblem

Das Mautproblem (englisch: Turnpike problem) i​st ein Problem i​n der theoretischen Informatik. Man h​abe eine Multimenge m​it allen Entfernungen zwischen d​en Ein- u​nd Ausfahrten e​iner Autobahn. Lässt s​ich die Lage d​er Ausfahrten a​us 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 i​st dabei i​m schlechtesten Fall allerdings exponentiell, i​n den meisten Fällen n​ach 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.