0

karger Minimum Cut アルゴリズムを実装しようとしています ( Karger wiki ページ)

これまでのところ、小さな例 (サイズ 10 の入力) でアルゴリズムを試してみましたが、うまくいくようです。しかし、より大きな入力をしようとすると、200 としましょう。クラッシュするだけです。

最小カット データを格納するために、2D 配列を作成します: GraphCut[SIZE_ARRAY][SIZE_ARRAY_2] この場合は SIZE_ARRAY = 200 ですが、SIZE_ARRAY_2 の適切な長さを見つけることができません。

問題は、初期配列を変更して異なる頂点をマージするため、SIZE_ARRAY_2 を大きくする必要があることです。

SIZE_ARRAY_2 = 200 と宣言するとサイズが足りなくなりますが、SIZE_ARRAY_2 = 1000 と宣言するとプログラムがクラッシュするだけです。

問題は、アルゴリズムを 100000 回実行する必要があるということです。

コードの一部を次に示します。

#define ARRAY_SIZE 200
#define ARRAY_SIZE_2 200

int main()
{
    int minCut,minMinCut;

    for (int k = 0; k < ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
        minCut = kargerMinCut(k);
        if (k == 0)
            minMinCut = minCut;
        else if (minMinCut > minCut)
            minMinCut = minCut;
    }
    printf("\n minMinCut = %d\n", minMinCut);

    return 0;
}

int kargerMinCut(int k) {
// 1st dimension: each different node
// 2nd dimension: vertices
    long graphCut[ARRAY_SIZE + 1][ARRAY_SIZE_2] = {0};
    populateIntegerArray(graphCut); // import data from a file

    int nodeToMain[ARRAY_SIZE + 1];
    int sizeOfMainNode, indexToMerge,initialRand,i,j,m,nodeToMerge,nodeRemaining = ARRAY_SIZE;
    for (m = 0;m<ARRAY_SIZE + 1;m++) // initialization of nodeToMain
        nodeToMain[m] = m;

    while (nodeRemaining > 2) {
i = 0;
        j = 0;
        srand(time(NULL) + nodeRemaining);// initialise rand
        initialRand = nodeToMain[rand()%(ARRAY_SIZE) + 1]; // pick a random initial node, but not a merged one
        sizeOfMainNode = sizeOfArray(graphCut[initialRand]); // size of the initial node

        srand(time(NULL) + k); // initialise rand
        indexToMerge = rand()%sizeOfMainNode;// pick another random node in the linked nodes (its index to be precise)
        nodeToMerge = nodeToMain[graphCut[initialRand][indexToMerge]];

        for (m = 0;m<ARRAY_SIZE + 1;m++)  // update the nodeToMain array, initialRand is now the main node for nodeToMerge
            if (nodeToMain[m] == nodeToMerge)
                nodeToMain[m] = initialRand;

        // remove the nodeToMerge numbers from the graphCut[initialRand] (as they are going to be merged)
        while(graphCut[initialRand][j] > 0 && j < sizeOfMainNode) {
            if (initialRand == nodeToMain[graphCut[initialRand][j]]) {
                // if this is the last element, do nothing
                while(nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]] == initialRand && j < sizeOfMainNode - 1) {
                    graphCut[initialRand][sizeOfMainNode - 1] = 0;
                    sizeOfMainNode--;
                }
                graphCut[initialRand][j] = nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]];
                graphCut[initialRand][sizeOfMainNode - 1] = 0;
                sizeOfMainNode--;
            }
            j++;
        }

        i = 0;
        while (graphCut[nodeToMerge][i] > 0 && sizeOfMainNode < ARRAY_SIZE_2 && i < ARRAY_SIZE_2) { // add each vextex of the nodeTomerge to the merged nodes
            if (nodeToMain[graphCut[nodeToMerge][i]] != initialRand) {
                graphCut[initialRand][sizeOfMainNode] = nodeToMain[graphCut[nodeToMerge][i]];
                sizeOfMainNode++;
            }
            i++;
        }

        nodeRemaining--;
    }

    return sizeOfArray(graphCut[nodeToMain[1]]);
}

コードは本当にきれいではなく、おそらく本当に悪いです（Cの初心者）。だから私は他のアドバイスを歓迎します。

デバッガーで発生するエラーは、本当にランダムに見えます。エラーは次のとおりです。

0で割り切れない

time64.c の 62 行目で停止します

tim = (__time64_t)((nt_time.ft_scalar - EPOCH_BIAS) / 10000000i64);
4

3 に答える 3

2

配列サイズの変更により、スタック オーバーフローが発生している可能性があります。スタックの一般的なデフォルト サイズは 1MB (1048576 バイト) です。あなたが持っている場合：

long graphCut[200][1000];

配列はバイトを占有し4 == sizeof(long)ているため、関数内のスタック変数には十分ではない可能性のあるバイトが残ります（その関数は表示されません）。その場合、配列には1MB を超えるバイト数が必要になります。graphCut200 * 1000 * 4 = 800000248576populateIntegerArray()8 == sizeof(long)1600000

そのサイズの配列が必要な場合は、スタックではなくヒープに (すべてまたは一部) を割り当てます。例えば：

long* graphCut[ARRAY_SIZE_1];
int i;
for (i = 0; i < sizeof(graphCut)/sizeof(graphCut[0]); i++)
{
    graphCut[i] = malloc(ARRAY_SIZE_2 * sizeof(graphCut[0][0]));
    memset(graphCut[i], 0, ARRAY_SIZE_2 * sizeof(graphCut[0][0]));
}

for (i = 0; i < sizeof(graphCut)/sizeof(graphCut[0]); i++)
{
    free(graphCut[i]);
}
于 2012-07-20T11:48:54.443 に答える
1

考えられる問題には、整数またはスタック オーバーフロー (正しいサイトにいるため) とメモリの初期化があります。

この実装では、グラフカットをヒープに割り当て、kargerMin が呼び出されるたびにゼロにする必要があるため、これらの問題に対処できます。

int minCut, minMinCut;
    // There is a small possibility that ARRAY_SIZE*ARRAY_SIZE*4 exceeds int boundary if 16-bit
    long k;
    long **buffer;
// Allocate graphCut on the heap
buffer = malloc((ARRAY_SIZE + 1)*sizeof(long *));
for (k = 0; k < ARRAY_SIZE + 1; k++)
    buffer[k] = malloc(ARRAY_SIZE_2*sizeof(long));

for (k = 0; k < ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
    minCut = kargerMinCut(k, buffer);
    if (k == 0)
        minMinCut = minCut;
    else if (minMinCut > minCut)
        minMinCut = minCut;
}
printf("\n minMinCut = %d\n", minMinCut);

// Here we free the buffer. We could do it in any order, but
// as it costs nothing here to do so, we free it in reverse-
// allocation-order to avoid any possible memory fragmentation
// - which is moot anyway, if this is a main() and we're exiting
// the program. In other instances it could be relevant.
for (k = 0; k < ARRAY_SIZE + 1; k++)
{
    free(buffer[ARRAY_SIZE-k]); buffer[ARRAY_SIZE-k] = NULL;
}
free(buffer); buffer = NULL;
// The NULLing of the just-freed variables has no purpose except
// to GUARANTEE that any illegal use of them, dangling pointers,
// leftover copies etc. will immediately trigger a core dump and
// be discovered, instead of lurking undetected.

return 0;
}

int kargerMinCut(long k, long **graphCut) {
    // 1st dimension: each different node
    // 2nd dimension: vertices

    // Zero graphCut. If populateIntegerArray rewrites
    // the whole of graphCut, these four lines are redundant.
    int     i, j;
    for (i = 0; i < ARRAY_SIZE + 1; i++)
            for (j = 0; j < ARRAY_SIZE_2; j++)
                    graphCut[i][j] = 0;
    // otherwise, they make sure that no old value of graphCut
    // or uninitialised value is going to linger and potentially
    // corrupt calculations later on.
    populateIntegerArray(graphCut); // import data from a file
于 2012-07-20T12:09:33.500 に答える