プロが教えるわが家の防犯対策術!

巡回セールスマン問題の解を求めるプログラムを作ったのですが、これでは全ての回路が表示されてしまいます。最小値だけでしかも順列の最初の値が0の回路だけを表示させるにはどうすればいいのでしょうか?どなたか教えてください。長くてすいません。

#include<stdio.h>
#define MAXN (100)
#define YES (1)
#define NO (0)

void perm(int d);
int n, a[MAXN], used[MAXN];
int dist[MAXN][MAXN];

int main(void)
{
int i;
int j;

// printf("Input n: ");
scanf("%d", &n);

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &dist[i][j]);
}
}

if (n > MAXN) {
printf("Change the value MAXN.\n");
exit(1);
}
else if (n < 0) {
printf("Error!(Input nonnegative integer.)\n");
exit(1);
}

for (i = 0; i < n; i++) used[i] = NO; /* 始めはどの値も使っていない */
perm(0);

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%2d ", dist[i][j]);
}
printf("\n");
}
}

/* 深さdの節点を根とする木を作成する関数 */
void perm(int d)
{
int i;

if (d == n) {
for(i = 0; i < n; i++) printf("%d", a[i]);
printf("\n");
}
else {
for (i = 0; i < n; i++) {
if (used[i] == NO) {
a[d] = i; /* 配列のd番目にiを代入する */
used[i] = YES; /* iを使ったことを記憶する */
perm(d + 1); /* 再帰呼び出し */
used[i] = NO; /* 命令文を追加する */
}
}
}
}

A 回答 (2件)

回答する前に色々聞きたい点・つっこむところがあるので…


全解探索はNP完全問題なので最適解を得る為には止むを得ないとして(n=100だとすごい事になるな)、「始点が0で最小値のパス」って…TSPの意味は判っているのでしょうか?TSPは始点が決まっているので始点0以外のルートは計算するだけ無駄なんですが…終点(=始点)も表示しないプログラムだし…
入力から察するとすべてのノードはn-1の次数を持つってことかな。再帰関数を使っている意味は?少なくともこの書き方だとあまり意味がない気もしますが。
stdlib.hは書き忘れですか?

まだ回答を得ていないならサンプルをあげます。再帰は使わないですけどね。

この回答への補足

回答ありがとうございます。
始点が0というのは、もともと重みつきグラフがあたえられていて、その各点に番号が与えられている(例えば4点なら0,1,2,3)ので、0→1→2→3→0と、1→2→3→0→1は同じになります。
もしよろしければサンプルをいただけないでしょうか?

補足日時:2005/11/25 12:53
    • good
    • 0

回答ではありませんが・・・



2ちゃんねるの方が恐らくこういった専門的な知識を持っている方は多いとおもいますので、こちらで良い回答が得られなかった場合、そちらで聞いてみてはいかがでしょうか?

「C言語のことなら俺に聞け!」ってレスもあったような気がします。ご参考までにどうぞ

参考URL:http://www2.2ch.net/2ch.html
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!