スタックオーバーフローの回避方法について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
蟻さん

スタックオーバーフローの回避方法について

#1

投稿記事 by 蟻さん » 10年前

以下のプログラムをデバッグ有りで実行するとスタックオーバーフローが表示されます。その解決方法を教えて頂きたく思います。このプログラムは巡回セールスマン問題を蟻の行動をモデルとして解くアルゴリズムをC言語で実装したものです。現在100都市バージョンでコードは書かれています。14都市バージョンでプログラムを実行すると正常に終了します。配列の大きさに問題があると考えてVisual C++のスタックのサイズを変更して実行したら実行こそできたものの途中で実行が不安定になります。ヒープ領域というものがあるようですがこのプログラムの問題点が掴めていない状態です。
ご回答宜しくお願いいたします。

コード: 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define CITY_NUM 100//都市数
#define ANT_NUM 100//エージェント数
#define MAX_ITER 10000//終了条件
double get_dists(double x1,double x2,double y1,double y2){//２点間の距離
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
void main(void){
	FILE *fp;
	double Q=1.0;//分泌されるフェロモンの定数
	double ALPHA=1.0;//フェロモンを優先させる度合
	double BETA=5.0;//ヒューリスティック情報を優先させる度合
	double RHO=0.9;//フェロモンの蒸発率
	double CITY[CITY_NUM],x[CITY_NUM],y[CITY_NUM];//都市数、ｘ、ｙ
	double dist[CITY_NUM][CITY_NUM],phe[CITY_NUM][CITY_NUM];//都市間の距離、フェロモン量
	double q=0,hide=0;//各エージェントが都市に移動する確率を求めるための評価値
	double p[CITY_NUM]={0};//各エージェントが都市に移動する確率
	double delta[CITY_NUM][CITY_NUM]={0};//フェロモン更新式のデルタに使用
	double deltamiu[CITY_NUM][CITY_NUM]={0};//フェロモン更新式のデルタに使用
	double kai[MAX_ITER+100]={0};//試行回数１回ごとの最良解の値を格納
	double last=0;//最終的な全体の最良解
	double L[ANT_NUM+100]={0};//各エージェントの総経路長
	double RANK[ANT_NUM+100]={0};//各エージェントの総経路長のソート用
	double s[CITY_NUM]; // 累積確立分布
	double dumy;//ソートに使用
	int dumy2;//ソートに使用
	int SIGMA=5;//上位何位までフェロモンを置くかのパラメタ
	int RANK2[ANT_NUM+100]={0};
	int sairyo=0;//試行回数１回での最良解
	int tmp[ANT_NUM+100]={0},line=0;//総距離を算出するために使う変数
	int t=0,i=0,j=0,max=0,key=0;//試行回数
	int ip; // 分布表カウンタ
	int rn; // 乱数
	int e,r;//ソートに使用
	srand((unsigned)time(NULL));
	if((fp=fopen("kroA100.txt","r"))==NULL)//データを読み込む
		printf("ファイルをオープンできません。\n");
	else{
		while(fscanf(fp,"%lf%lf%lf",&CITY[i],&x[i],&y[i])==3){//iが都市番号、CITY,x,yにはそれぞれ都市名、座標
			i++;
		}
	}
	fp=fopen("result.txt","w");
	for(i=0;i<CITY_NUM;i++){//都市iとj間の距離を全通り求める
		for(j=0;j<CITY_NUM;j++){
			dist[i][j]=get_dists(x[i],x[j],y[i],y[j]);
		}
	}
	for(i=0;i<CITY_NUM;i++){//フェロモンの初期化（同じ都市間なら０でそれ以外なら任意の値）
		for(j=0;j<CITY_NUM;j++){
			if(dist[i][j]==0){
				phe[i][j]=0;
			}
			else{phe[i][j]=10000000000;}
		}
	}
	for(t=0;t<MAX_ITER;t++){//終了条件まで繰り返す
		int ij[ANT_NUM][CITY_NUM][CITY_NUM]={0};//エージェントが通ったら1、通ってないなら0
		for(i=0;i<ANT_NUM;i++){//全てのエージェントが巡回路を生成
			int flag[CITY_NUM+100]={0};//1が訪問、0が未訪問
			max=i;//maxを初期化
			tmp[0]=i;
			line=0;//lineを初期化
			flag[i]=1;//エージェントが最初にいる都市は訪問済み
			L[i]=0;
			do{//１つの巡回路を生成
				key=0;//keyの初期化
				for(j=0;j<CITY_NUM;j++){//確率を格納
					q=0;//qの初期化
					if(flag[j]==0)
					{
						for(int tosi=0;tosi<CITY_NUM;tosi++)//確率の分母
						{
							if(flag[tosi]==0){q=q+pow(phe[max][tosi],ALPHA)*pow((1.0/dist[max][tosi]),BETA);}
						}
						if(dist[max][j]==0){//今いる都市に移動するケース
							p[j]=0;}
						else{//通常の移動のケース
							hide=pow(phe[max][j],ALPHA)*pow((1.0/dist[max][j]),BETA);
							p[j]=hide/q;}
					}
					else{p[j]=0;}
				}
				for(int r=0;r<CITY_NUM;r++){
					p[r]=p[r]*100;
				}
				s[0] = p[0];
				for(ip=1;ip<CITY_NUM;ip++){// 累積確率表を作る
					s[ip] = s[ip-1]+p[ip];
				}
				rn = rand()%100;
				for(ip=0;ip<CITY_NUM;ip++){// 都市を確率的に選択
					if((s[ip]>rn)&&(p[ip]>0)) break;
				}
				max=ip;
				line++;//lineをインクリメントする
				if(line>ANT_NUM-1){//lineの暴走を止める
					line=ANT_NUM-1;}
				tmp[line]=max;//maxをtmp[line]に退避
				flag[max]=1;//確率的に移動したのでflagを更新
				ij[i][tmp[line-1]][max]=1;//エージェントが通った道flagを更新
				ij[i][max][tmp[line-1]]=1;//エージェントが通った道flagを更新（a→bが1ならb→aも1であるべき）			
				L[i]=L[i]+dist[tmp[line-1]][max];//選ばれた都市までの距離をエージェント総経路長に加算、L[i]はi番目のエージェント、tmp[line-1]には更新前のmaxの都市番号が入っている
				for(int g=0;g<CITY_NUM;g++){//未訪問都市があればkeyの値は1
					if(flag[g]==0){
						key=1;
						break;
					}
				}
			}while(key==1);
			L[i]=L[i]+dist[max][i];//ゴールからスタートの都市間を加算して１つの巡回路の総経路長
			if(L[i]<0){
				L[i]=L[i-1];}
			fprintf(fp,"%f\n",L[i]);
			if(L[sairyo]>=L[i]){
				sairyo=i;//１回の試行回数での最良解
				kai[t]=L[sairyo];//１回の試行回数での最良解の値をkai配列に格納
			}
		}
		for(int d=0;d<CITY_NUM;d++){//ソート用の配列に経路長をコピー
			RANK[d]=L[d];
			RANK2[d]=d;
		}
		for(e=0;e<CITY_NUM;e++){//昇順ソート
			for(r=e+1;r<CITY_NUM;r++){//RANKには経路長の昇順、RANK2にはエージェント番号
				if(RANK[e] > RANK[r]){
					dumy=RANK[e];
					dumy2=RANK2[e];
					RANK[e]=RANK[r];
					RANK2[e]=RANK2[r];
					RANK[r]=dumy;
					RANK2[r]=dumy2;
				}
			}
		}
		for(int ii=0;ii<CITY_NUM;ii++){//最良の巡回路を辿ったエージェントのフェロモンを蓄積
			for(int jj=0;jj<CITY_NUM;jj++){
				if(ij[RANK2[0]][ii][jj]==1){delta[ii][jj]=delta[ii][jj]+SIGMA/RANK[0];}}}
		for(int miu=1;miu<(SIGMA-1);miu++){
			for(int ii=0;ii<CITY_NUM;ii++){//2位からσ-1番目までの優秀な巡回路を辿ったエージェントのフェロモンを蓄積
				for(int jj=0;jj<CITY_NUM;jj++){
					if(ij[RANK2[miu]][ii][jj]==1){deltamiu[ii][jj]=deltamiu[ii][jj]+(SIGMA-miu)/RANK[miu];}}}}
		for(i=0;i<CITY_NUM;i++){//エージェントが蓄積したフェロモン情報によりフェロモン量を更新
			for(j=0;j<CITY_NUM;j++){
				phe[i][j]=(1-RHO)*phe[i][j]+delta[i][j]+deltamiu[i][j];
			}
		}
		printf("試行回数%d回目の最良解 : %f\n",t+1,L[sairyo]);
	}
	last=kai[0];//lastをkai[0]で初期化
	for(t=1;t<MAX_ITER-1;t++){//kai配列に格納してある各試行ごとの最良解から全体での最良解lastを求める
		if(last>=kai[t]){
			last=kai[t];}}
	printf("全体での最良解 : %f\n",last);
	fclose(fp);
}
kroA100.txt
1 1380 939
2 2848 96
3 3510 1671
4 457 334
5 3888 666
6 984 965
7 2721 1482
8 1286 525
9 2716 1432
10 738 1325
11 1251 1832
12 2728 1698
13 3815 169
14 3683 1533
15 1247 1945
16 123 862
17 1234 1946
18 252 1240
19 611 673
20 2576 1676
21 928 1700
22 53 857
23 1807 1711
24 274 1420
25 2574 946
26 178 24
27 2678 1825
28 1795 962
29 3384 1498
30 3520 1079
31 1256 61
32 1424 1728
33 3913 192
34 3085 1528
35 2573 1969
36 463 1670
37 3875 598
38 298 1513
39 3479 821
40 2542 236
41 3955 1743
42 1323 280
43 3447 1830
44 2936 337
45 1621 1830
46 3373 1646
47 1393 1368
48 3874 1318
49 938 955
50 3022 474
51 2482 1183
52 3854 923
53 376 825
54 2519 135
55 2945 1622
56 953 268
57 2628 1479
58 2097 981
59 890 1846
60 2139 1806
61 2421 1007
62 2290 1810
63 1115 1052
64 2588 302
65 327 265
66 241 341
67 1917 687
68 2991 792
69 2573 599
70 19 674
71 3911 1673
72 872 1559
73 2863 558
74 929 1766
75 839 620
76 3893 102
77 2178 1619
78 3822 899
79 378 1048
80 1178 100
81 2599 901
82 3416 143
83 2961 1605
84 611 1384
85 3113 885
86 2597 1830
87 2586 1286
88 161 906
89 1429 134
90 742 1025
91 1625 1651
92 1187 706
93 1787 1009
94 22 987
95 3640 43
96 3756 882
97 776 392
98 1724 1642
99 198 1810
100 3950 1558
ページトップ
Rittai_3D
記事: 525
登録日時: 12年前

Re: スタックオーバーフローの回避方法について

#2

投稿記事 by Rittai_3D » 10年前

変数をメインの外に移動してみて下さい。
もしくは、大きめの配列はmalloc()かnewでメモリ確保をして下さい。
malloc/newを使う場合はメモリリークしないように注意して下さい。
初心者です
ページトップ
sleep

Re: スタックオーバーフローの回避方法について

#3

投稿記事 by sleep » 10年前

Windowsの32bit用アプリケーションですかね？
仮想メモリにシステムがデフォルトで割り当てるスタックサイズは１MBです。

プロジェクト プロパティページ にある
「構成プロパティ」→「リンカー」→「システム」の「スタックサイズの設定」で
100000000（←100MB）
など1MBより大きい値を設定してみてください。
（コマンドラインの場合は、/STACK:100000000 です）
ページトップ
sleep

Re: スタックオーバーフローの回避方法について

#4

投稿記事 by sleep » 10年前

あと、メモリ確保に成功すれば
ヒープでもスタックでも参照できていれば動作に差異は生まれません。
（片方だけ不安定になるということはありえません）

動作が不安定になる、というのがどういう状態なのか分かりませんが
メモリ確保とは別の要因に思えます。
ページトップ
蟻さん

Re: スタックオーバーフローの回避方法について

#5

投稿記事 by 蟻さん » 10年前

3D_3D さんが書きました:変数をメインの外に移動してみて下さい。
もしくは、大きめの配列はmalloc()かnewでメモリ確保をして下さい。
malloc/newを使う場合はメモリリークしないように注意して下さい。
回答ありがとうございます。配列の宣言をmalloc()で定義しなおそうと思いましたがどうやら他の回答してくださった方の回答によると「メモリ確保に成功すればヒープでもスタックでも参照できていれば動作に差異は生まれません。」とのことなのでVisual C++のスタックサイズを変更してプログラムは不安定ながら動いていることからメモリ確保以外に問題があると考えました。
ページトップ
蟻さん

Re: スタックオーバーフローの回避方法について

#6

投稿記事 by 蟻さん » 10年前

sleep さんが書きました:あと、メモリ確保に成功すれば
ヒープでもスタックでも参照できていれば動作に差異は生まれません。
（片方だけ不安定になるということはありえません）

動作が不安定になる、というのがどういう状態なのか分かりませんが
メモリ確保とは別の要因に思えます。
回答ありがとうございます。恐縮ですがスタックサイズの変更は既に試しました。スタックサイズの変更をするとスタックオーバーフローのエラーは無くなりますが別の問題が発生します。
このプログラムはある動作をMAX_ITAR回、つまり10000回実行するのですがメモリ確保が少ない14都市の場合では10000回正常に実行して終了することができるのですが今回の100都市の場合では必ず380回前後でプログラムが止まってしまいます。ブレークポイントを生成してローカルウィンドウを表示させてデバッグしてもなぜか変数が1つも表示されないので原因を掴む事ができていません。
ページトップ
アバター
softya（ソフト屋)
副管理人
記事: 11677
登録日時: 15年前
住所: 東海地方
連絡を取る:
softya（ソフト屋) に連絡する

Re: スタックオーバーフローの回避方法について

#7

投稿記事 by softya（ソフト屋) » 10年前

リリースビルドでデバッグされていませんか？
by softya（ソフト屋) 方針：私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います（代わりの方がいる保証は出来かねます）。
ページトップ
sleep

Re: スタックオーバーフローの回避方法について

#8

投稿記事 by sleep » 10年前

とりあえず、無限ループに陥るバグがありますね。

95～97行目のループで break となる条件が満たせず、maxに100が設定されるケースがあります。
蟻さん さんが書きました:

コード: 

                for(ip=0;ip<CITY_NUM;ip++){// 都市を確率的に選択
                    if((s[ip]>rn)&&(p[ip]>0)) break;
                }
                max=ip;
例えば、flag[1]が 0だったとき、
flag[max] に 1を設定した後に107～112行目のループで
flag[1]を見て 0 なので、breakで抜けて再度同じループに入る、という行為を繰り返します。

また、それが原因で
77行目の計算などで 添え字に0～99までしか指定できない配列へ
maxに100が入っているため、添え字に100が指定されたりします。
（phe[100][2] とか dist[100][2] など）
ページトップ
蟻さん

Re: スタックオーバーフローの回避方法について

#9

投稿記事 by 蟻さん » 10年前

softya（ソフト屋) さんが書きました:リリースビルドでデバッグされていませんか？
回答ありがとうございます。確認したところリリースビルドでデバッグしてはないようです。
ページトップ
蟻さん

Re: スタックオーバーフローの回避方法について

#10

投稿記事 by 蟻さん » 10年前

sleep さんが書きました:とりあえず、無限ループに陥るバグがありますね。

95～97行目のループで break となる条件が満たせず、maxに100が設定されるケースがあります。
蟻さん さんが書きました:

コード: 

                for(ip=0;ip<CITY_NUM;ip++){// 都市を確率的に選択
                    if((s[ip]>rn)&&(p[ip]>0)) break;
                }
                max=ip;
例えば、flag[1]が 0だったとき、
flag[max] に 1を設定した後に107～112行目のループで
flag[1]を見て 0 なので、breakで抜けて再度同じループに入る、という行為を繰り返します。

また、それが原因で
77行目の計算などで 添え字に0～99までしか指定できない配列へ
maxに100が入っているため、添え字に100が指定されたりします。
（phe[100][2] とか dist[100][2] など）
回答ありがとうございます。この無限ループのところを直せば問題は解決されるかもしれません。大変、参考になりました。
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る