Перебрать все потенциальные начальные позиции в алгоритме Хельд-Карпа, используя битовую маску.

Question

Меня интересует реализация алгоритма удерживаемого карпа на основе реализации C, найденной здесь: https://www.math.uwaterloo.ca/~bico/papers/comp_chapterDP.pdf в javascript. Однако в этой реализации используется только одна начальная позиция. Я пробовал множество методов для перемещения через все начальные позиции (все узлы в графе), однако, поскольку реализация использует битовую маску в качестве набора посещенных узлов, начальные позиции 1 и 0 не будут меняться при каждом вызове функции решения, потому что 0 & anynumber всегда будет 0.

function tsp_hk(dist){
    let n = dist.length;
    let opt = []; //array [endPoint][set] representing the optimum paths
    //Initialize array values
    for(let i = 0; i < n; i++){
        opt[i] = [];
        opt[i][1 << (i)] = dist[i][n-1];
    }

    function solve(set, end){
        if(opt[end][set] === undefined){
            let R = set & ~(1 << end);
            let minv = 99999;
            for (let i = 0; i < n; i++){
                if(!(R & (1 << i))) continue;
                let s = solve(R, i);
                let v = s + dist[i][end];
                if(v < minv) minv = v;
            }
            opt[end][set] = minv;
        }
        return opt[end][set];
    }
    let bestlen = 99999;  
    let N = (1 << (n-1))-1;
    for(let t = 0; t < n-1; t++){
        let s = solve(N,t);
        let len = s + dist[t][n-1];
        if(len < bestlen) bestlen = len;
    }

    return bestlen;
}

Answer 1

Если первый узел - это узел 0 и вы хотите, чтобы узел 2 был вашим начальным узлом, тогда просто поменяйте местами строку 0 и строку 2, а также столбец 0 и столбец 2. Измените матрицу смежности вместо изменения алгоритма.