制限付きソースから宛先への移動

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（NM）*少なくとも10 + 1

3. 最終ないが、両方のインデックスが異なるコストを有する別のインデックス1つのインデックスから移動した場合上に移動する、下に移動する、&右。対角線移動はありません。

どのデータ構造&アルゴリズムがこの問題に最も適しているか。私はこの問題をグラフとして表現し、貪欲なアプローチの1つを使用することを考えましたが、私の心の中では解決策には達しませんでした。

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に：（ - 4 0）= 4

DYのSから

• 距離（0,0）22
• DX = ABSであります= ABS（0から2）= 2
• dValue = ABS（3 - 1）= 2
• 推定=距離+ DX + DY + 10 * dValue = 22 + 4 + 2 + 10 * 2 = 48

注：インプリメンテーションでは、xとyのinstedの行と列が使用されているため、スワップされていても問題はありません。

Answer 2

明示的には述べられていませんが、問題の定式化では、正のノード重みのみが存在するように見えます。つまり、最短パスはノードの繰り返しを持ちません。コストはノードのみに依存しないので、Bellman-FordアルゴリズムまたはDijkstraアルゴリズムによるアプローチは適切ではありません。

言い換えれば、明らかに、パスは現在、スタックに出現しているノードがアクセスされないdepth-first searchを使用して再帰的に見つけることができます。目的地に達するたびに、現在の経路（目的地に達するたびにスタックに含まれる）と補助変数で維持できる関連コストが、以前に発見された最良の経路と比較して評価されます。終了時に、最小コストのパスが保存されます。