Проблема платных дорог

Проблема потери ( английский : проблема шлагбаума ) является проблемой в теоретической информатике . У вас есть множество расстояний между въездами и съездами с автострады. Можно ли с этих расстояний построить положение выходов?

Несколько более формально: Пусть положительные численные значения (позиция из выходов , начиная с 0 км) и в матрице , которая указывает расстояние для каждой пары выходов. Значения даются отсортированными в поле ( мультимножество ). Ценности ищутся в нем . ${\ displaystyle 0 = x_ {0} <x_ {1} <\ ldots <x_ {n}}$${\ displaystyle A}$${\ Displaystyle п \ раз п}$${\ displaystyle A_ {i, j} = | x_ {i} -x_ {j} |}$${\ Displaystyle A_ {я, j}, 1 \ leq я <j \ leq n}$${\ displaystyle F}$${\ displaystyle x_ {k}}$

Решение проблемы можно найти , используя откаты сначала всегда принимает наибольшее значение расстояния, которое по- прежнему доступны. Положение нового выхода проверяется рекурсивно один раз с положением, которое находится на этом расстоянии от самого левого выхода в данный момент. Если эта ветка не ведет к цели, попробуйте позицию от самого дальнего вправо выхода. В соответствии с положением, предполагаемым в каждом случае, выполняется проверка, появляются ли новые расстояния между существующим и новым выходом . Если это не так, то эта ветвь рекурсии была неправильным путем, и рекурсия используется для возврата. ${\ displaystyle F}$${\ displaystyle F}$

В худшем случае сложность экспоненциальна, но в большинстве случаев эмпирические исследования показывают, что это значительно лучше.

Тривиально, наоборот, можно перейти от значений в матрицу расстояний . ${\ displaystyle x_ {k}}$${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$${\ displaystyle A}$