以下代码是关于实时搜索邻居的。将新节点添加到我的图形后,将立即调用此节点的函数updateSeqNeighbours。我所知道的是,新节点肯定是最后添加的节点的邻居。在下一步中,我将使用此事实查找先前添加的节点的邻域,找到最接近新节点的邻域,然后在该邻域中搜索最邻近的邻域。

我仅重复3次,以将一个节点的邻居数限制为4,以保持恒定的时间范围进行计算。它的工作原理很棒,除了在大约30个节点之后,计算时间随着每个其他节点的增加而迅速增加,从而导致bad_alloc异常。

#ifndef GRAPH_NODE_H_
#define GRAPH_NODE_H_

#include <vector>
#include <cmath>

#include <iostream>

using namespace std;

class Node {
public:
    double x;
    double y;

    Node* nodePrev;

    vector<Node> seqNeighbours;

    //Constructor
    Node();
    Node(double x, double y);
    virtual ~Node();

    //Operator functions
    Node& operator=(const Node& n);

    //Get&Set
    int getID();

    //Public member functions
    void addNeighbour(Node& n);

    bool isSeqNeighbour(int ID);

    int updateSeqNeighbours();

    double distanceTo(Node& n);

private:
    static int count;
    int ID;

    void _setDefaults();
};

int Node::count = 0;

Node::Node() {
    _setDefaults();
}

Node::Node(double x, double y) {
    _setDefaults();
    this->x = x;
    this->y = y;
}

Node::~Node() {
    // TODO Auto-generated destructor stub
}

//Operator functions
Node& Node::operator=(const Node& n) {
    if (this != &n) {
        ID = n.ID;
            x = n.x;
            y = n.y;
        seqNeighbours.clear();
        seqNeighbours = n.seqNeighbours;
        nodePrev = n.nodePrev;
    }
    return *this;
}

//Get&Set
int Node::getID() {
    return this->ID;
}

//Public member functions
void Node::addNeighbour(Node& n) {
    seqNeighbours.push_back(n);
}

double Node::distanceTo(Node& n) {
    return sqrt((n.x-x)*(n.x-x) + (n.y-y)*(n.y-y));
}

bool Node::isSeqNeighbour(int ID) {
    for (int i = 0; i < seqNeighbours.size(); i++) {
        if (seqNeighbours[i].getID() == ID) {
            return true;
        }
    }
    return false;
}

int Node::updateSeqNeighbours() {
    if (nodePrev == NULL) {
        return 1;
    } else {
        Node seed = *nodePrev;  //previous node as seed
        seqNeighbours.push_back(seed);

            for (int i = 0; i < 3; i++) {
                    if (seed.nodePrev == NULL) break;
                    double minDist = 15353453;
                    Node closest;
                    for (int j = 0; j < seed.seqNeighbours.size(); j++) {
                            double dist = distanceTo(seed.seqNeighbours[j]);
                            if (dist < minDist) {
                                    minDist = dist;
                                    closest = seed.seqNeighbours[j];
                            }
                    }
                    if (minDist < 150) {
                            seqNeighbours.push_back(closest);
                    }
                    seed = closest;
            }
            cout << "neighbours = " << seqNeighbours.size() << endl;
    }
    return 0;
}

void Node::_setDefaults() {
    x = 0;
    y = 0;
    ID = count;
    nodePrev = NULL;
    seqNeighbours.clear();
    count++;
}
#endif /* GRAPH_NODE_H_ */

图形:
#ifndef GRAPH_GRAPH_H_
#define GRAPH_GRAPH_H_

#include <vector>
#include <iostream>
#include "Node.h"

using namespace std;

class Graph {
public:
    Graph();
    virtual ~Graph();

    vector<Node> list;

    void addNode(Node& n);
    void addSeqNode(Node& n);


private:
    void _setDefaults();
};

Graph::Graph() {
    // TODO Auto-generated constructor stub

}

Graph::~Graph() {
    // TODO Auto-generated destructor stub
}

void Graph::addNode(Node& n) {
    list.push_back(n);
}

void Graph::addSeqNode(Node& n) {
    if (!list.empty()) {
        n.nodePrev = &list.back();
    }
    n.updateSeqNeighbours();
    list.push_back(n);
}

void Graph::_setDefaults() {
    list.clear();
}


#endif /* GRAPH_GRAPH_H_ */

我怀疑内存不足会导致此问题。但是,对每4个邻居来说40个节点对我来说并不是什么大问题。任何人都知道出了什么问题吗?

编辑:
德语错误,因此我需要猜测:
std::bad_alloc类的项目prSimulation1.exe中发生异常。异常(exception)地址:“0x5476016”。进程已停止。

最佳答案

您的seqNeighboursvector<Node>。这意味着它将存储邻居本身,而不是指向邻居或其索引的指针。因此,复制构造函数将复制所有邻居。反过来,复制每个邻居都需要复制其邻居,而这又需要复制其邻居,依此类推。您的作业还会复制所有邻居,这需要复制他们的邻居,依此类推。这意味着每个副本都会成倍增加内存负载,直到系统无法存储所有邻居,邻居的邻居等。

PS:从侧面讲,一个叫做“list”的 vector 是个坏主意。它就像一个称为“ vector ”的列表,一组称为“ map ”的列表或名为“狗”的猫一样。

09-10 09:49
查看更多