c++ - 使用智能指针时递归函数中的段错误

Question

我在调用

时遇到段错误

auto n1=std::make_shared<Node>(n,n->x+i,n->y+j); 

经过几次递归调用。奇怪的是它总是在同一时间点。谁能发现问题？这是一个动态规划问题的实现，在这里我正在累积一条路径的成本。我已经简化了成本函数，但在这个例子中问题仍然存在。

void HorizonLineDetector::dp(std::shared_ptr<Node> n)
{
    n->cost= 1 + n->prev->cost;
    //Check if we reached the last column(done!)
    if (n->x==current_edges.cols-1)
    {
        //Save the info in the last node if it's the cheapest path
        if (last_node->cost > n->cost)
        {
            last_node->cost=n->cost;
            last_node->prev=n;
        }
    }
    else
    {
        //Check for neighboring pixels to see if they are edges, launch dp with all the ones that are
        for (int i=0;i<2;i++)
        {
            for (int j=-1;j<2;j++)
            {
                if (i==0 && j==0) continue;
                if (n->x+i >= current_edges.cols || n->x+i < 0 ||
                    n->y+j >= current_edges.rows || n->y+j < 0) continue;
                if (current_edges.at<char>(n->y+j,n->x+i)!=0)
                {
                    auto n1=std::make_shared<Node>(n,n->x+i,n->y+j);
                    //n->next.push_back(n1);
                    nlist.push_back(n1);
                    dp(n1);
                }
            }
        }
    }
}

---

class Node
{
    public:
        Node(){}
        Node(std::shared_ptr<Node> p,int x_,int y_){prev=p;x=x_;y=y_;lost=0;}
        Node(Node &n1){x=n1.x;y=n1.y;cost=n1.cost;lost=n1.lost;prev=n1.prev;}//next=n1.next;}
        std::shared_ptr<Node> prev;             //Previous and next nodes
        int cost;               //Total cost until now
        int lost;               //Number of steps taken without a clear path
        int x,y;
        Node& operator=(const Node &n1){x=n1.x;y=n1.y;cost=n1.cost;lost=n1.lost;prev=n1.prev;}//next=n1.next;}
        Node& operator=(Node &&n1){x=n1.x;y=n1.y;cost=n1.cost;lost=n1.lost;prev=n1.prev;n1.prev=nullptr;}//next=n1.next;n1.next.clear();}
};

Answer 1

您的代码看起来像病态路径搜索，因为它几乎检查每条路径并且不跟踪它已经检查过的路径，您可以获得不止一种方法。

这将构建等于最长路径长度的递归深度，然后是下一个最长路径，然后...向下到最短路径。即，类似于 O(# of pixels)深度。

这很糟糕。而且，由于调用堆栈深度有限，会使您崩溃。

简单的解决方案是将 dp 修改为 dp_internal，并让 dp_internal 返回节点的 vector处理下一步。然后编写 dp，它调用 dp_internal 并重复其返回值。

std::vector<std::shared_ptr<Node>>
HorizonLineDetector::dp_internal(std::shared_ptr<Node> n)
{
  std::vector<std::shared_ptr<Node>> retval;

...

            if (current_edges.at<char>(n->y+j,n->x+i)!=0)
            {
                auto n1=std::make_shared<Node>(n,n->x+i,n->y+j);
                //n->next.push_back(n1);
                nlist.push_back(n1);
                retval.push_back(n1);
            }

...

  return retval;
}

然后 dp 变成:

void HorizonLineDetector::dp(std::shared_ptr<Node> n)
{
  std::vector<std::shared_ptr<Node>> nodes={n};
  while (!nodes.empty()) {
    auto node = nodes.back();
    nodes.pop_back();
    auto new_nodes = dp_internal(node);
    nodes.insert(nodes.end(), new_nodes.begin(), new_nodes.end());
  }
}

但是 (A) 当排队节点的数量变得异常大时，这可能会崩溃，并且 (B) 这只是对递归导致崩溃的补丁，不会让你的算法变得更糟。

---

使用 A*。

这涉及跟踪您访问过哪些节点以及下一步要处理哪些节点及其当前路径成本。

然后，您可以使用试探法来确定您应该首先检查接下来要处理的那些。如果您在某种网格上，启发式方法是在没有任何阻碍的情况下使用尽可能短的距离。

加上到达节点到进程的成本，加上从该节点到目的地的启发式距离。找到总计最少 的节点到进程。处理那个:您将其标记为已访问，并将其所有相邻节点添加到要处理的节点列表中。

切勿将节点添加到节点列表中以处理您已经访问过的节点(因为这是多余的工作)。

一旦您有了解决方案，修剪节点列表以针对当前路径值大于或等于您的解决方案的任何节点进行处理。如果您知道您的启发式算法很强(不可能更快到达目的地)，您甚至可以根据启发式算法和当前成本的总和进行修剪。同样，不要添加到要处理的节点列表中，如果它会被本段修剪。

结果是您的算法在一条相对狭窄的线上搜索目标，然后向外扩展，试图找到绕过任何障碍的方法。如果有一条相对直接的路线，就会使用它，甚至不会触及宇宙的其余部分。

您可以对 A* 进行许多优化，甚至还有不依赖启发式的替代解决方案。但是从 A* 开始。