我正在使用统一成本搜索制作迷宫求解器,基本上我想做的是在迷宫中的房间之间存储随机成本。
房间(命名单元格)的数据结构:
struct Cell
{
int row;
int column;
vector<Cell*> neighbors;
State state;
};
行和列是Cell在迷宫 vector 中的位置,vector<Cell*> neighbors
定义此特定单元格连接到哪些单元格,状态保持单元格的状态(已访问、空等)。
我尝试做的是像这样创建 Cell 结构的属性:vector<int> cost
该数组的每个元素都与相邻元素匹配。
例如:
012345
0 ######
1 # ##
2 # # #
3 ######
maze[1][1] 在它的邻居 vector 中:
neighbors[0] = *maze[1][2];
neighbors[1] = *maze[2][1];
它的成本 vector 现在是:
cost[0] = 5;
cost[1] = 10;
但这种做法带来了很多问题。
我的想法是我需要一个成本矩阵,它将一个节点与另一个节点匹配并将成本存储在矩阵中,如下所示:
0 1 2
0[0][2][4]
1[2][0][6]
2[4][6][0]
但是为了做到这一点,我将如何让我的矩阵知道哪个单元格是哪个单元格?我如何让它知道它是 [0][0] [0][1] [0][2] 等而不是 0 和 1。
我需要为这样的事情使用 3D vector 吗?如果我这样做,我宁愿避免它,因为我对 3D vector 没有经验。
最佳答案
您不能使用自定义对象链接到另一个房间吗?例如:
struct Cell;
struct CellLink {
const Cell *cell;
const int weight;
..
};
struct Cell {
int row;
int column;
vector<CellLink> neighbors;
State state;
};
这将使成本和电池无后顾之忧。唯一的缺点是您将每个成本存储两次(假设它是对称的),但在许多其他方法(包括矩阵)中也是如此。
关于c++ - 节点之间的存储成本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20002882/