使用BFS解决3D迷宫.如果在C ++中找到，如何获得到终点的完整的最短路径? [英] 3D Maze solving with BFS. How to get a full shortest path to the end point if found in C++?
问题描述
我正在尝试实施BFS算法，以检查在指定起始位置的3D迷宫中是否可以达到目标.迷宫是从txt文件导入的.我的解决方案似乎找到了目标，但是我无法仅显示所采取的路径.我的问题:我能够找到目标，但我不知道如何获得最短的路径并将其打印出来.我当时正在考虑使用父母/子女概念，但不确定是否可行.我希望我最终可以打印出这样的路径:(从起点到终点)
1 3 11 3 22 3 3 这是我的代码:
我使用struct来存储txt文件中的信息.
struct迷宫{int x，y，z;//方面int sx，sy，sz;//起点int ex，ey，ez;//出口点整数网格//迷宫中有可用动作的网格数vector< vector< int>>闪闪发光向量<对< int，对< int，int>>>gpoint;//可访问的(x，y，z)列表};void BFS(迷宫&迷宫，vector< pair< int，pair< int，int>>>结果){boolreach_end = false;int xx，yy，zz;int j = 0;int move_count = 0;int nodes_left_in_layer = 1;int nodes_in_next_layer = 0;队列< int>xq，yq，zq;xq.push(maze.sx); yq.push(maze.sy); zq.push(maze.sz);向量<对< int，对< int，int>>>Visited(maze.grids);visit.push_back(make_pair(xx，make_pair(yy，zz)));;result.push_back(make_pair(xx，make_pair(yy，zz)));;while(！xq.empty()){int xfront = xq.front(); int yfront = yq.front(); int zfront = zq.front();xq.pop(); yq.pop(); zq.pop();if(xfront == maze.ex& yfront == maze.ey&& zfront == maze.ez){reach_end = true;cout<<到达终点！"<< endl;休息;}int index = 0;索引= getindex(迷宫，xfront，yfront，zfront);//探索邻居for(j = 0; j< maze.glist [index] .size()-3; j ++){int动作= maze.glist [index] [3 + j];xx = xfront + dx [action-1];//dx，dy，dz是动作列表.yy = yfront + dy [action-1];zz = zfront + dz [action-1];自动p2 = make_pair(xx，make_pair(yy，zz));//跳过边界if(xx< 0 || yy< 0 || zz< 0){}否则if(xx> = maze.x || yy> = maze.y || zz> = maze.z){}否则if(find(visited.begin()，visited.end()，p2)！= visited.end()){cout<<"访问:<< xx<< yy<< zz<< endl;}否则if(find(maze.gpoint.begin()，maze.gpoint.end()，p2)！= maze.gpoint.end()){int index2 = getindex(maze，xx，yy，zz);xq.push(xx); yq.push(yy); zq.push(zz);visit.push_back(p2);nodes_in_next_layer ++;}别的{cout<<"不在glist中!!<< endl;}}nodes_left_in_layer--;if(nodes_left_in_layer == 0){nodes_left_in_layer = nodes_in_next_layer;nodes_in_next_layer = 0;move_count ++;}}如果(reach_end){cout<<" move_count:"<< move_count<< endl;cout<<" nodes_left_in_layer:"<< nodes_left_in_layer<< endl;cout<<" nodes_in_next_layer:"<< nodes_in_next_layer<< endl;}别的{cout<<" xxxFAILxxx"<< endl;}} 有2种常见方法:
-
您会记住每个访问的像元从起点开始的距离，然后当您找到终点时，您将沿着沿着每步减小距离的路径回到起点.当您可以对访问的顶点使用位压缩表示形式时，此方法可节省内存，因为您只需要记住距离的最低2位即可.这对您来说并不容易.
-
您可以直接记住每个访问过的单元格的前身，找到终点后，只需将所有这些链接追溯到起点即可.
您可能应该使用方法(2).
我建议您用 std :: unordered_map 替换当前效率非常低的 visited 向量，该向量将每个访问的顶点映射到其前任的索引./p>
I am trying to implement the BFS algorithm to check if a goal is reachable in a 3D maze given a starting position. The maze was imported from a txt file. My solution seems to find the goal however I am not able to display just the path that was taken. My issue: I am able to find the goal but I have no idea how to get the shortest path and print it out. I was thinking about using parents/children concept but I am not sure whether it works. I hope I can finally print out the path like this: (from start point to end point)
1 3 1
1 3 2
2 3 3
This is my code:
I use struct to store informations from txt file.
struct Maze
{
int x,y,z; //dimensions
int sx,sy,sz;//start point
int ex,ey,ez;//exit point
int grids; //number of grids in the maze where are actions available
vector<vector<int> > glist;
vector< pair<int, pair<int, int> > > gpoint; // list of (x,y,z) accessible
};
void BFS(Maze &maze,vector< pair<int, pair<int, int> > > result){
bool reach_end = false;
int xx,yy,zz;
int j=0;
int move_count = 0;
int nodes_left_in_layer = 1;
int nodes_in_next_layer = 0;
queue<int> xq,yq,zq;
xq.push(maze.sx);yq.push(maze.sy);zq.push(maze.sz);
vector< pair<int, pair<int, int> > > visited(maze.grids);
visited.push_back(make_pair(xx, make_pair(yy, zz)));
result.push_back(make_pair(xx, make_pair(yy, zz)));
while(!xq.empty()){
int xfront = xq.front();int yfront = yq.front();int zfront = zq.front();
xq.pop();yq.pop();zq.pop();
if(xfront==maze.ex && yfront==maze.ey && zfront==maze.ez){
reach_end = true;
cout << "reach end!" <<endl;
break;
}
int index=0;
index = getindex(maze,xfront,yfront,zfront);
//EXPLORE NEIGHBORS
for(j=0;j<maze.glist[index].size()-3;j++){
int action = maze.glist[index][3+j];
xx = xfront+dx[action-1]; // dx,dy,dz are lists of actions.
yy = yfront+dy[action-1];
zz = zfront+dz[action-1];
auto p2 = make_pair(xx,make_pair(yy,zz));
//skip bounds
if(xx<0 || yy<0 || zz<0){}
else if(xx >= maze.x || yy>= maze.y || zz >= maze.z){}
else if(find(visited.begin(),visited.end(),p2)!=visited.end()){
cout << "Visited: "<<xx <<yy<<zz<<endl;
}
else if(find(maze.gpoint.begin(),maze.gpoint.end(),p2)!=maze.gpoint.end()){
int index2 = getindex(maze,xx,yy,zz);
xq.push(xx);yq.push(yy);zq.push(zz);
visited.push_back(p2);
nodes_in_next_layer++;
}else{
cout<<"Not in glist!! "<<endl;
}
}
nodes_left_in_layer--;
if(nodes_left_in_layer==0){
nodes_left_in_layer = nodes_in_next_layer;
nodes_in_next_layer=0;
move_count++;
}
}
if(reach_end){
cout<< "move_count: " <<move_count<<endl;
cout << "nodes_left_in_layer: " <<nodes_left_in_layer<<endl;
cout << "nodes_in_next_layer: " <<nodes_in_next_layer<<endl;
}else{
cout<< "xxxFAILxxx " <<endl;
}
}
There 2 common ways:
You remember the distance of every visited cell from the start, and then when you find the end you walk back to the start, along the path that decreases distance with every step. This method is memory-efficient when you can use a bit-packed representation for visited vertexes, since you only need to remember the lowest 2 bits of the distance. This doesn't apply easily to you.
You directly remember the predecessor of every visited cell, and when you find the end you just follow all those links back to the start.
You should probably use method (2).
I suggest you replace your visited vector, which is currently very inefficient, with a std::unordered_map that maps each visited vertex to the index of its predecessor.
这篇关于使用BFS解决3D迷宫.如果在C ++中找到，如何获得到终点的完整的最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
