节点之间的存储成本

Question

我正在使用统一成本搜索来制作迷宫解算器，基本上我想要做的是在我的迷宫中存储房间之间的随机成本。房间

数据结构（命名为细胞）：

struct Cell 
    { 
     int row; 
     int column; 
     vector<Cell*> neighbors; 
     State state; 
    }; 

行和列是在Cell的迷宫矢量的位置，vector<Cell*> neighbors定义了哪些小区这个特定单元连接到与状态保持一小区的状态（已访问，空白等）。

我所做的是制作Cell结构的属性，如下所示：vector<int> cost其中该数组的每个元素都与邻居元素相匹配。

例如：

0 ###### 
1 # ## 
2 # # # 
3 ###### 

迷宫[1] [1]在它的邻国矢量：

neighbors[0] = *maze[1][2]; 
neighbors[1] = *maze[2][1]; 

它的成本向量现在是：

cost[0] = 5; 
cost[1] = 10; 

但这种方式做这件事造成了很多问题。

我所想的是，我需要一个成本矩阵将一个节点匹配另一并存储在矩阵中的成本，这样的事情：

0 1 2 
0[0][2][4] 
1[2][0][6] 
2[4][6][0] 

但为了做到这一点我怎么会让我的矩阵知道哪个单元是哪个？如何取代0和1，我知道它是[0] [0] [0] [1] [0] [2]等。

我需要为这样的事情使用3D矢量吗？如果我这样做，我宁愿避免它，因为我对3D矢量经验不足。

Answer 1

难道你不能使用自定义对象来链接到另一个房间吗？例如：

struct Cell; 

struct CellLink { 
    const Cell *cell; 
    const int weight; 
    .. 
}; 

struct Cell { 
    int row; 
    int column; 
    vector<CellLink> neighbors; 
    State state; 
}; 

这将保持成本和细胞加上无后顾之忧。唯一的缺点是，你将存储每个成本两次（假设它是对称的），但在许多其他方法（包括矩阵）中都是如此。