Toll problem

The toll problem ( English : Turnpike problem ) is a problem in theoretical computer science . You have a multitude of distances between the entrances and exits of a motorway. Can the position of the exits be constructed from these distances?

Somewhat more formal: Let there be positive numerical values ​​(the position of the exits starting at kilometer 0) and a matrix , which indicates the distance for each pair of exits. The values are given so sorted in a field (the multiset ). The values ​​are sought out of it . ${\displaystyle 0=x_{0}<x_{1}<\ldots <x_{n}}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle A_{i,j}=|x_{i}-x_{j}|}$ ${\displaystyle A_{i,j},1\leq i<j\leq n}$ ${\displaystyle F}$ ${\displaystyle x_{k}}$

A solution to the problem can be found using backtracking by first always taking the greatest distance value that is still available. The position of the new exit is tested recursively once with the position that is this distance away from the currently most left exit. If this branch does not lead to the goal, you will try the position from the exit furthest to the right. Under the position assumed in each case, a check is made to see whether the new distances between the existing and the new exit also occur in. If this is not the case, this recursion branch was a wrong path and the recursion is used to go back. ${\displaystyle F}$ ${\displaystyle F}$

In the worst case, the complexity is exponential, but in most cases, empirical studies show that it is significantly better.

Trivially, conversely, one can come from the values in to the distance matrix. ${\displaystyle x_{k}}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle A}$