矢量数组在这里发生了什么?
What is happening with vector array here?
我正在通过 C++ 中的 ACO 实现解决旅行商问题。但是,我发现到目前为止我构建的程序出现了分段错误。
(注意:出于调试目的,我已将算法限制为仅对菌落进行一次迭代)。
首先,我从一个文件中总共取出了 52 个城市,我分配了蚂蚁,使每个城市从它开始都有相同数量的蚂蚁。
为了存储每对城市之间的距离,我使用了一个名为 Map(方矩阵)的双精度向量向量。然而,在执行的中途,这些向量似乎被删除了。在这种情况下,它发生在计算 55 号蚂蚁的路径时。我添加了一段代码只是为了突出显示崩溃的确切位置:
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
那里,函数 Map[0].size() 通常是 returns 52(就像 Map.size(),因为它应该是一个方阵),但在崩溃迭代它 returns 看起来像一个内存地址,当我尝试访问任何元素时,就会发生分段错误。
我已经检查过内存访问总是正确的,并且我可以毫无问题地访问任何其他变量,除了 Map 直到第 55 只蚂蚁。
我尝试过不同的轮盘种子方法,但它总是在同一个地方崩溃。
我还改变了蚁群中蚂蚁的数量。如果每个城市只有一只蚂蚁,程序可以毫无问题地执行,但对于任何更高的数量,程序总是在第 55 只蚂蚁时崩溃。
您可以从 github 下载完整的 cpp 文件和阅读 .tsp 文件:
https://github.com/yitosmash/ACO
无论如何,我会在这里留下完整的功能:
void ACO(const vector<City>& cities, const vector<vector<double>>& Map, int max_it, int num_ants, double decay, double heur_coef, double pher_coef, double pher_coef_elit)
{
srand(30);
//Initialise colony of ants (each ant is a vector of city indices)
vector<vector<int>> Colony(num_ants, vector<int>(cities.size(), 0));
//Initialise pheromone matrix
vector<vector<double>> pheromones(cities.size(), vector<double>(cities.size(), 0));
//Initialise costs vector(for etilist expansion)
vector<double> costs(cities.size(), 0);
//Auxiliar vector of indices
vector<int> cityIndices(cities.size());
for (int i = 0; i < cities.size(); ++i)
cityIndices[i] = i;
//Longest distance from Map, used for heuristic values.
vector<double> longests(cities.size(), 0);
for(int i = 0; i < cities.size(); ++i)
longests[i] = *(max_element(Map[i].begin(), Map[i].end()));
const double MAX_DIST = *(max_element(longests.begin(), longests.end()));
longests.clear();
int i=0;
while(i<max_it)
{
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
{
cout << "Ant: " << ant_i << endl;
//City for ant_i to start at; each ant is assigned a determined starting city
int starting_city = (int) ((float)ant_i/num_ants*cities.size());
//cout << starting_city << endl;
Colony[ant_i][0] = starting_city;
//Get a vector with the cities left to visit
vector<int> RemainingCities = cityIndices;
//Remove starting city from remaining cities
RemainingCities.erase(RemainingCities.begin() + starting_city);
//Create path for ant_i
for(int city_i = 1; city_i < Colony[ant_i].size(); ++city_i)
{
cout << "Calculating city number: " << city_i << endl;
//Create roulette for next city selection
vector<double> Roulette(RemainingCities.size(), 0);
double total = 0;
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
for(int j = 0; j < RemainingCities.size(); ++j)
{
//Heuristic value is MAX_DIST - current edge.
Roulette[j] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[j]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[j]]), pher_coef);
total += Roulette[j];
}
cout << endl;
//Transform roulette into stacked probabilities
Roulette[0] = Roulette[0]/total;
for(int j = 1; j < Roulette.size(); ++j)
Roulette[j] = Roulette[j-1] + Roulette[j] / total;
//Select a city from Roulette
int chosen = 0;
double r = (double) rand()/RAND_MAX;
while(Roulette[chosen] < r)
chosen++;
//Add chosen city to
Colony[ant_i][city_i] = RemainingCities[chosen];
RemainingCities.erase(RemainingCities.begin() + chosen);
}
cout << endl;
//Save cost of ant_i, for elitist expansion
costs[ant_i] = pathCost(Colony[ant_i], Map);
}
i++;
}
}
那部分很可疑:
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
因为 i 是 map 的大小,但是您将它用作可能的字符串/向量中的索引,所以您可能以未定义的行为离开 string/vector
可能你想要
for(int i = 0; i < Map.size(); ++i)
cout << Map[i] << " ";
或
for(int i = 0; i < Map[0].size(); ++i)
cout << Map[0][i] << " ";
正如我刚才在评论中所说 RemainingCities[0]
值 -163172699 首先在
cout << "Test: Operation: " << Map.at(Colony.at(ant_i).at(city_i-1)).at(RemainingCities.at(k)) << endl;
so 不是 Map 中的有效索引,但是查看代码有明显的理由,所以原因可能是 [=52] =]vector 破坏你的记忆元素。
为了检测我将所有 [...]
替换为 .at(...)
的位置,我遇到的第一个错误是 ACO 行
costs.at(ant_i) = pathCost(Colony.at(ant_i), Map);
其中 ant_i
值为 52,而 costs 有 52 个条目,Colony 为 260,因此错误涉及 成本
注意ant_i
是由循环设置的
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
在这种情况下,num_ants
的值 260 比 costs 的大小大得多,后者定义为
vector<double> costs(cities.size(), 0);
但是cost只是分配和设置但从未读取,所以它的目标只是破坏内存。
如果我删除与它相关的两行我不再有错误并且程序正常结束,在 .at(...)
和 valgrind 检测中没有异常也没有错误。
我正在通过 C++ 中的 ACO 实现解决旅行商问题。但是,我发现到目前为止我构建的程序出现了分段错误。 (注意:出于调试目的,我已将算法限制为仅对菌落进行一次迭代)。
首先,我从一个文件中总共取出了 52 个城市,我分配了蚂蚁,使每个城市从它开始都有相同数量的蚂蚁。
为了存储每对城市之间的距离,我使用了一个名为 Map(方矩阵)的双精度向量向量。然而,在执行的中途,这些向量似乎被删除了。在这种情况下,它发生在计算 55 号蚂蚁的路径时。我添加了一段代码只是为了突出显示崩溃的确切位置:
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
那里,函数 Map[0].size() 通常是 returns 52(就像 Map.size(),因为它应该是一个方阵),但在崩溃迭代它 returns 看起来像一个内存地址,当我尝试访问任何元素时,就会发生分段错误。
我已经检查过内存访问总是正确的,并且我可以毫无问题地访问任何其他变量,除了 Map 直到第 55 只蚂蚁。 我尝试过不同的轮盘种子方法,但它总是在同一个地方崩溃。
我还改变了蚁群中蚂蚁的数量。如果每个城市只有一只蚂蚁,程序可以毫无问题地执行,但对于任何更高的数量,程序总是在第 55 只蚂蚁时崩溃。
您可以从 github 下载完整的 cpp 文件和阅读 .tsp 文件:
https://github.com/yitosmash/ACO
无论如何,我会在这里留下完整的功能:
void ACO(const vector<City>& cities, const vector<vector<double>>& Map, int max_it, int num_ants, double decay, double heur_coef, double pher_coef, double pher_coef_elit)
{
srand(30);
//Initialise colony of ants (each ant is a vector of city indices)
vector<vector<int>> Colony(num_ants, vector<int>(cities.size(), 0));
//Initialise pheromone matrix
vector<vector<double>> pheromones(cities.size(), vector<double>(cities.size(), 0));
//Initialise costs vector(for etilist expansion)
vector<double> costs(cities.size(), 0);
//Auxiliar vector of indices
vector<int> cityIndices(cities.size());
for (int i = 0; i < cities.size(); ++i)
cityIndices[i] = i;
//Longest distance from Map, used for heuristic values.
vector<double> longests(cities.size(), 0);
for(int i = 0; i < cities.size(); ++i)
longests[i] = *(max_element(Map[i].begin(), Map[i].end()));
const double MAX_DIST = *(max_element(longests.begin(), longests.end()));
longests.clear();
int i=0;
while(i<max_it)
{
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
{
cout << "Ant: " << ant_i << endl;
//City for ant_i to start at; each ant is assigned a determined starting city
int starting_city = (int) ((float)ant_i/num_ants*cities.size());
//cout << starting_city << endl;
Colony[ant_i][0] = starting_city;
//Get a vector with the cities left to visit
vector<int> RemainingCities = cityIndices;
//Remove starting city from remaining cities
RemainingCities.erase(RemainingCities.begin() + starting_city);
//Create path for ant_i
for(int city_i = 1; city_i < Colony[ant_i].size(); ++city_i)
{
cout << "Calculating city number: " << city_i << endl;
//Create roulette for next city selection
vector<double> Roulette(RemainingCities.size(), 0);
double total = 0;
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
for(int j = 0; j < RemainingCities.size(); ++j)
{
//Heuristic value is MAX_DIST - current edge.
Roulette[j] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[j]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[j]]), pher_coef);
total += Roulette[j];
}
cout << endl;
//Transform roulette into stacked probabilities
Roulette[0] = Roulette[0]/total;
for(int j = 1; j < Roulette.size(); ++j)
Roulette[j] = Roulette[j-1] + Roulette[j] / total;
//Select a city from Roulette
int chosen = 0;
double r = (double) rand()/RAND_MAX;
while(Roulette[chosen] < r)
chosen++;
//Add chosen city to
Colony[ant_i][city_i] = RemainingCities[chosen];
RemainingCities.erase(RemainingCities.begin() + chosen);
}
cout << endl;
//Save cost of ant_i, for elitist expansion
costs[ant_i] = pathCost(Colony[ant_i], Map);
}
i++;
}
}
那部分很可疑:
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
因为 i 是 map 的大小,但是您将它用作可能的字符串/向量中的索引,所以您可能以未定义的行为离开 string/vector
可能你想要
for(int i = 0; i < Map.size(); ++i)
cout << Map[i] << " ";
或
for(int i = 0; i < Map[0].size(); ++i)
cout << Map[0][i] << " ";
正如我刚才在评论中所说 RemainingCities[0]
值 -163172699 首先在
cout << "Test: Operation: " << Map.at(Colony.at(ant_i).at(city_i-1)).at(RemainingCities.at(k)) << endl;
so 不是 Map 中的有效索引,但是查看代码有明显的理由,所以原因可能是 [=52] =]vector 破坏你的记忆元素。
为了检测我将所有 [...]
替换为 .at(...)
的位置,我遇到的第一个错误是 ACO 行
costs.at(ant_i) = pathCost(Colony.at(ant_i), Map);
其中 ant_i
值为 52,而 costs 有 52 个条目,Colony 为 260,因此错误涉及 成本
注意ant_i
是由循环设置的
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
在这种情况下,num_ants
的值 260 比 costs 的大小大得多,后者定义为
vector<double> costs(cities.size(), 0);
但是cost只是分配和设置但从未读取,所以它的目标只是破坏内存。
如果我删除与它相关的两行我不再有错误并且程序正常结束,在 .at(...)
和 valgrind 检测中没有异常也没有错误。