掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.29382

巡回セールスマン問題続き
投稿者---かわの(2007/01/09 20:24:32)


厳密解のプログラムはしたのようになります。これを改良すればいいと思うのですがどうしてよいかわかりません。
#difine YES (1)
#difine NO (0)

if(d == n){
for(i = 0; i < n-1;,i++)
length += dist[[a[i]][a[i+1]];
length += dist[a[n-1][a[0]];
if(length < min){
min = length;
for(i = 0; i<n;, i++)
mina[i] = a[i]
}
}
else{
for(i =1; i < n; i++){
if (used[i] == NO){
a[d] = i
used[i] = YES
perm(d+1)
used[i] = NO;
}
}
}


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:巡回セールスマン問題続き 29387 ぽへぇ 2007/01/09 22:18:47


No.29387

Re:巡回セールスマン問題続き
投稿者---ぽへぇ(2007/01/09 22:18:47)



以下の変数(?)とNo.29380で示された隣接行列の関係が不明です。

dist[]
a[ ]
used[ ]
perm(d+1)
mina[i] = a[i]

「これを改良すればいい」と思う根拠は何ですか?



この投稿にコメントする

削除パスワード

No.29391

Re:巡回セールスマン問題続き
投稿者---かわの(2007/01/10 12:48:34)


 ご返信ありがとうございます。挙げられた変数の意味も含めた自分でつくってみた厳密解のプログラムは下のようになります。改良してできる根拠は特になく改良してできればいいなという願望のようなものです。どうにか貪欲法で巡回セールスマン問題の近似解を得るプログラムをつくりたいのですがどうしていいかわかりません。


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

int n, a[MAXN+1], used[MAXN+1], dist[MAXN+1][MAXN+1];
int mina[MAXN+1];
int min = 10000
void perm(int d);

int main(int argc, char **argv)
{
int i, j;
FILE *fp; //開くためのファイルへのポインタをFILE型として宣言する

if (argc != 2) { //実行ファイル(a.out)とファイル名の2語以外の入力なら強制終了
printf("Usage: %s <filename>\n", argv[0]);
exit(1);
}

fp = fopen(argv[1],"r"); //実際にファイルを開く。詳細は%man fopenで
if (fp == NULL) {
printf("File not found.\n");
exit(1); //ファイルが開けなかったときは強制終了
}

fscanf(fp, "%d", &n); //最初の値はグラフの頂点数

if ((n > MAXN) || (n < 0)) { //範囲外の頂点数の場合は強制終了
printf("Out of range: n.\n");
exit(1);
}

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
fscanf(fp, "%d", &dist[i][j]); //隣接行列のデータの読みこみ
}
}

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", dist[i][j]); //隣接行列のデータの出力
}
printf("\n");
}

for (i = 0; i < n; i++) used[i] = NO; //始めはどの値も使っていない
perm(0);
printf("%d",min);
printf("\n");
for(i = 0; i < n; i++) printf("%d", mina[i]);
printf("\n");
}

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

if (d == n) {
for(i = 0; i < n; i++) printf("%d", a[i]);
printf("\n");
for(i = 0; i < n-1;,i++)
length += dist[[a[i]][a[i+1]];
length += dist[a[n-1][a[0]];
if(length < min){
min = length;
for(i = 0; i < n;, i++)
mina[i] = a[i];
}
}
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; // iを使ったことを忘れる
}
}
}
}



この投稿にコメントする

削除パスワード

No.29397

Re:巡回セールスマン問題続き
投稿者---ぽへぇ(2007/01/10 19:17:23)


>自分でつくってみた厳密解のプログラム。
ウソは感心しませんな。

少なくとも自分でプログラムを書いて、No.29380 に示された
テストケースを「そのまま」食わしたことがあるんだったら、
頂点数が0になることくらい知っているはずですよね?

コンパイルが通らないプログラムを貼るのも問題外。
あと、HTML変換ツールって知ってます?

ツッコミだけでは進展しないのでヒントを示します。
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec10-1.html




この投稿にコメントする

削除パスワード

No.29404

Re:巡回セールスマン問題続き
投稿者---かわの(2007/01/11 18:43:45)


文献を調べそれらをつなぎ合わせたプログラムで厳密には自分でつくってみた厳密解のプログラムではないかもしれません。申し訳ありません。ヒントのサイトを元に考えて見ます。



この投稿にコメントする

削除パスワード

No.29416

Re:巡回セールスマン問題続き
投稿者---ぽへぇ(2007/01/12 06:28:30)


>文献を調べそれらをつなぎ合わせたプログラムで厳密には自分でつくってみた厳密解の
>プログラムではないかもしれません。申し訳ありません。
>ヒントのサイトを元に考えて見ます。

どうしてこう裏目裏目に出るかなぁ。
 テストケースも、プログラムも少し修正するだけで
(テストケース程度の規模なら)厳密解が求まるものになります。
でもそういった修正を掲示板の皆さんに要求(期待)するのは
良くないでしょう。

もう消されちゃったけど、テストケースでは dist[a][b] != dist[b][a]
なんですね。そういうテストケースだ、ということだけでも面白い例題だったんですが。
(レスがついた投稿を消すという行為もマナー違反ですぞ)

叩くこと自体は目的ではない。でも自助努力はして欲しい。
叩かれたのも良い経験だと思ってがんばってくれとしか
書きようがない orz...



この投稿にコメントする

削除パスワード

No.29517

Re:巡回セールスマン問題続き
投稿者---ぽへぇ(2007/01/20 12:44:06)


>でもそういった修正を掲示板の皆さんに要求(期待)するのは
>良くないでしょう。
ローカルで修正して貼らないのも何なので、貼ってみます。

// テストケース
5
0 3 4 2 3
1 0 2 5 8
7 5 0 6 1
3 5 8 0 4
6 4 3 2 0

// プログラム
#include    <stdio.h>

#define MAXN (100)
#define YES (1)
#define NO (0)

int n;            // 巡回すべき頂点数
int a[MAXN+1];            // 巡回経路(お試し経路)
int used[MAXN+1];            // 巡回済か否か
int dist[MAXN+1][MAXN+1];    // 隣接行列 dist[a][b] 頂点aから頂点bまでの距離(コスト)
int mina[MAXN+1];         // 最小コストが得られる巡回経路
int min = 10000;

void perm(int d);

int main(int argc, char **argv)
{
    int  i, j;
    FILE*   fp;
    if (argc != 2) {
        // 実行ファイル(a.out)とファイル名の2語以外の入力なら強制終了
        printf("Usage: %s <filename>\n", argv[0]);
        exit(1);
    }
    fp = fopen(argv[1], "r");
    if (fp == NULL) {
        printf("File not found.\n");
        exit(1);
    }
    //  最初の値はグラフの頂点数
    fscanf(fp, "%d", &n);
    //  範囲外の頂点数の場合は強制終了
    if ((n > MAXN) || (n <= 0)) {
        printf("Out of range: n.\n");
        exit(1);
    }
    //  隣接行列のデータの読みこみ
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            fscanf(fp, "%d", &dist[i][j]);
        }
    }
    //  隣接行列のデータの出力
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
    //  始めはどの値も使っていない
    for (i = 0; i < n; i++) {
        used[i] = NO;
    }
    perm(0);    //  探索
    // 最短経路(距離合計)の表示
    printf("%d\n", min);
    // 最短経路(訪問順序)の表示
    for (i = 0; i < n; i++) {
        printf("%d", mina[i]); 
    }
    printf("\n");
}

/* 深さdの節点を根とする木を作成する関数 */
void perm(int d)
{
    int i;
    int length = 0;
    if (d == n) {
        ///// 深さ == 頂点数
        //     -> 高いか安いかは不明だが、何か一つ(お試し)経路ができた
        //  現在のお試し経路を表示
        for (i = 0; i < n; i++) {
            printf("%d", a[i]);
        }
        printf("\n");
        //  経路にしたがって距離(コスト)を総和
        for (i = 0; i < n-1; i++) {
            length += dist[ a[i] ][ a[i+1] ];
        }
        // 最後に最終点から開始点へのコストを加える
        length += dist[ a[n-1] ][ a[0] ];
        // よりコストが少ない訪問順が得られたら記録する
        if(length < min) {
            min = length;
            for (i = 0; i < n; i++) {
                mina[i] = a[i];
            }
        } 
    } 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; // iを使ったことを忘れる
            }
        }
    }
}




この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧