个性化阅读
专注于IT技术分析

使用回溯算法解决收费公路重建问题,JavaScript算法设计

从左到右排列,可设x1=0,di=|xi – xj|,其中i不等于j,di表示每一个点对对应一个距离值,这样n个点一共有k=n(n-1)/2个距离值。需要求解的问题是:已知k个距离值,反求出n个x坐标值(x1可设为0)。

回溯算法:使用回溯算法首先是找出并构建解的状态空间树,在状态空间树上执行DFS,并进行适当的剪枝操作。其中回溯算法一个比较明显的想法是,一个个试,也就是每种情况都需要考虑,基于这个想法,可得到如下使用回溯算法解决收费公路重建问题的步骤:

  1. 给定距离集D(不妨设D已排序),求解坐标集P,x1可确定为0,xn可确定为D中的最大值。
  2. 接下来确定xn-1,如何确定呢?取出D中未使用的最大值m,将m与P中已知的坐标求解距离d,若D中存在d,则可得到xn-1的值为m。
  3. 确定xn-2也是类似的2中的步骤,但是当在确定xn-2的时候,取出的m不符合要求的话,则需要取下一个最大值进行尝试。
  4. 如果在确定xi的时候尝试D中的所有未使用值都不符合要求,那么需要回退到上一层,例如,确定xn-2的时候,使用D中的所有未使用值都不行,那么需要回退到xn-1,此时将xn-1的值从P中删除,尝试下一个最大值。

下面是使用JavaScript实现的回溯算法解决收费公路重建问题的代码:

// 回溯算法:收费公路重建问题
function setValueState(D, T, dist, state){
    for(var i = 0;i < D.length;i++)
        if(state){
            if(D[i] == dist && !T[i]){
                T[i] = state;
                break;
            }
        }
        else{
            if(D[i] == dist && T[i]){
                T[i] = state;
                break;
            }
        }
}

function isContainInD(D, T, dist){
    var result = false;
    for(var i = 0;i < D.length;i++)
        if(D[i] == dist && !T[i]){
            result = true;
            break;
        }
    return result;
}

function PisFull(P){
    for(var i = 0;i < P.length;i++)
        if(P[i] == -1)
            return false;
    return true;
}

function DisEmpty(T){
    for(var i = 0;i < T.length;i++){
        if(!T[i])
            return false;
    }
    return true;
}

function dfs(D, P, T, index){
    if(PisFull(P) && DisEmpty(T))
        return true;
    var dist = 0;
    var flag = true;
    for(var k = D.length - 1;k >= 0;k--){
        if(T[k] || D[k] >= P[index + 1] || D[k] == dist)
            continue;
        dist = D[k];
        for(var i = 0;i < P.length;i++){
            if(P[i] != -1){
                var point = P[i];
                var dp = Math.abs(point - dist);
                if(isContainInD(D, T, dp)){
                    setValueState(D, T, dp, true);
                }
                else{
                    flag = false;
                    break;
                }
            }
        }
        if(!flag){
            for(var j = i - 1;j >= 0;j--){
                if(P[j] != -1){
                    var point = P[j];
                    var dp = Math.abs(point - dist);
                    setValueState(D, T, dp, false);
                }
            }
            flag = true;
            continue; // 剪枝:当前发现不符合马上跳过
        }

        P[index] = dist;
        var result = dfs(D, P, T, index - 1); // DFS

        if(!result){
            // 回溯处理:继续尝试下一个路径
            P[index] = -1;
            for(var i = 0;i < P.length;i++){
                if(P[i] != -1){
                    var point = P[i];
                    var dp = Math.abs(point - dist);
                    setValueState(D, T, dp, false);
                }
            }
        }
        else
            return true; // 有一个解立即返回
    }
    return false;
}

function turnpike(D, P){
    var T = new Array(D.length);
    for(var i = 0;i < T.length;i++)
        T[i] = false;
    P[0] = 0;
    P[P.length - 1] = D[D.length - 1];
    T[D.length - 1] = true;
    return dfs(D, P, T, P.length - 2);
}


// 例子1:自定义距离集
var n = 6;
var D = [1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10];
var P = new Array(6);
for(var i = 0;i < P.length;i++)
    P[i] = -1;
var r = turnpike(D, P);

function print(r, P){
    if(r){
        var str = "";
        for(var i = 0;i < P.length;i++)
            str += "[" + i + " " + P[i] + "]  ";
        console.log(str);
    }
    else
        console.log("the problem has no solution.");
    
}

print(r, P);

console.log("");

function compare(a, b){
    if(a > b)
        return 1;
    else if(a < b)
        return -1;
    else
        return 0;
}

// 例子2:根据存在的点集生成距离集
function generate(set, D){
    D.length = 0;
    var k = 0;
    for(var i = 0;i < set.length;i++){
        for(var j = i+1;j < set.length;j++)
            D[k++] = Math.abs(set[i] - set[j]);
    }
    D.sort(compare);
    console.log("D length: " + D.length);
    var str = "";
    for(var i = 0;i < D.length;i++){
        str += D[i] + " ";
    }
    console.log(str);
}

n = 8;
var set = [0, 2, 8, 16, 23, 31, 33, 39];
generate(set, D);
console.log("");

// 使用正确的距离集进行测试:结果可能和预定的点集不一样,表示一个距离集可能有多个解
var NP = new Array(n);
for(var i = 0;i < NP.length;i++)
    NP[i] = -1;
var r = turnpike(D, NP);
print(r, NP);
赞(0)
未经允许不得转载:srcmini » 使用回溯算法解决收费公路重建问题,JavaScript算法设计

评论 抢沙发

评论前必须登录!