以下代码是关于实时搜索邻居的。将新节点添加到我的图形后,将立即调用此节点的函数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”。进程已停止。
最佳答案
您的seqNeighbours
是vector<Node>
。这意味着它将存储邻居本身,而不是指向邻居或其索引的指针。因此,复制构造函数将复制所有邻居。反过来,复制每个邻居都需要复制其邻居,而这又需要复制其邻居,依此类推。您的作业还会复制所有邻居,这需要复制他们的邻居,依此类推。这意味着每个副本都会成倍增加内存负载,直到系统无法存储所有邻居,邻居的邻居等。
PS:从侧面讲,一个叫做“list”的 vector 是个坏主意。它就像一个称为“ vector ”的列表,一组称为“ map ”的列表或名为“狗”的猫一样。