GNode findPath(g, a, b) //a为源点,b为目标点 g[a.row][a.col]=0 GNode here= new GNode(a.row, a.col, NULL) Q = Φ //活结点队列 while here != NULL or here !=b GNode[] childNodes = getChildNodes(here) for each n in childNodes if g[n.row][n.col]== -1 enQueue(Q, n) n.pNode = here g[n.row][n.col] = g[here.row][here.col]+1的后续代码怎么写,完善一下,他的功能是布线问题的队列分支限界伪代码
时间: 2024-02-13 11:05:11 浏览: 24
完善后的布线问题的队列分支限界伪代码如下:
```
// 定义布线问题节点的数据结构
struct GNode {
int row, col; // 当前节点所对应的网格行列坐标
GNode* pNode; // 指向父节点的指针
// 其他必要的数据成员和成员函数
};
// 定义布线问题的队列分支限界算法函数
GNode* findPath(int g[][M+1], GNode a, GNode b) {
g[a.row][a.col] = 0;
GNode* here = new GNode(a.row, a.col, NULL);
queue<GNode*> Q;
Q.push(here);
while (!Q.empty() && here->row != b.row && here->col != b.col) {
here = Q.front();
Q.pop();
GNode childNodes[3] = {GNode(here->row-1, here->col, NULL), GNode(here->row, here->col-1, NULL), GNode(here->row+1, here->col, NULL)};
for (int i = 0; i < 3; i++) {
GNode n = childNodes[i];
if (g[n.row][n.col] == -1) {
Q.push(&n);
n.pNode = here;
g[n.row][n.col] = g[here->row][here->col] + 1;
}
}
}
if (here->row == b.row && here->col == b.col) {
return here;
} else {
return NULL;
}
}
// 定义计算最短路径的函数
vector<GNode> shortestPath(int g[][M+1], GNode a, GNode b) {
vector<GNode> path;
GNode* p = findPath(g, a, b);
while (p != NULL) {
path.push_back(*p);
p = p->pNode;
}
reverse(path.begin(), path.end());
return path;
}
```
其中,`GNode` 结构体表示布线问题节点,`findPath` 函数用于搜索最短路径,`shortestPath` 函数用于计算最短路径。在 `findPath` 函数中,首先将起点的代价设为 0,将起点节点放入队列中,然后从队列中取出一个活结点,拓展它的子节点,并将子节点放入队列中。重复这个过程,直到找到布线终点,或者队列为空。如果找到布线终点,则返回终点节点的指针,否则返回空指针。在 `shortestPath` 函数中,将最短路径上的所有节点依次保存到一个 vector 中,然后将 vector 中的节点顺序反转,得到从起点到终点的最短路径。