我有一个定义如下的结构:
struct Edge
{
int u, v; // vertices
Edge() { }
Edge(int u, int v)
{
this->u = u;
this->v = v;
}
};
并且定义了一个类字段,如下所示
vector<Edge> solution;
在我创建新的
Edge
并像这样将它们推入向量中的一个方法中(这是我真实代码的极度简化,但问题依然存在):solution.push_back(Edge(1, 2));
solution.push_back(Edge(3, 4));
solution.push_back(Edge(5, 6));
solution.push_back(Edge(7, 8));
solution.push_back(Edge(9, 10));
solution.push_back(Edge(11, 12));
solution.push_back(Edge(13, 14)); // adding 7th element; the problem occurs here
当执行最后一个push_back时,在Visual Studio的调试模式下出现了一个错误窗口,调试器跳转到malloc.c文件的_heap_alloc函数结尾处,并弹出一个断点。在这个第七行之前,向量看起来可以正常工作。我可以在调试器中看到所有的元素。似乎这个向量在重新分配自己(扩展大小)时存在问题。
有趣的是,如果我将以下内容放在所有推回操作之前:
solution.reserve(7);
第七个边已经被正确添加。更有趣的是,尝试为超过22个元素保留空间也会导致上述错误。
我做错了什么?我该如何调试?应用程序的其余部分并没有使用太多内存,所以我不相信堆已经满了。
需要更多代码,请请求。这是一个比较粗糙的Metric Travelling Salesman's Problem 2-近似算法实现。它首先创建最小生成树,然后按DFS顺序将顶点(只是索引)添加到partialSolution
向量中。
void ApproxTSPSolver::Solve()
{
// creating a incidence matrix
SquareMatrix<float> graph(noOfPoints);
for (int r=0; r<noOfPoints; r++)
{
for (int c=0; c<noOfPoints; c++)
{
if (r == c)
graph.SetValue(r, c, MAX);
else
graph.SetValue(r, c, points[r].distance(points[c]));
}
}
// finding a minimum spanning tree
spanningTree = SquareMatrix<bool>(noOfPoints);
// zeroeing the matrix
for (int r=0; r<noOfPoints; r++)
for (int c=0; c<noOfPoints; c++)
spanningTree.SetValue(r, c, false);
bool* selected = new bool[noOfPoints];
memset(selected, 0, noOfPoints*sizeof(bool));
selected[0] = true; // the first point is initially selected
float min;
int minR, minC;
for (int i=0; i<noOfPoints - 1; i++)
{
min = MAX;
for (int r=0; r<noOfPoints; r++)
{
if (selected[r] == false)
continue;
for (int c=0; c<noOfPoints; c++)
{
if (selected[c] == false && graph.GetValue(r, c) < min)
{
min = graph.GetValue(r, c);
minR = r;
minC = c;
}
}
}
selected[minC] = true;
spanningTree.SetValue(minR, minC, true);
}
delete[] selected;
// traversing the tree
DFS(0);
minSol = 0.0f;
// rewriting the solution to the solver's solution field
for (int i=0; i<noOfPoints - 1; i++)
{
solution.push_back(Edge(partialSolution[i], partialSolution[i + 1]));
minSol += points[partialSolution[i]].distance(points[partialSolution[i + 1]]);
}
solution.push_back(Edge(partialSolution[noOfPoints - 1], partialSolution[0]));
minSol += points[partialSolution[noOfPoints - 1]].distance(points[partialSolution[0]]);
cout << endl << minSol << endl;
solved = true;
}
void ApproxTSPSolver::DFS(int vertex)
{
bool isPresent = std::find(partialSolution.begin(), partialSolution.end(), vertex)
!= partialSolution.end();
if (isPresent == false)
partialSolution.push_back(vertex); // if I comment out this line, the error doesn't occur
for (int i=0; i<spanningTree.GetSize(); i++)
{
if (spanningTree.GetValue(vertex, i) == true)
DFS(i);
}
}
class ApproxTSPSolver : public TSPSolver
{
vector<int> partialSolution;
SquareMatrix<bool> spanningTree;
void DFS(int vertex);
public:
void Solve() override;
};
来自main.cpp
:
TSPSolver* solver;
string inputFilePath, outputFilePath;
// parsing arguments
if (ArgParser::CmdOptionExists(argv, argv + argc, "/a"))
{
solver = new ApproxTSPSolver();
}
else if (ArgParser::CmdOptionExists(argv, argv + argc, "/b"))
{
solver = new BruteForceTSPSolver();
}
else
{
solver = new BranchAndBoundTSPSolver();
}
inputFilePath = ArgParser::GetCmdOption(argv, argv + argc, "/i");
outputFilePath = ArgParser::GetCmdOption(argv, argv + argc, "/s");
solver->LoadFromFile(inputFilePath);
Timer timer;
timer.start();
solver->Solve();
timer.stop();
cout << timer.getElapsedTime();
TSPSolver.c的一部分:
TSPSolver::TSPSolver()
{
points = NULL;
solved = false;
}
TSPSolver::~TSPSolver()
{
if (points)
delete[] points;
}
void TSPSolver::LoadFromFile(string path)
{
ifstream input(path);
string line;
int nodeID;
float coordX, coordY;
bool coords = false;
minX = numeric_limits<float>::max();
maxX = numeric_limits<float>::min();
minY = numeric_limits<float>::max();
maxY = numeric_limits<float>::min();
while (input.good())
{
if (coords == false)
{
getline(input, line);
if (line == "NODE_COORD_SECTION")
{
coords = true;
}
else if (line.find("DIMENSION") != string::npos)
{
int colonPos = line.find_last_of(":");
noOfPoints = stoi(line.substr(colonPos + 1));
#ifdef _DEBUG
cout << noOfPoints << " points" << endl;
#endif
// allocating memory for this amount of points
points = new Point[noOfPoints];
}
}
else
{
input >> nodeID >> coordX >> coordY;
points[nodeID - 1].X = coordX;
points[nodeID - 1].Y = coordY;
minX = min(minX, coordX);
maxX = max(maxX, coordX);
minY = min(minY, coordY);
maxY = max(maxY, coordY);
if (nodeID == noOfPoints)
{
break;
}
}
}
input.close();
}
Edge(int uu, int vv):u(uu),v(vv){}
构造函数,它比您当前的构造函数更有效率。 - TemplateRex