Turnpike Problem (F#)

The Problem

This is a problem for which no polynomial time solution exists, although a pseudo-polynomial (polynomial in the degree of the maximum element) does exist. In this paper, the algorithm proposed for the sum-function with full information is simple enough. For the original problem with the difference funcition, the algorithm is simple as well:

Problem. Given a set , reconstruct the original set . (Naturally, we can only consider positive deltas:
, the set is sorted in the descending order).

A simple algorithm exists. It performs in time, but in practice its performance is closer to , as it "probably" won't hit the worst case.

We first reduce our set to only positive values and assume they are sorted in the descending order.
Then the pseudocode will run as follows:

solution = [0; Da[0]]
max_element = Da[0]
remove (Da, Da[0])
while (Da not empty) {
   if solution = [0] return []
   if distances(solution.Add(Da[0]))  Da && not explored_this_path()
      remove(Da, distances)
   else if distances(solution.Add(max - Da[0]))  Da && not explored_this_path()
      remove(Da, distances)
   else
      backtrack(solution, Da)
}
return solution;

We start by adding 0 and the maximal element to the solution, and remove the latter from the Da. At every step, we have a new version of the solution and Da. We take to be the possible next element of the set . Then we compute pair-wise distances of the current sub-solution and see if they represent the subset of . If that fails – we then try the same way. If that fails as well, we backtrack to the previous state of the solution and previous , and keep backtracking until we reach a state, where not all of alternatives have been tried.

Once current Da is empty – we have a solution. If we have reached the root state and all alternatives have been tried – there is no solution.

Essentially, we are building a binary tree, where each node contains the current solution, current Da, and an edge connecting it with one or both of the alternatives above. Hopefully, we do not need to keep building this tree for too long. Here is a nice illustration of this process.

Note, that at every step we favor the remaining maximal element of as opposed to . Doing the latter would produce a symmetric solution.

F# Implementation

The source for this implementation is here

At every step, we keep building the following tree:

type DecisionTree =
    | Empty
    | TreeNode of deltas : Dictionary<int, int> * solution : int list * visited: uint32 * maxElem : DecisionTree * maxDist : DecisionTree * prev : DecisionTree 

Every node contains the current deltas, current state of the solution, the number of times we have visited this node (for optimization), two possible branches and a pointer to the parent node.

The function that implements the current algorithm:

let rec insert (deltas : Dictionary<int, int>) (res : int list) (node : DecisionTree) (prevNode : DecisionTree) maxSol =
    let insPrev () =
        let res, deltas, prevPrev = getPrev prevNode
        insert deltas res prevNode prevPrev maxSol

    match node with 
    | Empty -> TreeNode(deltas, res, 0u, Empty, Empty, prevNode)
    | TreeNode(dct, rslt, visited, maxElem, maxDist, prev) when visited < 2u ->
        let curVisited = visit node
        let elem = 
            if visited = 0u then keySeqMax deltas else maxSol - keySeqMax deltas
        let dists = stepOk elem res deltas
        if dists.Length > 0 then
            let newDeltas = removeDist deltas dists
            insert newDeltas (elem::res) (if visited = 0u then maxElem else maxDist) curVisited maxSol
        elif visited = 0u then
            insert deltas res curVisited prev maxSol
        else
            insPrev()
    | _ -> insPrev()

The insert function implements each step of the algorithm and returns a reference to the currently inserted node.
The driver is a loop, implemented, naturally as a tail-recursive function:

let rec buildSolution (deltas : Dictionary<int, int>) (res : int list) (node : DecisionTree) (prev : DecisionTree) =
    if deltas.Count = 0 then res |> List.sort
    else
        let newNode = insert deltas res node prev maxSol
        let prevNode = node
        match newNode with
        | Empty -> [] // no solution
        | TreeNode(deltas, res, visited, maxElem, maxDist, prev) ->
             if visited >=2u && prev = Empty then [] // came all the way back, no solution
             else
                 buildSolution deltas res newNode prevNode

This algorithm is biased towards always selecting the maximum remaining element from the Da as the next element in the solution. So, for an input set [2; 2; 3; 3; 4; 5; 6; 7; 8; 10], this algorithm produces [0; 3; 6; 8; 10]. Symmetrically, [0; 2; 4; 7; 10] is also a solution.