尝试用 A* 解决大型迷宫时出现 SIGSEGV

问题描述 投票：0回答：2

我正在用 C++ 实现 A* 寻路算法来解决迷宫问题，但当迷宫尺寸较大（~10,000x10,000 或更大）时，我遇到分段错误 (SIGSEGV)。

错误发生在第 58 行调用 

~__shared_count()
后，
shared_ptr_base.h
中的 
node = queue.top()
函数，之后又调用了几十个 
~Node()
解构函数。

编辑：错误现在实际上发生在 

_Sp_counted_base<_S_atomic>::_M_release()
函数中，尽管我不知道我更改了什么。

以下是我的代码中应该相关的部分。我刚开始使用共享指针，所以我不太确定问题是什么或如何解决它。

主.cpp

#include <iostream>
#include <queue>
#include <random>
#include <vector>
#include <algorithm>
#include <stack>
#include <fstream>

#include "Node.hpp"

constexpr uint16_t maze_size = 10000;

void solve(const uint16_t start_x, const uint16_t start_y, const uint16_t goal_x,
           const uint16_t goal_y,
           const std::vector<std::vector<std::pair<bool, bool> > > &walls) {
    std::vector<std::vector<bool> > visited(maze_size, std::vector<bool>(maze_size, false));

    // Min heap for our queue
    std::priority_queue<Node, std::vector<Node>, std::greater<> > queue;

    Node node(start_x, start_y, goal_x, goal_y);

    visited[node.x][node.y] = true;

    while (!node.solved(goal_x, goal_y)) {
        // Add all valid neighbors to the queue
        {
            const auto x = node.x;
            const auto y = node.y;
            const auto ptr = std::make_shared<Node>(node);
            // Right
            if (x < maze_size - 1 && !walls[x][y].first && !visited[x + 1][y]) {
                queue.emplace(x + 1, y, goal_x, goal_y, ptr);
                visited[x + 1][y] = true;
            }
            // Left
            if (x > 0 && !walls[x - 1][y].first && !visited[x - 1][y]) {
                queue.emplace(x - 1, y, goal_x, goal_y, ptr);
                visited[x - 1][y] = true;
            }
            // Down
            if (y < maze_size - 1 && !walls[x][y].second && !visited[x][y + 1]) {
                queue.emplace(x, y + 1, goal_x, goal_y, ptr);
                visited[x][y + 1] = true;
            }
            // Up
            if (y > 0 && !walls[x][y - 1].second && !visited[x][y - 1]) {
                queue.emplace(x, y - 1, goal_x, goal_y, ptr);
                visited[x][y - 1] = true;
            }
        }
        node = queue.top();
        queue.pop();
    }
}

节点.hpp

#ifndef NODE_HPP
#define NODE_HPP

#include <cstdint>
#include <memory>

class Node {
public:
    uint16_t x, y;
    uint32_t steps;
    uint32_t value;

    std::shared_ptr<Node> parent;

    Node(const uint16_t x, const uint16_t y, const uint16_t goal_x, const uint16_t goal_y,
         const std::shared_ptr<Node> &parent = nullptr) : x(x), y(y), parent(parent) {
        steps = parent ? parent->steps + 1 : 0;
        value = abs(static_cast<int32_t>(goal_x) - static_cast<int32_t>(x)) +
                abs(static_cast<int32_t>(goal_y) - static_cast<int32_t>(y)) +
                steps;
    }

    [[nodiscard]] bool solved(const uint16_t goal_x, const uint16_t goal_y) const {
        return x == goal_x && y == goal_y;
    }

    // Overload the > operator for the priority queue
    bool operator>(const Node &rhs) const {
        if (value == rhs.value) {
            return steps < rhs.steps;
        }
        return value > rhs.value;
    }
};

#endif

Valgrind 输出

valgrind --leak-check=full ./Tests 
==5385== Memcheck, a memory error detector
==5385== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==5385== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==5385== Command: ./Tests
==5385== 
Maze loaded10000
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385== 
==5385== Process terminating with default action of signal 11 (SIGSEGV)
==5385==  Access not within mapped region at address 0x1FFE801FF8
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385==    at 0x116230: std::_Sp_counted_ptr_inplace<Node, std::allocator<void>, (__gnu_cxx::_Lock_policy)2>::_M_dispose() (shared_ptr_base.h:613)
==5385==  If you believe this happened as a result of a stack
==5385==  overflow in your program's main thread (unlikely but
==5385==  possible), you can try to increase the size of the
==5385==  main thread stack using the --main-stacksize= flag.
==5385==  The main thread stack size used in this run was 8388608.
==5385== 
==5385== HEAP SUMMARY:
==5385==     in use at exit: 239,026,864 bytes in 556,422 blocks
==5385==   total heap usage: 3,380,473 allocs, 2,824,051 frees, 374,594,816 bytes allocated
==5385== 
==5385== LEAK SUMMARY:
==5385==    definitely lost: 0 bytes in 0 blocks
==5385==    indirectly lost: 0 bytes in 0 blocks
==5385==      possibly lost: 0 bytes in 0 blocks
==5385==    still reachable: 239,026,864 bytes in 556,422 blocks
==5385==         suppressed: 0 bytes in 0 blocks
==5385== Reachable blocks (those to which a pointer was found) are not shown.
==5385== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5385== 
==5385== For lists of detected and suppressed errors, rerun with: -s
==5385== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

您可以尝试使用以下函数来加载此迷宫文件来重现错误。抱歉尺寸问题。您可以使用此功能加载它：

std::vector<std::vector<std::pair<bool, bool> > > readVectorFromFile(const std::string &filename) {
    std::vector<std::vector<std::pair<bool, bool> > > vec;
    std::ifstream inFile(filename, std::ios::binary);
    if (!inFile) {
        std::cerr << "Error opening file for reading: " << filename << std::endl;
        return vec;
    }

    // Read the size of the outer vector
    size_t outerSize;
    inFile.read(reinterpret_cast<char *>(&outerSize), sizeof(outerSize));

    vec.resize(outerSize);

    for (auto &innerVec: vec) {
        // Read the size of each inner vector
        size_t innerSize;
        inFile.read(reinterpret_cast<char *>(&innerSize), sizeof(innerSize));

        innerVec.resize(innerSize);

        // Read each pair in the inner vector
        for (auto &pair: innerVec) {
            inFile.read(reinterpret_cast<char *>(&pair.first), sizeof(bool));
            inFile.read(reinterpret_cast<char *>(&pair.second), sizeof(bool));
        }
    }

    inFile.close();
    return vec;
}

主要看起来像：

int main() {
    auto walls = readVectorFromFile("maze.dat");
    std::cout << "Maze loaded" << std::endl;

    solve(0, 0, maze_size - 1, maze_size - 1, walls);

    return 0;
}
c++ pointers segmentation-fault shared-ptr smart-pointers
2个回答
0
投票

在你的

Node
中，
std::shared_ptr<Node> parent;
并不是真正需要的，并且容易产生循环依赖，这显然发生在你的迷宫中（尽管我懒得确认这一点）。删除 
shared_ptr
并仅提供有关父节点的信息 
steps
:

class Node {
public:
    uint16_t x, y;
    uint32_t steps;
    uint32_t value;

    Node(uint16_t x, uint16_t y, uint16_t goal_x, uint16_t goal_y, int parentSteps = -1) : x(x), y(y) {
        steps = parentSteps + 1;
        value = abs(static_cast<int32_t>(goal_x) - static_cast<int32_t>(x)) +
                abs(static_cast<int32_t>(goal_y) - static_cast<int32_t>(y)) + steps;
    }

    [[nodiscard]] bool solved(const uint16_t goal_x, const uint16_t goal_y) const { return x == goal_x && y == goal_y; }

    // Overload the < operator for the priority queue
    bool operator>(const Node &rhs) const {
        if (value == rhs.value) {
            return steps < rhs.steps;
        }
        return value > rhs.value;
    }
};

然后你可以像这样创建新节点：

queue.emplace(x + 1, y, goal_x, goal_y, node.steps);
0
投票

您没有显式定义 

Node::~Node()
，但编译器为您做到了这一点。在那里，它调用 
std::shared_ptr<Node>::~shared_ptr
。反过来，这称为 
Node::~Node
。

这是一个递归调用。根据您的迷宫和查询，这可能会溢出调用堆栈。

更简单的解决方案是让

solve()
管理所有节点的所有权；每个节点只能有一个非拥有的 
Node* parent
。这种所有权可以像 
std::deque<Node>
一样简单（但不是 
std::vector<Node>
，因为这会重新分配并破坏 
Node* parent
）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.