6

プログラムを実行した直後に強制終了されるプロセスがあります。これはコンパイルされた実行可能ファイルのコードであり、数値で表されるいくつかのグラフを標準入力 (通常は記述ファイル) から読み取り、Prim のアルゴリズムを使用してすべてのグラフの最小スパニング ツリーを見つける小さなプログラムです (まだ結果は出ていませんが、解決策を見つけるだけです)。

#include <stdlib.h>  
#include <iostream>  

using namespace std;

const int MAX_NODOS = 20000;
const int infinito = 10000;

int nnodos;
int nAristas;
int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS];
int menorCoste[MAX_NODOS];
int masCercano[MAX_NODOS];



void leeGrafo(){
    if (nnodos<0 || nnodos>MAX_NODOS) {
        cerr << "Numero de nodos (" << nnodos << ") no valido\n";
        exit(0);
    }  
    for (int i=0; i<nnodos ; i++)
        for (int j=0; j<nnodos ; j++)
            G[i][j] = infinito; 
    int A,B,P;
    for(int i=0;i<nAristas;i++){
        cin >> A >> B >> P; 
        G[A][B] = P;
        G[B][A] = P;
    }   
}


void prepararEstructuras(){
    // Grafo de salida
    for(int i=0;i<nnodos;i++)
        for(int j=0;j<nnodos;j++)
            solucion[i][j] = infinito;
    // el mas cercaano 
    for(int i=1;i<nnodos;i++){
        masCercano[i]=0;
        // menor coste
        menorCoste[i]=G[0][i];
    }           
}

void prim(){
    prepararEstructuras();
    int min,k;  
    for(int i=1;i<nnodos;i++){
        min = menorCoste[1];
        k = 1;
        for(int j=2;i<nnodos;j++){
            if(menorCoste[j] < min){
                min = menorCoste[j];
                k = j;
            }
        }
        solucion[k][masCercano[k]] = G[k][masCercano[k]];
        menorCoste[k] = infinito;
        for(int j=1;j<nnodos;j++){
            if(G[k][j] < menorCoste[j] && menorCoste[j]!=infinito){
                menorCoste[j] = G[k][j];
                masCercano[j] = k;
            }       
        }           
    }
}

void output(){
    for(int i=0;i<nnodos;i++){
        for(int j=0;j<nnodos;j++)
            cout << G[i][j] << ' ';
        cout << endl;
    }
}

int main (){
    while(true){
        cin >> nnodos;
        cin >> nAristas;
        if((nnodos==0)&&(nAristas==0)) break;
        else{
            leeGrafo();
            output();
            prim(); 
        }
    }   
}

何が起こっているのかを見つけるためにstraceを使用する必要があることを学びました.これが私が得たものです:

execve("./412", ["./412"], [/* 38 vars */] <unfinished ...>
+++ killed by SIGKILL +++
Killed

ubuntu を実行していますが、この種のエラーが発生するのはこれが初めてです。プログラムは、入力から 2 つのゼロを続けて読み取った後に停止することになっています。これは、グラフ記述ファイルにあることを保証できます。また、グラフファイルへの入力リダイレクトを行わずにプログラムを実行しても問題が発生します。

4

2 に答える 2

8

これが問題であると 100% 確信しているわけではありませんが、グローバル配列のサイズを見てください。

const int MAX_NODOS = 20000;

int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS];

4 バイトと仮定するとint、以下が必要になります。

20000 * 20000 * 4 bytes * 2 = ~3.2 GB

1 つには、それほど多くのメモリがない場合もあります。第 2 に、32 ビットを使用している場合、OS が 1 つのプロセスがそれほど多くのメモリを持つことを許可しない可能性があります。

64 ビットを使用していると仮定すると (そして十分なメモリがあると仮定すると)、解決策は実行時にすべてを割り当てることです。

于 2012-01-02T01:54:55.253 に答える
6

配列Gとsolucionそれぞれには 400,000,000 の整数が含まれています。これは、ほとんどのマシンでそれぞれ約 1.6 GiB です。そのための十分な (仮想) メモリ (3.2 GiB とカウント) と、それを使用する許可 (試してみてください。MacOS X 10.7.2 ではulimit -d正しいです) がない限り、プロセスは開始に失敗し、SIGKILL によって強制終了されます (これはbashプロセスがまだ実際に進んでいるわけではありません)。

于 2012-01-02T01:54:29.190 に答える