1

我正在编写一些代码，用于在 C++ 中使用 BFS 搜索迷宫（我的主要语言是 Python，但我想稍微锻炼一下我的 C++ 大脑......），我偶然发现了这个奇怪的错误。

以下是相关的数据结构：

struct Maze {
  std::pair<int, int> start;
  std::pair<int, int> goal;
  std::pair<int,int> dims;
  std::set<std::pair<int, int> > passable;
};

struct SearchNode {
  std::pair<int, int> cell;
  Maze* pMaze;
  SearchNode* parent;
  std::vector<SearchNode*> children;
};

假设我已经有了一个void parseFile(Maze* maze, char* filename)读取迷宫文本文件的方法，存储起始和目标方块的 (row, col) 对以及对应于“可通过”的 (row, col) 对的集合在迷宫中。

还有一些其他功能：

bool isPassable(Maze* maze, std::pair<int,int> testCell);
std::vector<SearchNode*> getPassableChildren(SearchNode sn);
void mazeSearch(Maze* maze);

以下是它们的实现：

// <...snip...>
inline bool isPassable(Maze* maze, std::pair<int,int> cell) {
  return maze->passable.find(cell) != maze->passable.end();
}


std::vector<SearchNode*> getPassableChildren(SearchNode sn) {
  // Store a cached copy of the children, so if we require multiple queries
  // we do not have to re-compute children.
  if(sn.children.empty()) {
    Maze* mazePointer = sn.pMaze;
    int r = sn.cell.first;
    int c = sn.cell.second;
    for(int i = 0; i <= 2; ++i) {
      for(int j = 0; j <= 2; ++j) {
        if (!(i == 1 && j == 1)) {
          std::pair<int,int> childCell(r+i-1, c+j-1);

          if(isPassable(mazePointer, childCell)) {
            // Build child SN
            SearchNode child;
            child.cell = childCell;
            child.parent = &sn;
            child.pMaze = mazePointer;
            sn.children.push_back(&child);
          }
        }
      }
    }
  }
  return sn.children;
}

void mazeSearch(Maze* maze) {
  std::set<std::pair<int,int> > visited;
  std::deque<SearchNode> workQueue;

  // Create root node.
  SearchNode root;
  root.cell = maze->start;
  root.parent = NULL;
  root.pMaze = maze;

  workQueue.push_back(root);
  visited.insert(root.cell);

  while(!workQueue.empty()) {
    SearchNode sn = workQueue.front();
    workQueue.pop_front();

    for(SearchNode* passableNeighbor : getPassableChildren(sn))  {
      // THIS IF-STATEMENT IS BROKEN
      if(passableNeighbor->cell.first == maze->goal.first &&
         passableNeighbor->cell.second == maze->goal.second) {
        printf("Found a path.\n");
        return;
      }
      // Check to make sure it is not in our visited set.
      // THIS STATEMENT IS ALSO BROKEN
      if (visited.find(passableNeighbor->cell) == visited.end()) {
        workQueue.push_back(*passableNeighbor);
        visited.insert(passableNeighbor->cell);
      }
    }
  }
  printf("No path found.\n");
}
// <...snip...>

该代码在 GCC 4.6.3 下编译良好：$g++ maze.cc -g -std=c++0x 但是，$./a.out smallMaze.txt产生

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

我已经对 Valgrind 和 GDB 进行了一些健全性检查：ValgrindConditional jump or move depends on uninitialised value(s)在开头的那一行中指出

if(passableNeighbor->cell.first == maze->goal.first

以及附近进行设置查找的线路，

if(visited.find(passableNeighbor->cell) == visited.end())

当我在 GDB 中检查这些 passableNeighbor 指针时，看起来底层的 SearchNode 对象没有正确初始化它的子单元格，并且出现了各种奇怪的值。我怀疑这与我对 C++ 如何分配对象缺乏了解有关。

所以很明显，潜在的问题是 passableNeighbor 对象以某种方式在其中包含损坏的数据。这是我如何编写 getPassableChildren() 方法的产物吗？还有其他想法吗？

我查看了 std::bad_alloc ，似乎这个异常通常与内存不足有关，但是我在 BFS 期间扩展的第一个节点上遇到了这个错误，所以我似乎极不可能达到任何内存限制。

4

2 回答 2

1

这部分有问题

      if(isPassable(mazePointer, childCell)) {
        // Build child SN
        SearchNode child;
        child.cell = childCell;
        child.parent = &sn;
        child.pMaze = mazePointer;
        sn.children.push_back(&child);
      }

children因为它用指向局部变量的指针填充。当您离开 if 语句时，所有指针都无效。

如果你child在这里创建一个新的，你最好存储它的值而不是存储一个指针。

于 2012-09-05T18:39:41.313 回答
1

您正在向子向量添加局部变量的地址，这是一个很大的禁忌

SearchNode child;
child.cell = childCell;
child.parent = &sn;
child.pMaze = mazePointer;
sn.children.push_back(&child);

使用某种分配方式，或者让你的孩子成为vector<SearchNode>

例如：

SearchNode *child = new SearchNode();
child->cell = childCell;
child->parent = &sn;
child->pMaze = mazePointer;
sn.children.push_back(child);

然后你需要稍后清理它，或者制作你的向量vector<unique_ptr<SearchNode>>并继续前进，unique_ptr<SearchNode>(child)并且将为你完成取消分配

于 2012-09-05T18:40:21.107 回答