algorithm - 人在约束条件下从源头移动到目的地

Question

考虑这个笛卡尔图，其中每个索引代表一个权重。

[3, 2, 1, 4, 2

1, 3, 3, 2, 2

S、3、4、1、D

3, 1, 2, 4, 3

4, 2, 3, 1, 4]

一个人站在源头“S”，他必须以最小的成本到达目的地“D”。约束是:

1. 如果人从一个索引移动到另一个索引，其中两个索引共享相同的成本，则移动人的成本为“1”。

2. 如果人从一个索引移动到另一个索引，两个索引的成本不同，移动人的成本是 abs(n-m)*10 + 1。

3. 最后但同样重要的是，人只能上下左右移动。没有对角线移动。

哪种数据结构和算法最适合这个问题。我曾考虑将此问题表示为图表并使用其中一种贪心方法，但无法在我的脑海中找到干净的解决方案。

Answer 1

我会使用 A* 来解决问题。距离可以通过 dx + dy + 10 * dValue + 行进距离来估算(路径不可能比这更短，请参见底部的示例)。 A* 的思想是总是扩展估计距离最小的节点，一旦找到目标节点就完成了。如果估计从不高估距离，则此方法有效。这是 JS ( fiddle ) 中的一个实现:

function solve(matrix, sRow, sCol, eRow, eCol) {
    if (sRow == eRow && sCol == eCol)
        return 0;
    let n = matrix.length, m = matrix[0].length;
    let d = [], dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    for (let i = 0; i < n; i++) {
        d.push([]);
        for (let j = 0; j < m; j++)
            d[i].push(1000000000);
    }
    let list = [[sRow, sCol, 0]];
    d[sRow][sCol] = 0;
    for (;;) {
        let pos = list.pop();
        for (let i = 0; i < dirs.length; i++) {
            let r = pos[0] + dirs[i][0], c = pos[1] + dirs[i][1];
            if (r >= 0 && r < n && c >= 0 && c < m) {
                let v = d[pos[0]][pos[1]] + 1 + 10 * Math.abs(matrix[pos[0]][pos[1]] - matrix[r][c]);
                if (r == eRow && c == eCol)
                    return v;
                if (v < d[r][c]) {
                    d[r][c] = v;
                    list.push([r, c, v + Math.abs(r - eRow) + Math.abs(c - eCol) + 10 * Math.abs(matrix[r][c] - matrix[eRow][eCol])]);
                }
            }
        }
        list.sort(function(a, b) {
            if (a[2] > b[2])
                return -1;
            if (a[2] < b[2])
                return 1;
            return 0;
        });
    }
}

示例的答案是 46，只有 8 个节点正在扩展!

估计示例，从 (0,0) 到 D:

• 从 S 到 (0,0) 的距离是 22
• dx = abs(0 - 4) = 4
• dy = abs(0 - 2) = 2
• dValue = abs(3 - 1) = 2
• 估计 = 距离 + dx + dy + 10 * dValue = 22 + 4 + 2 + 10 * 2 = 48

注意:实现使用行和列而不是 x 和 y，因此它们被交换，这并不重要，只要保持一致即可。