Segmentation fault

[大工]

初投稿ですバタン♪Ю―(^O^ )おじゃましマース

ダイクストラ法を用いて最短経路問題を解くプログラムが完成したのですが。。。

問題が発生しました。
Segmentation fault　とCygwinで表示され
gdbで調べてみたんですが。。

#0  0x00401649 in daijkstra (a=14) at C_2~extra.c:135
#1  0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#2  0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#3  0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#4  0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#5  0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#6  0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#7  0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#8  0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#9  0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#10 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#11 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#12 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#13 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#14 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#15 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#16 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#17 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#18 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#19 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#20 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#21 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
#22 0x00401651 in daijkstra (a=14) at C_2~extra.c:135
#23 0x00401651 in daijkstra (a=57) at C_2~extra.c:135
---Type <return> to continue, or q <return> to quit--

となり135行目はちょうど矢印の部分です。

いったい何が起こっているのでしょうか？？

再帰の無限ループになっているのでしょうか？？

でも、同じ点はten * hen 以上アクセスできないようにして、そのうちその点はアクセスできないようになり再帰は起こらない(count[/url]の要素にならないから)はずなんですが。。hen * ten の部分を 1 に変えてみるとうまくいきごくたまにSegmentation faultと表示されます。この場合はある点aは２回以上アクセスできないということになるので、２回目でアクセスしたときに２回目の方が１回目より短い場合変更できなくなります。ten * hen は全ての点にネットワーク(無向グラフです)の辺が付いたと考えた場合です(これ以上の数はないという条件です・たぶん間違ってます；；)

どなたかSegmentation faultを表示しなくなる方法を教えて下さい.

[大工]

削除

[box]

> ダイクストラ法を用いて最短経路問題を解くプログラムが完成したのですが。。。
>
> 問題が発生しました。

入力パラメータの具体例を教えてください。

[大工]

失礼しました..

ダイクストラのスペルが間違ってますが気になさらず

確率は小数で入力して下さい.
入力>>>>>0.004234
何個の点を対象としますか
入力>>>>>600
何個のネットワークを生成しますか
入力>>>>>200

Program received signal SIGSEGV, Segmentation fault.
0x00401649 in daijkstra (a=0) at C_2~extra.c:135
135 daijkstra(f);


何個の点を対象としますか
入力>>>>>150
何個のネットワークを生成しますか
入力>>>>>20

Program received signal SIGSEGV, Segmentation fault.
0x00401649 in daijkstra (a=0) at C_2~extra.c:135
135 daijkstra(f);


↓これはうまくいった時のものです

確率は小数で入力して下さい.
入力>>>>>0.005345
何個の点を対象としますか
入力>>>>>40
何個のネットワークを生成しますか
入力>>>>>2
ネットワークの直径の平均値: 2.000000
ネットワーク不完全数 → 0
Program exited normally.

[box]

> 確率は小数で入力して下さい.
> 入力>>>>>0.004234
> 何個の点を対象としますか
> 入力>>>>>600
> 何個のネットワークを生成しますか
> 入力>>>>>200

コードをすべて追いかけたわけではないのですが、
もしかすると、入力データの内容によっては
再帰のレベルが深くなりすぎているのかもしれません。

[大工]

再帰のレベルですか。。。。

すみません、初心者なんでもうすこし詳しくお願いします.

[box]

> 再帰のレベルですか。。。。

daijkstra関数では、

自分から自分を呼び出して→また自分から自分を呼び出して→
またまた自分から自分を呼び出して→…→

ということを行なっています。
この、再帰呼び出しを行なう際には、いずれ元へ戻ってきたときのために、
・戻ってきた後、次に実行する命令のアドレス
・その時点でのローカル変数の状態
など、さまざまな情報を保持した上で、次の再帰呼び出しを行なっています。

再帰のレベルというのは、最初に書いた矢印の数だと思ってくださってよいと思います。
自分を呼び出して、さらに自分を呼び出して、…というレベルがあまり深くなりすぎると、
上に書いた保持しておくべき情報が多くなりすぎて、
保持するための領域（スタック）をはみ出してしまうのかもしれません。

はみ出してしまったとき、通常は「スタックオーバーフロー」という
現象が起きるように思うのですが、今回のプログラムではたまたま
「segmentation fault」（これも、アクセスしてはいけない領域を
アクセスしてしまった、という種類のエラーです）が発生してしまった、
ということであるのかもしれません。

問題の解決に直接つながる回答でなくて、申し訳ありません。

[大工]

難しいんですね。。

ありがとうございます

[Justy]

　スタックオーバーフローが原因ならスタックサイズを増やしてあげれば解決すると思います。
　リンカの設定の項目を調べて増やしてみて下さい。

[大工]

リンカの設定(？)ですかすみません、よくわかんないです

[Justy]

　コンパイラ・リンカは何を使っていますか？

[大工]

Ｃｙｇｗｉｎです(これって答えになってます？)

[Justy]

　Cygwin上でということは gccでしょうか。

　なら --stack 4096 のようにオプションに追加してスタックサイズを指定できます（たしか）。
　数値は適当なので、増やして試してみて下さい。
（手っ取り早く 1048576くらいまで一気に増やしてみてもいいかも）

[大工]

回答ありがとうございます。

やってみたんですが、cc1: error: unrecognized command line option "-fstack"

と表示されます。これはいったい。。

[Justy]

　このオプションはリンカに対するオプションなので、コンパイラに指定してもダメです。

　うーん、少し　linuxから試してみましたが、リンカ側も認識しませんでした、そのオプション。
　今の gccはうまくいかないのでしょうか・・・。


　ただ、今回のケースは元々再帰が深すぎるのに問題があるので、アルゴリズム面から見直した方がいいかもしれません。
　tenの数が多ければ多いほど・・・ 20とかの数値でも 3000階層以上の再帰を行うことがあるようです。

[大工]

そぅなんですか。。。。＿｜￣｜〇

１からやり直しか。。
どこかちょっと変えるだけじゃ無理ですよね

[mas]

スタックオーバーフローを防ぐだけなら、
再帰の部分を自前のstackで置き換えるのはどうでしょう？

void func(int n) {
  if(flag)
    func(next_n);
}

int main() {
  func(i);
}

このような再帰呼び出しを

int main() {
  int top = 0;
  int stack[STACK_SIZE];
  stack[top] = i;
  while(top >= 0) {
    // このnは再帰関数のnと等価
    int n = stack[top];
    top--;
    
    if(flag) {
      top++;
      stack[top] = next_n;
    }
  }
}

再帰を使わずにループで表現できます。

根本的な解決にはならないかもしれませんけど。

[大工]

それっていったいなにが起こってるんですか？

[mas]

> それっていったいなにが起こってるんですか？
再帰をループに置き換えています。
具体的な例)

#include <stdio.h>

void func(int n)
{
    if(n != 0) {
        int i;
        for(i=0;i<n;i++)
            printf("%d", i);
        printf("\n");
        func(n-1);
    }
}

int main()
{
    func(5);
    return 0;
}

----------------------------------------------

#include <stdio.h>

#define STACK_SIZE 10

int main()
{
    int top = 0;
    int stack[STACK_SIZE];
    stack[top] = 5;
    while(top >= 0) {
        int n = stack[top];
        top--;

        if(n != 0) {
            int i;
            for(i=0;i<n;i++)
                printf("%d", i);
            printf("\n");
            
            top++;
            stack[top] = n-1;
        }
    }
    return 0;
}

実行してみるとわかると思いますが、上の2つのプログラムは同じ動作をします。
見比べると共通点が多いこともわかると思います。

同様に、ダイクストラ法の再帰関数もループにして置き換えることができます。

[mas]

大工さんのプログラムをもとに再帰をループに置き換えたものを載せます。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define ARRAY_MAX 10000

#define STACK_SIZE 1000000

static int ten, hen, count[ARRAY_MAX];
static int adj[ARRAY_MAX][ARRAY_MAX], place[ARRAY_MAX], no_loop[ARRAY_MAX], result[ARRAY_MAX], net_max[ARRAY_MAX];

int a_stack[STACK_SIZE];


int main (void)
{
    int sum = 0, sub = 0;
    //各要素を格納する
    int length[ARRAY_MAX], begin[ARRAY_MAX], end[ARRAY_MAX];
    int a, b, c, d, e, f, g, h, i, receive, net_kosuu;
    double ran, kakuritu, re_result;


    printf("確率は小数で入力して下さい.\n");
    printf("入力>>>>>");
    scanf(" %lf", &kakuritu);
    printf("何個の点を対象としますか\n");
    printf("入力>>>>>");
    scanf(" %d", &ten);
    printf("何個のネットワークを生成しますか\n");
    printf("入力>>>>>");
    scanf("%d", &net_kosuu);

    //  srand((unsigned)time(NULL));
    srand(0);

    for(h = 0;h != net_kosuu;h++){

        net_max[h] = -INT_MAX;

        //辺にINT_MAXを入力する.
        for(a = 0;a != ten;a++){
            for(b = 0;b != ten;b++){
                adj[a] = INT_MAX;
            }
        }

        for(a = 0, hen = 0;a != ten;a++){
            for(b = 0;b != ten;b++){
                ran = (double)rand() / RAND_MAX;//０から１の値を生成.
                if(a == b) continue;
                if(kakuritu >= ran){
                    adj[a] = 1;
                    adj[a] = 1;
                    hen++;
                }
            }
        }
        //ネットワーク作成完了.


        for(i = 0;i != ten;i++){
            result = -INT_MAX;
            for(b = 0;b != ten;b++){
                no_loop = 0;
            }

            for(b = 0;b != ten;b++){
                place = INT_MAX;      /*十分大きな値を入力する*/
            }                               /*０番目は始点なので    */
            place = 0;                   /*          ０を入力する*/

            //           daijkstra(i);
            {
                int top = 0;
                a_stack[top] = i;
                while(top >= 0) {
                    int a = a_stack[top];
                    int g, b, c, d, e, f;
                    top--;
                    //アクセス出来る点を探索.
                    for(b = 0, c = 0;b != ten;b++){
                        if(adj[a] == INT_MAX || a == b) continue;
                        else{
                            if(no_loop != ten * hen){
                                count[c] = b;//アクセス出来た点を入力.
                                c++;
                                no_loop = no_loop + 1;
                            }
                        }
                    }
                    count[c] = -1;

                    for(d = 0;count[d] != -1; d++){
                        c = count[d];
                        if(place[c] == INT_MAX){
                            place[c] = adj[a][c] + place[a];
                        }
                        else{
                            g = adj[a][c] + place[a];
                            if(g < place[c]){
                                place[c] = g;
                            }
                        }
                    }

                    for(e = 0;count[e] != -1;e++){
                        f = count[e];
                        //                  daijkstra(f);/*←ここです.*/
                        top++;
                        a_stack[top] = f;
                    }

                    //                    return;
                }
            }
            
            for(c = 0;c != ten;c++){
                if(place[c] == INT_MAX) continue;
                else if(result < place[c]) result = place[c];
            }
        }
        for(d = 0;d != ten;d++){
            if(net_max[h] < result[d]) net_max[h] = result[d];
        }
    }
    for(a = 0, sum = 0;a != net_kosuu;a++) {
        if(net_max[a] == 0) sub++;
        sum += net_max[a];
    }

    net_kosuu = net_kosuu - sub;

    if(net_kosuu != 0) {
        re_result = (double)sum / net_kosuu;
        printf("ネットワークの直径の平均値: %lf\n", re_result);
    }
    printf("ネットワーク不完全数 → %d", sub);

    return EXIT_SUCCESS;
}

私の環境では
> 確率は小数で入力して下さい.
> 入力>>>>>0.004234
> 何個の点を対象としますか
> 入力>>>>>150
> 何個のネットワークを生成しますか
> 入力>>>>>20
このくらいの条件であれば時間はかかりますがスタックオーバーフローをおこすこともなく実行できました。

# もしかしたら大工さんのダイクストラ法の実装が間違っている可能性もあります。
# 記憶が定かではありませんが、ダイクストラ法を用いれば数百程度の点であれば、
# それほど時間をかけずに最短経路が求まった覚えが…

[大工]

わざわざありがとうございます。

高速化したいんですけどなかなか参考できるWebがなくて。。

どこかにないでしょうか？？自分ではフィボナッチヒープが速いと調べたんですが色々聞くと実はそんなに速くないとか。。

[Interest]

http://okwave.jp/qa2627756.html　の人です。

高速化する前に，正しく動く事を優先しましょうよ。
間違ったプログラムが高速で動いても結果が間違っていたら意味がない。

[大工]

そのプログラミングは捨てました。もっといいのが思いついたので