交叉について

c言語を使い始めて、ＴＳＰについて勉強中で、遺伝的アルゴリズムの交叉（順序交叉）について以下のプログラムを作ってみたのですが、凄く遅いです。答えはきちんと出るのですが、循環交叉を取り入れたプログラムは5000ループでも１秒弱で出るのに対して２０秒近くかかってしまいます。ループに無駄が多そうなのですが思いつきません。ヒントでも宜しいのでご教授下さい。
順序交叉とは、例えば
x[i] = 3,4,5,2,1とy[i] = 4,3,5,1,2(i = 0～)という数字が与えられたときtargetを2とすると
x[i] = 3,4, y[i] = 4,3まではそのまま受け継ぎ、3以降は相手方の数字を左から順番に使われていないものを取り入れていくものです。この場合だと、x[i] = 3,4,5,1,2 y[i] = 4,3,5,2,1となります。

#define a 5
int main(void)
{
　　　int x[a] = {3, 4, 5, 2, 1}, y[a] = {4, 3, 5, 1, 2};
　　　int target, i, j, k, l;
　　　int x2[a], y2[a];
　　　srand((unsigned)time(NULL));

　　　target = rand () % a;
　　　for (i = 0; i < target; i++) {
　　　　　　x2[i] = x[i];
　　　　　　y2[i] = y[i];
　　　}
　　　for (i = target; i < a; i++) {
　　　　　　x2[i] = 0;
　　　　　　y2[i] = 0;
　　　}
　　　j = 0;
　　　k = 0;
　　　while (k != a - target) {
　　　　　　for (i = 0; i < target + k; i++) {
　　　　　　　　　for (l = 0; l < target + k; l++) {
　　　　　　　　　　　　if (x2[l] == y[j])
　　　　　　　　　　　　　　　j++;
　　　　　　　　　}
　　　　　　}

　　　　　　if (x2[target + k] != y[j]) {
　　　　　　　　　x2[target + k] = y[j];
　　　　　　　　　k++;
　　　　　　　　　j++;
　　　　　　}
　　　　　　else
　　　　　　　　　j++;
　　　}
　　　ｙについても同様の作業です

}

No.1 ベストアンサー 回答者： osamuy 回答日時： 2005/10/01 12:20

パッと思いついたところだけ。

出現済みチェック（かな?）の二重ループ。jがインクリメントされなければ、次のiのループでもインクリメントされないので、ループしなくても良いかと。こんな感じ：

while (k != a - target) {
for (i = 0; i < target + k; i++) {
int prev_j = j; // jを記憶。
for (l = 0; l < target + k; l++) {
if (x2[l] == y[j])
j++;
}
printf( "j: %d->%d?n", prev_j, j ); //デバッグ用。
if ( prev_j == j ){break;} // jに変化無ければブレーク。
}

遺伝子が重複無く存在するような表現式なのだとしたら、以下のやり方でもいけるかも。

for (i = 0; i < target; i++) { // 交叉直前まで遺伝。
x2[i] = x[i];
}
for (i = 0; i < a; i++) { // 片親を作業領域にコピー。
y2[i] = y[i];
}
for ( j = 0; j < target; j++ ){
for ( i = 0; i < a; i++ ){
if ( x2[j] == y2[i] ){ y2[i] = 0; } // 既に遺伝済みのものは引き継がないよう片親側に0でマーク。
}
}
i = 0;
for( k = target; k < a; k++ ){　// 片親から残りを遺伝。
while ( y2[i] == 0 ){ i++; } // マークされている部分をスキップ。
x2[k] = y2[i++];
}
}

この回答へのお礼

有難う御座いました。おかげで、循環交叉と同じ位のスピードで処理出来るようになりました。大変勉強になりました。また質問するようなことがあったら宜しく御願い致します。

お礼日時：2005/10/01 17:24