初期集団の生成

[ｐｋｔ]

現在大学で遺伝的アルゴリズムについて学んでいます。
今回は初期集団をランダムでだし、重ならないようにするプログラムを行っています。
しかし、エラーはないのですが、結果がうまく表示されません。よければご意見いただけると助かります。

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

#define PS 10 /*遺伝子プール*/
#define GL 10 /*長さ*/
#define start 0/*スタート*/
#define goal 9/*ゴール*/
int xrand(int, int);
int main(void)
{
	int p[PS][G[/url];
	int g[G[/url];
	int i,j,k,m;
	int rnd;
	srand((unsigned)time(NULL));
	printf("初期集団\n");
	for(i=0;i<PS;i++){
		for(j=1;j<GL-1;j++){
			rnd=xrand(2,8);
			g[rnd]=1;
			if(g[j]==0){
				p[j]=rnd;
			}else{
				continue;
			}
			//printf("%d",p[j]);
		}
		//printf("\n");
	}

	for(i=0;i<PS;i++){
		for(j=0;j<GL;j++){

			if(j==0){
	p[0]=start;
			}else if(j==9){
	p[j]=goal;
			}
			printf("%d",p[j]);
		}
			printf("\n");
	}
}
int xrand(int lower, int upper)
{
    return (upper - lower + 1) * (int)rand() / 32768 + lower;
}

よろしくお願いいたします。

[ｐｋｔ]

言葉が足りてないですね。乱数でだし、同じ数値が出ないようにしたいのです。
1334425などのようなものを出したくないのです。

[non]

原因の１つめは、
g[G[/url]を初期化していないこと。
２つめは、
既に使った数字の場合、continueしていること。
よくわからないのは、乱数の発生xrandが２から８の範囲だけど、
start=0でgoal=9なら１から８の乱数を発生させるのでは？

[ｐｋｔ]

レスありがとうございます。
1つ目の初期化については理解することができます。
２つめのcontinueのほうがいまいち理解できません。
最後の指摘はおっしゃる通りです。ありがとうございます

[conio]

>>２つめのcontinueのほうがいまいち理解できません。 

とりあえず、1～10までの乱数を発生させるとします。
で、「既に使った数字ならcontinue」と言う風にすると、もし数字が被った場合
何も値が入らないまま処理が次へ進むことになります。
--------------------------------------------------------
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

int main(void)
{
	srand((unsigned int)time(NULL));
	int Value[10] = {0};
	int g[10] = {0};

	for(int i = 0; i < 10; i++){
		int Num = rand() % 10 + 1;

		if(g[Num - 1] == 0){
			Value = Num;
			g[Num - 1] = 1;
		}else{
			continue;
		}
	}

	for(int i = 0; i < 10; i++){
		printf("Value[%d] = %d\n",i, Value);
	}

	return(0);
}

【実行結果】
Value[0] = 8
Value[1] = 6
Value[2] = 2
Value[3] = 0　　←数字が被り、値を設定する処理が飛ばされている。
Value[4] = 7
Value[5] = 0　　←数字が被り、値を設定する処理が飛ばされている。
Value[6] = 0　　←数字が被り、値を設定する処理が飛ばされている。
Value[7] = 5
Value[8] = 0　　←数字が被り、値を設定する処理が飛ばされている。
Value[9] = 0　　←数字が被り、値を設定する処理が飛ばされている。
続行するには何かキーを押してください . . .
--------------------------------------------------------

実行結果を見てもらえば分かりますが、値を入れる処理が行われなかった場合は初期値のままです。
これは、「被らない乱数を発生させる」という意図に反する結果です。

[ｐｋｔ]

なるほど。回答ありがとうございます。
continueでは、入力されないまま次へ行ってしまう。ということですね。
となると、処理の方法は全く別なものを考えないといけないっぽいですね・・・。

[ｐｋｔ]

皆様の意見を参考に作りなおしてみました。
しかし、わからないところが出てきてしまいましたので、再度質問させてください。

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

#define PS 10 /*遺伝子プール*/
#define GL 10 /*長さ*/
#define start 0/*スタート*/
#define goal 9/*ゴール*/
int xrand(int, int);
int main(void)
{
	int p[PS][G[/url];
	int g[GL-1]={0,0,0,0,0,0,0,0,0};
	int i,j,k,m;
	int rnd=0;
	srand((unsigned)time(NULL));
	printf("初期集団\n");
	for(i=0;i<PS;i++){
		for(j=1;j<GL-1;j++){
			rnd=xrand(1,8);
			if(g[rnd]==0){　// ここから
			  p[j]=rnd;
			}else{
				p[j]=0;
			}              // ここまで
			g[rnd]=1;
			//printf("%d",p[j]);
		}
		//printf("\n");
	}

	for(i=0;i<PS;i++){
		for(j=0;j<GL;j++){

			if(j==0){
	p[0]=start;
			}else if(j==9){
	p[j]=goal;
			}
			printf("%d",p[j]);
		}
			printf("\n");
	}
}
int xrand(int lower, int upper)
{
    return (upper - lower + 1) * (int)rand() / 32768 + lower;
}

印をつけさせていただいたところの処理がうまくいきません。
あいているところに１～８をすべて収めたいのですが・・・何か良いアイデアはありますでしょうか？
p[j]=0;
というのは、まだなにも思いついてなくて仮にいれてあります。
現在のプログラムの実行結果では
初期集団
0126870009
0040030009
0500000009
0000000009
0000000009
0000000009
0000000009
0000000009
0000000009
0000000009
続行するには何かキーを押してください . . .
のように2次元配列すべてのなかで、重ならない数字が出てきてしまいます。
きっとelse文での処理が重要なのだと思うのですが・・・
ご意見いただけると嬉しく思います

[conio]

一つの考え方としては、
----------------------------------------------------------------------------------------------
【１】乱数を生成する
【２】その乱数が、今まで代入してきたどの値とも一致していなければ【３】へ。被っていれば【１】へ。
【３】値を代入し、配列の一番最後の要素でなければ【１】へ。　一番最後であれば終了。
----------------------------------------------------------------------------------------------

例えば int Num[10];があり、Num[5]に8を代入しようとするとします。
この場合はNum[0]　～　Num[4]まで探索し、8が無いかを探します。
---------------
┃Num[0] = 1
┃Num[1] = 2
┃Num[2] = 6
┃Num[3] = 4
▼Num[4] = 7
---------------
この場合だと8は存在しないので、Num[5]に8を代入します。

---------------
┃Num[0] = 1
┃Num[1] = 2
┃Num[2] = 6
┃Num[3] = 4
▼Num[4] = 8
---------------
この場合は、Num[4]に8があるので、もう一度乱数を生成し直します。
そして、もういちどNum[0]　～　Num[4]まで探索します。


それと、もう一つの考え方としては、
---------------------------------------------
【１】予め、代入する値の配列を定義しておく
【２】配列の要素をランダムに入れ替える
【３】添え字の順番どおりに代入していく
---------------------------------------------
です。

例えば、まず1　～　9　までの配列を定義しておきます。
int temp[9] = {1,2,3,4,5,6,7,8,9};

そして、内部の要素を入れ替えます。
---------------------------------------
【前】内部の要素⇒ 1 2 3 4 5 6 7 8 9
【後】内部の要素⇒ 9 4 5 6 7 2 3 8 1
---------------------------------------

後は単純に、順番通りに代入して行くだけです。
----------------------------
for(int i = 0; i < 9; i++)
    Num = temp;
----------------------------

で、前者と後者の場合は、後者の方が効率は良いです。
前者の場合は、被った乱数を生成する場合がある（特に、後半は高確率で被る）からです。

後者の場合は、プログラムの仕組み上、絶対に被る事はありません。



あと、とりあえず　最後のこの部分ですが、
--------------------------------------------------------
	for(i=0;i<PS;i++){
		for(j=0;j<GL;j++){

			if(j==0){
	p[0]=start;
			}else if(j==9){
	p[j]=goal;
			}
			printf("%d",p[j]);
		}
			printf("\n");
	}
--------------------------------------------------------


↓こうした方が良いと思います。
--------------------------------------------------------
for(i=0;i<PS;i++){
    p[0] = start;	
    p[9] = goal;
    for(j=0;j<GL;j++){
        printf("%d",p[j])
    }
    printf("\n");
}
--------------------------------------------------------

むしろ、最初のfor文で値の代入はやっておいて、最後のfor文ではprintf関数のみ（表示する処理のみ）
にした方が良いと思います。

[ｐｋｔ]

ご意見ありがとうございます。
どちらの方法も判り易く説明していただいて助かります。
前者の2の操作なのですが、３へ進む、１へ戻るの処理の方法がなかなか難しく悩んでおります。
戻るという処理を今まで書いたことがないというのもありますが・・・
よければ、処理方法の例などを参考にさせていただけないでしょうか？
申し訳ありません。

[conio]

「条件が達成できるまで繰り返す」というのはdo while文を使ったりします。
自分は一応こんな感じにしました。
---------------------------------------------------------------------------
do{
    flag = 0
    //乱数を生成し、被っていればflag = 1　（繰り返す）
    //被っていなければ何もしない。　(flag に0が代入されているので、do while文を抜ける)
}while(flag);
---------------------------------------------------------------------------

前回の記述との対応関係はこんな感じでしょうか。
---------------
do{
    flag = 0;
    【１】
    【２】
}while(flag);
【３】
---------------



全体のプログラムの中でいうと、赤字の部分です。
このままコピーペーストで実行できます。
-----------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main(void)
{
	srand((unsigned int)time(NULL));
	int Value[10][10] = {0};

	for(int i = 0; i < 10; i++){
		Value[0] = 0;
		Value[9] = 9;
		for(int j = 1; j < 10 - 1; j++){
			int temp;
			int flag;
			do{
				flag = 0;
				temp = rand() % 8 + 1;
				for(int k = 1; k <= j; k++){  //被っていないか以前の要素を探索
					if(temp == Value[k]){
						flag = 1;
						break;
					}
				}
			}while(flag);
			Value[j] = temp;
		}
	}

        //表示処理
	for(int i = 0; i < 10; i++){
		printf("Value[%d] = ",i);
		for(int j = 0; j < 10; j++){
			printf("%2d", Value[j]);
		}
		puts(" ");
	}

	return(0);
}
-----------------------------------------------------------------------

[non]

なるべく、元のプログラムを尊重しました。

#define PS 10 /*遺伝子プール*/
#define GL 10 /*長さ*/
#define start 0/*スタート*/
#define goal 9/*ゴール*/
int xrand(int, int);
int main(void)
{
	int p[PS][G[/url];
	int g[G[/url];
	int i,j,k,m;
	int rnd;
	srand((unsigned)time(NULL));
	printf("初期集団\n");
	for(i=0;i<PS;i++){
		for(j=1;j<GL-1;j++)
			g[j]=0;
		for(j=1;j<GL-1;j++){
			do{
				rnd=xrand(1,8);
				if(g[rnd]==0)
					break;
			}while(1);
			p[j]=rnd;
			g[rnd]=1;
			//printf("%d",p[j]);
		}
		//printf("\n");
	}

	for(i=0;i<PS;i++){
		for(j=0;j<GL;j++){

			if(j==0){
				p[0]=start;
			}else if(j==9){
				p[j]=goal;
			}
			printf("%d ",p[j]);
		}
			printf("\n");
	}
	return 0;
}

[ｐｋｔ（自宅）]

すごくわかりやすく説明していただいて助かりました。
ありがとうございました。
さらにここに

const char list[kaz[/url][6]={
	1,2,3,-1,-1,-1,/*A*/
	0,2,5,8,-1,-1,/*B*/
	0,1,3,4,5,-1,/*C*/
	0,2,4,-1,-1,-1,/*D*/
	2,3,5,6,-1,-1,/*E*/
	1,2,4,6,7,-1,/*F*/
	4,5,9,-1,-1,-1,/*G*/
	5,8,9,-1,-1,-1,/*H*/
	1,7,-1,-1,-1,-1,/*I*/
	6,7,-1,-1,-1,-1/*J*/};

のような隣接リストの情報を加え、より経路探索のための初期集団にしていこうと思っています。
この隣接リストの関連付けを行う方法を調べていたのですが、予想以上に進みませんでした。
どのような方法で行うのがよいのでしょうか？教えていただけると嬉しく思います。

[non]

誰からもRESがない理由は、意味がわからないからです。
あなたと同じ、授業を受けているわけではありませんので、
世間一般でわかるように説明してもらわないと、なんのことを質問
されているのかわかりません。

[ｐｋｔ（自宅）]

そうですね。すいません。言葉が全く足りてませんね。

const char list[kaz[/url][6]={
	1,2,3,-1,-1,-1,/*A*/
	0,2,5,8,-1,-1,/*B*/
	0,1,3,4,5,-1,/*C*/
	0,2,4,-1,-1,-1,/*D*/
	2,3,5,6,-1,-1,/*E*/
	1,2,4,6,7,-1,/*F*/
	4,5,9,-1,-1,-1,/*G*/
	5,8,9,-1,-1,-1,/*H*/
	1,7,-1,-1,-1,-1,/*I*/
	6,7,-1,-1,-1,-1/*J*/};

上のプログラムはノードのつながりを表していまして
Ａの点とＢ、Ｃ、Ｄ
Ｂの点とＡ、Ｃ、Ｆ、Ｉ
とつながっているという事を表したリストになります。
これをプログラムに関連付けることによって
０の次は１，２，３のうちの１つをランダムで出す。
１の次は０，２，５，８からランダムで１つ出す。
のようなプログラムを作りたいのですが、関連付けのさせ方がわからず困っていました。
方法としてはどのようなものがあるのでしょうか？

[conio]

おおまかな流れはこんな感じでしょう。
-------------------------------------------------------
【1】それぞれの遷移先の数を調べる。
【2】rand()の値を、遷移先の数で割った余りを求める。
【3】その余りを添え字として使い、配列の値を得る。
【4】得られた配列の値を、現在の状態とする。
-------------------------------------------------------


まず遷移先の数を求めます。

"A"の場合は3です。
"A"の遷移先の数は3なのでその余りを求めます。
--------------------------------------------
temp = rand() % 3; //0～2の値が出る。
--------------------------------------------

その結果を添え字として使います。
-------------------------------
NowState = list[NowState][temp];
-------------------------------

NowStateには、list[0][0]、list[0][1]、list[0][2]のどれかの値が入ることになります。
（つまり、1・2・3のどれか）

また遷移する場合は、上記の計算を全く同じ方法で行うだけです。
"B"の遷移先の数は4で、　temp = rand() % 4;　・・・・みたいな。

あと、添え字に使うので、listはchar型ではなく、int型がいいと思います。

[non]

ぱっと、conioさんの文章を読んだだけなので、勘違いかもしれないけど、
既に使ったノードかをチェックして乱数を再発生する必要がありそうです。
そうすると、ノードの順番によっては、先に進めなくなる可能性もあるかも。
すると、再帰呼び出しが必要かなぁ？
その場合は乱数でなくて、解が何通りあるかを全部出して、その中から
乱数で解を選んだ方がいいかもしれない。
ちょっと、絵でも描いて、なぞってみないとわかんないです。
pktさん、絵を描いてそんなことはありませんでしたか？
ところで、先頭は必ずAですか？

[non]

それから、最後はJ？

[ｐｋｔ（自宅）]

conioさんありがとうございます。少しみながら頑張ってみたいと思います。
nonさん、現在はＡからＪですが、ゴールはまだまだ伸びますので、複雑になるのかなぁとは思います。
教授にお聞きしたところ、最低でも100という答えがきてまして・・・

[non]

やっぱり、再帰がいいでしょうね。

[ｐｋｔ（自宅）]

再帰とはどのような方法なのでしょうか？
いままで自分がやろうと思っていたやり方とは全く別物な感じでしょうか？

[non]

再帰呼び出し、リカーシブコールで検索するといいでしょう。
考え方として、
題意から、
ネットワークの図を書いてみて下さい。
A,B・・・Fのノードは○で囲み、関連づけを線で繋ぎます。
この絵で、AからFまですべてのノードを通る一筆書きが求める解ですね。
あなたは、この解を紙と鉛筆でもれなく全ての解をみつけなければいけないと
したら、どのような方法をとりますか。
ＡからＢＣＤと３通りありますが、どの道を選ぶか、乱数で決めますか？
そんなことは、しないでしょう。
もれなく道を選ばなければいけないとしたら、まず、Ｂを選び、Ｂから行ける
道を全て試した後、Ｃ、Ｄと順番に試して行くでしょう。
すなわち、あるノードから順番に道に進んでいく、進めなくなったら、前に戻り
次の道を進むという方法を繰り返していくわけです。
これを実現するプログラムの方法が再帰呼び出しです。

今回、この課題が卒論などのゼミで行われているのであれば、自分で基本から
勉強することをお勧めします。ただ単に、授業の課題なら、解答例のプログラムを
お見せしてもかまいません。

[ｐｋｔ（自宅）]

今回の課題はここまでとなっています。
授業では、あまり詳しくやってくださらない教授なのでなかなか困っています。
自分でも再帰呼び出しについて調べてみました。
考え方はわかりましたが、なかなかプログラムとして上手くいきません。
よければ、助けていただけないでしょうか？

[non]

>今回の課題はここまでとなっています。
まだ、遺伝的アルゴリズムには入ってませんよ。
これから、もっと難しくなるので、理解することをお勧めします。

#include <stdio.h>
int list[10][6]={
	1,2,3,-1,-1,-1,/*A*/
	0,2,5,8,-1,-1,/*B*/
	0,1,3,4,5,-1,/*C*/
	0,2,4,-1,-1,-1,/*D*/
	2,3,5,6,-1,-1,/*E*/
	1,2,4,6,7,-1,/*F*/
	4,5,9,-1,-1,-1,/*G*/
	5,8,9,-1,-1,-1,/*H*/
	1,7,-1,-1,-1,-1,/*I*/
	6,7,-1,-1,-1,-1/*J*/};
int g[10]={0};
int p[10];
void disp_list(int m)
{
	int i;
	for(i=0;i<=m;i++)
		printf("%d ",p);
	printf("\n");
}
void make_list(int m,int n)
{
	int i;
	if(g[n]==1)
		return;
	p[m]=n;
	if(m==9 && n==9){
		disp_list(m);
		return;
	}
	g[n]=1;
	for(i=0;i<6;i++){
		if(list[n]!=-1)
			make_list(m+1,list[n]);
	}
	g[n]=0;
	return;
}
int main(void)
{
		make_list(0,0);
		return 0;
}