交叉について
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++;
}
ｙについても同様の作業です
}
お礼
ありがとうございます。そうですよね、「交叉」の 言葉の意味だけで考えてもそうじゃないとおかしい ですよね。回答を頂いて、改めてインターネットの 文献を読み返したところ、(2)の意味で使われている ものであったことがわかりました。つまり、私の勘違 いでした。（でも表現の仕方が紛らわしかったと言い 訳させて頂きます・・・） とってもすっきりです。ありがとうございました。