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 で健全性チェックを行いました。Valgrindは、次Conditional 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

子ベクトルにローカル変数のアドレスを追加しています。

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 に答える
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 に答える