节点间存储成本

Question

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

房间数据结构(命名单元)：

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

行和列是单元格迷宫矢量中的位置，vector<Cell*> neighbors定义了该单元格与哪个单元格连接，状态保持单元格的状态(访问、空等)。

我尝试做的是创建一个单元格结构的属性，如：vector<int> cost，其中该数组的每个元素都与相邻元素匹配。

例如：

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

maze1的邻居向量是：

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的，等等。

我需要利用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;
};

这将保持成本和细胞的结合，不用担心。唯一的缺点是，您将每项成本存储两次(假设它是对称的)，但在许多其他方法(包括矩阵)中是正确的。