巡回セールスマン問題の解を求めるプログラムを作ったのですが、これでは全ての回路が表示されてしまいます。最小値だけでしかも順列の最初の値が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件)
- 最新から表示
- 回答順に表示
No.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は同じになります。
もしよろしければサンプルをいただけないでしょうか?
No.1
- 回答日時:
回答ではありませんが・・・
2ちゃんねるの方が恐らくこういった専門的な知識を持っている方は多いとおもいますので、こちらで良い回答が得られなかった場合、そちらで聞いてみてはいかがでしょうか?
「C言語のことなら俺に聞け!」ってレスもあったような気がします。ご参考までにどうぞ
参考URL:http://www2.2ch.net/2ch.html
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# 10個の実数に対する降順ソート結果を出力するプログラムを作りたいのですが、以下のプログラムをどう直せ 1 2022/07/09 22:16
- C言語・C++・C# 並列プログラミングのπ計算について 1 2022/07/16 22:30
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語について
-
unsigned int型について
-
2の累乗を計算するプログラム...
-
strcmp
-
コマンドラインに出力した文字...
-
平均合計偏差値標準偏差の出し方
-
10個出力で改行したいのですが...
-
既約分数の表示プログラム
-
switch分のケースを範囲数?に...
-
WM_CLOSEで閉じれないウィンド...
-
【C言語教えてください】sin波...
-
じゃんけんゲーム
-
ifなんですが
-
C言語の勉強しています。すみま...
-
小数点切捨て表示
-
c言語でAからZまでを表示する...
-
C言語に関する質問です
-
C言語の数値入力
-
2つ分数の四則演算を行うプロ...
-
改行について 1行に何個かづ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
printf で二進表示を行いたい。
-
%P と %X の違い
-
【C言語教えてください】sin波...
-
テキストカーソル位置の取得
-
10個出力で改行したいのですが...
-
cshの文字列操作(0埋め)
-
コンパイルエラーについて
-
コマンドラインに出力した文字...
-
ifなんですが
-
strcmp
-
c言語でAからZまでを表示する...
-
なぜgccはstdio.hをインクルー...
-
(C言語)西暦年月日を入力して...
-
error C2143: 構文エラー : ';'...
-
三角形の判別
-
4の倍数を論理演算で表す。。
-
printfの出力内の文字をdefine...
-
scanfに文字が入力されたときに...
-
unsigned int型について
-
C言語について
おすすめ情報