0

ロボットが障害物のあるn*nグリッド（必要に応じて迷路）を探索するためのアルゴリズムが必要です。目標は、障害物のないすべての正方形を探索し、障害物のある正方形を避けることです。秘訣は、障害物がロボットにその経路を変更させ、障害物の背後にある可能性のある自由な正方形を見逃すことです。ロボットのx/y座標をゆっくりとインクリメント/デクリメントして、障害物がなく、ロボットが他の自由な正方形に到達するために（必要に応じて）事前に確認されたパスを通過できる場合に、ロボットを4つの方向のいずれかに移動させることができます。 。すべてのフリースクエアが少なくとも1回満たされると、アルゴリズムは終了する必要があります。

これを行うための簡単な怠惰な/効率的な方法はありますか？擬似コードは大歓迎です

4

3 に答える 3

1

未踏の隣人のリストを保管してください。リストのどのフィールドを次に訪問するかについての巧妙なヒューリスティックを使用して、必要に応じてより効率的にすることができます。

擬似コード（スタックを使用して、DFSをもたらす未探索のネイバーを追跡します）：

// init
Cell first_cell;
CellStack stack;
stack.push(first_cell);

while(!stack.isEmpty()) {
    Cell currentCell = stack.pop();
    currentCell.markVisisted();
    for(neighbor in currentCell.getNeighbors()) {
        stack.push(neighbor);
    }
}
于 2012-07-19T07:29:39.047 に答える
1

この問題は巡回セールスマン問題から軽減できると思います。したがって、NP困難であるため、問題を最適かつ効率的に解決する多項式の解を見つけることはほとんどありません。

ただし、TSPのヒューリスティックと近似のいくつかを採用することをお勧めします 。問題はそもそもTSPに非常に近いように見えるため、これらもこの問題に適応できると思います。

編集：

最短パスを見つける必要がなく、任意のパスが必要な場合は、訪問先セットを維持する単純なDFSで実行できます。DFSのステップでは、再帰から戻ります。前の正方形に移動します。これにより、すべての正方形へのパスがある場合、ロボットはすべての正方形を確実に探索できます。

DFSの擬似コード：

search(path,visited,current):
   visited.add(current) 
   for each square s adjacent to current:
      if (s is an obstacle): //cannot go to a square which is an obstacle
         continue
      if (s is not in visited): //no point to go to a node that was already visited
         path.add(s) //go to s
         search(path,visited,current) //recursively visit all squares accesable form s
         //step back from s to current, so you can visit the next neighbor of current.
         path.add(current)

で呼び出すsearch([source],{},source)

ステップの前に最適化ヒューリスティックを使用できることに注意してくださいfor each。ヒューリスティックは、ノードの反復順序を並べ替えるだけです。

于 2012-07-19T07:53:40.703 に答える
0

問題を解決する最善の方法は再帰的だと思います（最も近いフリーセルに移動します）。次の追加のヒューリスティックを使用して：最小の空き隣接セルがある最も近い空きセルに移動します（スタブを優先します）。

擬似コード：

// init:
for (cell in all_cells) {
    cell.weight = calc_neighbors_number(cell);
}

path = [];

void calc_path(cell)
{
    cell.visited = true;
    path.push_back(cell);
    preferred_cell = null;
    for (cell in cell.neighbors)
        if (cell.visited) {
            continue;
        }
        if (preferred_cell == null || preferred_cell.weight > cell.weight)
           preferred_cell = cell;
    }
    if (preferred_cell != null) {
        calc_path(preferred_cell);
    }
}

// Start algotithm:
calc_path(start);
于 2012-07-19T08:19:34.417 に答える