c++ Valgrind : Address 0x0 is not stack'd, malloc'd 或(最近)free'd

Question

我正在学习一些编程，我正在尝试为 QAP 编写一个 Ant Colony 算法，问题是有时我会遇到段错误，当我使用 valgrind 时它告诉我“地址 0x0 没有堆栈，malloc 'd 或(最近)自由'”。这是代码:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>  //ifstream
#include <string>
#include <sstream>
#include <vector>
#include <utility> //pair
#include <iostream>
#include <algorithm> //shuffle
#include <random> //default_random_engine
#include <chrono> //chrono::system_clock
#include <cstdlib> // rand
#include <unistd.h>
#include <csignal>
using namespace std;

sig_atomic_t volatile done = 0;
void game_over(int) { done = 1; }

int funCosto(int dim,vector<int> sol,vector<int> dist, vector<int> flujo){
    int costo = 0;
    for (int i = 0; i<dim;i++){
        for (int j = i+1; j<dim;j++){
            // El costo es la * del valor de los flujos por la permutacion de las distancias 
            costo += flujo[dim*i+j] * dist[dim*(sol[i]-1) + (sol[j]-1)]; 
        }
    }
    return costo*2; //La matriz es simétrica
}

int buscarLista(vector<int> lista, int elemento, int dim){
    int aux = 0;
    for (int i = 0; i < dim; i++){
        if (lista[i] == elemento){aux = 1;}
    }
    return aux;
}

vector<int> localSearch(int dim,vector<int> sol, vector<int> dist, vector<int> flujo){

    vector<int> solActual(dim), solAux(dim);
    solActual = sol;
    int mejorCosto = funCosto(dim,solActual,dist,flujo);
    int costoActual, mejorCostoAnterior;

    do{
        mejorCostoAnterior = mejorCosto; // para determinar que se llegó a un óptimo local
        for (int i = 0; i < dim; i++){
            for (int j = i+1; j < dim; j++){
                solAux = solActual;
                solAux[i] = solActual[j];
                solAux[j] = solActual[i]; //intercambiamos dos elementos
                /*Importante, hay que optimizar el cálculo del costo de los vecinos*/
                costoActual = funCosto(dim,solAux,dist,flujo);
                if (costoActual<mejorCosto){
                    break;
                }
            }
            if (costoActual < mejorCosto){
                mejorCosto = costoActual; //se actualiza el mejor costo
                solActual = solAux; //se efectua el movimiento
                break; 
            }
        }
    } while (mejorCosto < mejorCostoAnterior); //se detiene cuando ya no hay mejoría

    return solActual;
}

pair<int,vector<int>> antColony(int numAnts, int dim, vector<int> dist, vector<int> flujo){

    done = 0;
    std::signal(SIGALRM, game_over);
    alarm(300);

    vector<vector<int>> hormigas(numAnts, vector<int>(dim));
    vector<vector<int>> hormigasNuevas(numAnts, vector<int>(dim));
    vector<vector<double>> feromonas(dim, vector<double>(dim));
    vector<int> mejorSol, mejorSolNueva;
    double mejorCosto, mejorCostoNuevo, totalFer, prob, auxProb, probAcum = 0 ;
    int numSwaps = dim/3;  // número de cambios que va a hacer cada hormiga en cada iteración
    random_device rd; // obtener un número aleatorio de hardware
    mt19937 eng(rd()); // semilla para el generador
    uniform_int_distribution<> disInt(0,dim-1);
    uniform_real_distribution<> disReal(0,1);
    int prim, seg, aux, contadorRep, sinMejoria = 0; //indices 
    int inten = 1; //la intensificación está prendida al comienzo

    for (int i = 1; i <= dim; i++){
        hormigas[0][i-1] = i;
    }
    for (int j = 1; j < numAnts; j++){
        hormigas[j] = hormigas[0];
    }
    //obtener una semilla basada en el tiempo
    for (int k = 0; k < numAnts; k++){
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        shuffle(hormigas[k].begin(),hormigas[k].end(), default_random_engine(seed));
    } 

    for (int i = 0; i < numAnts; i++){ //aplica local Search para las soluciones aleatorias
        hormigas[i] = localSearch(dim,hormigas[i],dist,flujo);
    }

    mejorCosto = funCosto(dim,hormigas[0],dist,flujo);
    mejorSol = hormigas[0];
    for (int i = 1; i < numAnts; i++){
        if (funCosto(dim,hormigas[i],dist,flujo) < mejorCosto){
            mejorCosto = funCosto(dim,hormigas[i],dist,flujo);
            mejorSol = hormigas[i];
        }
    }
    for (int i = 0; i<dim; i++){
        for (int j = 0 ; j<dim; j++){
            feromonas[i][j] = 1.0/(100*mejorCosto);
        }
    }

    for (int z = 0; z < 1; z++){ //máximo número de iteraciones

        for (int i = 0; i < numAnts; i++ ){

            hormigasNuevas[i] = hormigas[i];

            for (int j = 0; j < numSwaps; j++){
                prim = disInt(eng);
                auxProb = disReal(eng);
                seg = -1;
                probAcum = 0;
                do{
                    seg++;
                    if (seg == prim){seg++;}
                    totalFer = 0; //limpiamos para esta iteración
                    for (int k = 0; k < dim; k++){
                        if (k != prim){
                            totalFer += feromonas[prim][hormigasNuevas[i][k]-1] + feromonas[k][hormigasNuevas[i][prim]-1];
                        }
                    }    
                    //construimos la probabilidad con la que es aceptado el cambio segun las feromonas
                    prob = (feromonas[prim][hormigasNuevas[i][seg]-1]+feromonas[seg][hormigasNuevas[i][prim]-1]) / totalFer;
                    probAcum += prob;
                }while ((auxProb > probAcum) && (seg < dim));

                if (seg == dim){seg--;}

                aux = hormigasNuevas[i][prim];
                hormigasNuevas[i][prim] = hormigasNuevas[i][seg];
                hormigasNuevas[i][seg] = aux;

            }
            //mejoramos la solución modificada por la hormiga
            hormigasNuevas[i] = localSearch(dim,hormigasNuevas[i],dist,flujo);
        }

        //contadorRep = 0;
        //intensificación
        for (int a = 0; a < numAnts; a++){
            if (inten == 1){
                if (funCosto(dim,hormigasNuevas[a],dist,flujo) < funCosto(dim,hormigas[a],dist,flujo)){
                    hormigas[a] = hormigasNuevas[a];
                }
                else{ contadorRep++;} //para contar cuantas veces se queda con la respuesta anterior
            }
            else{
                hormigas[a] = hormigasNuevas[a];
            }
        }

        //if (contadorRep == numAnts){inten = 0;} //apaga la intensificación

        mejorCostoNuevo = funCosto(dim,hormigas[0],dist,flujo);
        for (int b = 1; b < numAnts; b++){
            if (funCosto(dim,hormigas[b],dist,flujo) < mejorCostoNuevo){
                mejorCostoNuevo = funCosto(dim,hormigas[b],dist,flujo);
                mejorSolNueva = hormigas[b];
            }
        }

        if (mejorCostoNuevo < mejorCosto){
            //si se consigue una mejor solucíón
            mejorCosto = mejorCostoNuevo;
            mejorSol = mejorSolNueva;
            inten = 1;
            sinMejoria = 0;
        }

        //actualiación de la matriz de feromonas
        for (int c = 0; c < dim; c++){
            for (int d = 0; d < dim; d++){ //Evaporación
                feromonas[c][d] = 0.9*feromonas[c][d];
            }
        }

        for (int e = 0; e < dim; e++){//reforzamos la mejor solución
            feromonas[e][mejorSol[e]-1] = feromonas[e][mejorSol[e]-1] + 0.1/mejorCosto;
        }

        //diversificación
        if (sinMejoria > dim/2){

            hormigas[0] = mejorSol; //se queda la mejor solución hasta el momento
            //se vuelve a inicializar las hormigas
            for (int k = 1; k < numAnts; k++){
                unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
                shuffle(hormigas[k].begin(),hormigas[k].end(), default_random_engine(seed));
            } 

            for (int i = 0; i < numAnts; i++){ //aplica local Search para las soluciones aleatorias
                hormigas[i] = localSearch(dim,hormigas[i],dist,flujo);
            }

            mejorCosto = funCosto(dim,hormigas[0],dist,flujo);
            mejorSol = hormigas[0];
            for (int i = 1; i < numAnts; i++){
                if (funCosto(dim,hormigas[i],dist,flujo) < mejorCosto){
                    mejorCosto = funCosto(dim,hormigas[i],dist,flujo);
                    mejorSol = hormigas[i];
                }
            }

            //renovar la matriz de feromonas
            for (int i = 0; i<dim; i++){
                for (int j = 0 ; j<dim; j++){
                    feromonas[i][j] = 1.0/(100*mejorCosto);
                }
            }
        }
        sinMejoria++;
    }

    pair <int,vector<int>> pairSol = make_pair (mejorCosto,mejorSol);
    return pairSol; 

}

int main (int argc, char* argv[]) {

    vector<int> resultados(10);
    for (int i = 0; i < 10; i++){

        clock_t startTime = clock();
        ifstream file(argv[1]);
        int dim;  //dimensiones de las matrices
        file >> dim;
        vector<int> suc(dim*dim); //matriz con los flujos entre las sucursales
        vector<int> loc(dim*dim); //matriz con las distancias de las localidades
        pair <int,vector<int>> pairSol; //tiene el costo de la busqueda y la permutación

        //guardar la matriz de distancia
        for (int i = 0; i < dim; i++){ 
            for (int j = 0; j < dim; j++) {
                file >> suc[dim*i+j];
            }
        }

        //guardar la matriz de flujos
        for (int i = 0; i < dim; i++){ 
            for (int j = 0; j < dim; j++) {
                file >> loc[dim*i+j];
            }
        }

        pairSol = antColony(10,dim,loc,suc);
        resultados[i] = pairSol.first;
        cout << pairSol.first << endl;

        for (int i = 0; i < dim; i++){
            cout << pairSol.second[i] << " ";
        }
        cout << endl;

        cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
    }

    int total = 0;
    for (int j = 0; j<10; j++){
        total += resultados[j];
    }

    cout << endl << "El promedio de de las soluciones es: " <<endl;
    cout << total/10 << endl;

    return 0;
} 

Valgrind 给我这个:

0x804B331 处大小 4 的无效读取:main (antColony.cpp:269)地址 0x0 未被堆栈、分配或(最近)释放

进程以信号 11 (SIGSEGV) 的默认操作终止访问不在地址 0x0 的映射区域内在 0x804B331: main (antColony.cpp:269)

我正在使用这个文件:

20

 0 87 14  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
87  0  0 82 57  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
14  0  0  0  0 68  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0 82  0  0  0  0 19 18 38 47  0  0  0  0  0  0  0  0  0  0
 0 57  0  0  0  0  0  0  0  0 91  0  0  0  0  0  0  0  0  0
 0  0 68  0  0  0  0  0  0  0  0 77  0  0  0  0  0  0  0  0
 0  0  0 19  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0 18  0  0  0  0  0  0  0  0  6  0  0  0  0  0  0  0
 0  0  0 38  0  0  0  0  0  0  0  0  0 75  0  0  0  0  0  0
 0  0  0 47  0  0  0  0  0  0  0  0  0  0 73 52  0  0  0  0
 0  0  0  0 91  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0 77  0  0  0  0  0  0  0  0  0  0 51  0  0  0
 0  0  0  0  0  0  0  6  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0 75  0  0  0  0  0  0  0  0 93  0  0
 0  0  0  0  0  0  0  0  0 73  0  0  0  0  0  0  0  0 84  0
 0  0  0  0  0  0  0  0  0 52  0  0  0  0  0  0  0  0  0 40
 0  0  0  0  0  0  0  0  0  0  0 51  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0 93  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0 84  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 40  0  0  0  0

0 4 7 7 4 6 3 7 1 7 8 7 2 9 8 2 9 3 4 3
4 0 8 1 7 9 8 7 6 5 1 3 1 4 4 2 7 6 3 5
7 8 0 5 7 9 1 6 3 2 9 8 4 8 7 7 4 3 7 1
7 1 5 0 3 1 9 9 7 1 6 6 1 1 2 2 4 2 7 8
4 7 7 3 0 9 9 6 9 4 1 8 2 9 8 6 1 9 2 6
6 9 9 1 9 0 7 6 9 2 3 1 4 1 9 5 3 3 7 3
3 8 1 9 9 7 0 3 7 3 5 1 9 4 6 4 7 4 9 6
7 7 6 9 6 6 3 0 7 1 6 7 3 9 4 1 8 4 9 1
1 6 3 7 9 9 7 7 0 6 1 5 7 6 5 3 4 9 8 1
7 5 2 1 4 2 3 1 6 0 6 3 9 3 3 6 4 1 8 6
8 1 9 6 1 3 5 6 1 6 0 6 3 8 2 4 8 1 9 6
7 3 8 6 8 1 1 7 5 3 6 0 8 2 7 6 4 5 4 1
2 1 4 1 2 4 9 3 7 9 3 8 0 4 4 2 5 6 4 9
9 4 8 1 9 1 4 9 6 3 8 2 4 0 3 2 8 7 2 8
8 4 7 2 8 9 6 4 5 3 2 7 4 3 0 4 3 3 8 4
2 2 7 2 6 5 4 1 3 6 4 6 2 2 4 0 8 5 9 9
9 7 4 4 1 3 7 8 4 4 8 4 5 8 3 8 0 1 2 7
3 6 3 2 9 3 4 4 9 1 1 5 6 7 3 5 1 0 1 1
4 3 7 7 2 7 9 9 8 8 9 4 4 2 8 9 2 1 0 4
3 5 1 8 6 3 6 1 1 6 6 1 9 8 4 9 7 1 4 0

错误来自接近尾声的这一行:

    for (int i = 0; i < dim; i++){
        cout << pairSol.second[i] << " ";
    }

我尝试打印解 vector 的地方。

我不明白生成的内存有什么问题。这更令人困惑，因为有时它可以完美运行。如果有人能向我解释一下，我将不胜感激。

期待您的帮助!

Answer 1

我调试了一下你的程序，发现当错误发生时，pairSol.second实际上是空的。

我认为这可能发生的唯一方式是如果 mejorSolNueva 从未被赋值，但随后赋值 mejorSol = mejorSolNueva 发生了。