1
私はこの特定のパスを見つけるための再帰的実装を書いています。これは、psuedocodeを使ってn * n行列を求めました。直後の呼び出し元に再帰関数が返されない
- (マトリックスにおける隣接セルに対するセルマトリックス)他に私達のグラフの一つの頂点から立ち上がりエッジ値を保持するパス重みアレイ
- 我々のパス内の各インデックスの隣接配列:私は、2つの配列を構築しましたウェイト配列
何らかの理由で私の再帰関数が返されたときに直前の呼び出し元に戻らないのですか?
私の実装:次の行
// find paths of specific length from our starting cell 1,1
// when a path is found print it
// otherwise return?
function findPaths(adjMatrix, pathW_array, path, pathWeight, x, y, idx, curpath_idx){
// set curpath to the current path (an array with storing path weight values)
var curpath = path;
// tempArray with store pathW_array (set cell value to -1 if value has been added to curpath)
var tempArray = pathW_array;
// curValue retruns sum value of our curpath
if ((curValue(curpath) == pathWeight) && (Object.keys(curpath).length !=1)){
for(i = 0; i < Object.keys(curpath).length; i++){
console.log(curpath[i]);
}
return;
}if(tempArray[x][y] == -1){
return;
}if(curValue(curpath) > pathWeight){
return;
}
// Did not return, add current cell value to curpath array
curpath[curpath_idx] = tempArray[x][y];
curpath_idx = curpath_idx + 1;
// set current cell value in tempArray to -1 because we've added it to current path (do not want to add same cell value multiple times)
tempArray[x][y] = -1;
// iterate until i = pathWeight -1
for(var i = 0; i < pathWeight; i++){
if(adjMatrix[idx][i] != -1){
// get pathW_array indices for next neighbor cell of current element
arrayIndices = neighbor_value(adjMatrix, tempArray, idx);
x = arrayIndices[0];
y = arrayIndices[1];
adjMatrix[idx][i] = -1;
idx = adjMatrix_idx(x,y);
// findpaths from the next cell in the matrix
findPaths(adjMatrix, tempArray, curpath, pathWeight, x, y, idx, curpath_idx);
curpath.pop();
curpath_idx = curpath -1;
}
}
}