73272


このサイトで前回テキストについての質問をさせていただいたので、そのURLを以下に貼り付けます。  
[テキストから各列の最小値を読み込んで、それらの数値を足していくプログラム](https://ja.stackoverflow.com/questions/73143/%e3%83%86%e3%82%ad%e3%82%b9%e3%83%88%e3%81%8b%e3%82%89%e5%90%84%e5%88%97%e3%81%ae%e6%9c%80%e5%b0%8f%e5%80%a4%e3%82%92%e8%aa%ad%e3%81%bf%e8%be%bc%e3%82%93%e3%81%a7-%e3%81%9d%e3%82%8c%e3%82%89%e3%81%ae%e6%95%b0%e5%80%a4%e3%82%92%e8%b6%b3%e3%81%97%e3%81%a6%e3%81%84%e3%81%8f%e3%83%97%e3%83%ad%e3%82%b0%e3%83%a9%e3%83%a0)

前回質問した時、今回のことに関連するサイト"traveling salesman problem greedy algorithm C program"  
に入って、色々似ているプログラムを見つけたので、それを参考にここ数日考え、以下のようにプログラムをしたのですが、実行は出来るものの、結果がかなり期待するものとは異なってしまいました

[code]

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    const int FNLEN=50;          /* ファイル名の長さ */
    const int MAX_CITY=100;      /* 都市数最大値 */
    
    int main()
    {
      FILE *fp;
      int i,j,ncity,dept;
      int visit[MAX_CITY];  /* 0: 未訪問、1: 訪問済み (訪問したかどうか)*/
      int visit_list[MAX_CITY];  /* 訪問順 */
      double dist[MAX_CITY][MAX_CITY],total_dist,min_dist;
      char file_name[FNLEN];  /* データファイル名 */
        
      printf("Data file name: ");
      scanf("%s",file_name);
        
      if ((fp = fopen(file_name,"r")) == NULL){  /* ファイルオープンに失敗した場合は終了 */
        printf("%s: ファイルをオープンできません!\n",file_name);
        return -1;
      }
    
      /* ファイルからデータを読み込む　*/
      printf("データファイル名:   %s\n",file_name);
      fscanf(fp,"%d",&ncity);  /* 都市数の読み込み */
      
      if (ncity > MAX_CITY){
        printf("都市の数は%3d以下にしてください！\n",MAX_CITY);
        return -1;
      }
      
      for (i=0;i<ncity;i++){   /* 距離行列の読み込み */
        for (j=0;j<ncity;j++){
          fscanf(fp,"%lf",&dist[i][j]);
          printf("%10.3lf",dist[i][j]);
        }
        printf("\n");
      }
            
      fclose(fp);  /* ファイルクローズ */
    
      /* 出発する都市の都市番号をキーボード入力 */
      printf("出発地の都市番号(1--%3d)を入力して下さい。  ",ncity);
      scanf("%d", &dept);
      if (dept > ncity || dept < 0){
        printf("都市番号が無効です。\n");
        return(-1);
      }
      
      /* 配列 visit および visit_list の初期化 */
      for (i=0;i<ncity;i++){
        visit[i]=0;
        visit_list[i] = -1;
      }
        
      /* ---- 貪欲算法 start ---- */
      double min,cost;
      printf("順回路は\n");
      for(i=dept;i<ncity;i++){
        for(j=dept;j<ncity;j++){
        if(dist[i][j]!=0) 
          if(dist[i][j]<min){
              min=dist[i][j];
              printf("%d ",j);
              cost+=min;
          } 
         }
       }
       printf("総移動距離は%fです。\n",cost);       
      /* ---- 貪欲算法 end ---- */
        
       return 0;
    }
    
[/code]

[code]

    $ ./a.out
    Data file name: euro.txt
    データファイル名:   euro.txt
         0.000   340.000  1270.000  1450.000  2400.000   780.000
       340.000     0.000  1060.000  1120.000  2100.000   490.000
      1270.000  1060.000     0.000  1370.000  2370.000  1250.000
      1450.000  1120.000  1370.000     0.000  1040.000   700.000
      2400.000  2100.000  2370.000  1040.000     0.000  1620.000
       780.000   490.000  1250.000   700.000  1620.000     0.000
    出発地の都市番号(1--  6)を入力して下さい。  1
    順回路は
    総移動距離は0.000000です。
    
[/code]

期待する実行結果

[code]

    ata file name: euro.txt
    データファイル名:   euro.txt     
    0.000   340.000  1270.000  1450.000  2400.000   780.000   
    340.000     0.000  1060.000  1120.000  2100.000   490.000  
    1270.000  1060.000     0.000  1370.000  2370.000  1250.000  
    1450.000  1120.000  1370.000     0.000  1040.000   700.000  
    2400.000  2100.000  2370.000  1040.000     0.000  1620.000   
    780.000   490.000  1250.000   700.000  1620.000     0.000
    出発地の都市番号(1--  6)を入力して下さい。  1
    巡回路は    1    2    6    4    5    3    1
    総移動距離は  6210.000です。
    
    
[/code]

このように、期待する実行結果とは順回路と総距離の部分で出力が違います。  
プログラミング歴四ヶ月程度の自分なりにはかなり考えたのですが、自分的にはこれ以上は思いつきませんでした。  
不明な点、修正すべき点があれば、それをどのように修正すればいいのか教えてくれるととても助かります。


CC BY-SA 4.0
2021-01-12T12:46:35.727
73248
2021-01-13T13:32:45.820
2021-01-13T01:06:22.963
41837
41837
question
c
最近近傍法のC言語プログラミング

[code]

      /* ---- 貪欲算法 start ---- */
      double min,cost;
    
[/code]

と`min`を初期化せずに使用されているので

[code]

          if(dist[i][j]<min){
              min=dist[i][j];
              printf("%d ",j);
              cost+=min;
          } 
    
[/code]

このifブロックに入れないだけではないでしょうか。  
この場合、何で初期化すればよいかですが、適当な値を入れるより、読み込んだ値の中の最大値を入れておけば良いと思います。


CC BY-SA 4.0
2021-01-13T02:19:37.453
73257
2021-01-13T02:19:37.453
9515
73248
answer


`visit` や `visit_list` 配列が使われていないので、「巡回」という事を誤って解釈しているのではないでしょうか。

以下に変更箇所だけ載せておきます(ごく単純な greedy algorithm の実装例になります)。

[code]

    // import DBL_MAX
    #include <float.h>
                :
    
      /* 出発する都市の都市番号をキーボード入力 */
      printf("出発地の都市番号(1--%3d)を入力して下さい。  ",ncity);
      scanf("%d", &dept);
      if (dept > ncity || dept <= 0){
        printf("都市番号が無効です。\n");
        return(-1);
      }
      dept--; // 入力値は 1-base, 配列の index は 0-base
    
      /* 配列 visit の初期化 */
      for (i=0;i<ncity;i++)
        visit[i] = 0;
      visit[dept] = 1;  // 1: 訪問済
    
      /* ---- 貪欲算法 start ---- */
      double min, cost;
      int min_idx;
      printf("順回路は\n");
      printf("%d ", dept+1);
      i = dept;
      while(i >= 0) {
        min = DBL_MAX;
        min_idx = -1;
        for(j=0;j<ncity;j++){
          if (i != j && !visit[j]) {
            if(dist[i][j] < min){
              min = dist[i][j];
              min_idx = j;
            }
          }
        }
    
        if (min_idx < 0) { // 全ての地点を訪問済
          printf("%d\n", dept+1);
          cost += dist[i][dept];
        } else {
          printf("%d ", min_idx+1);
          cost += min;
          visit[min_idx] = 1;
        }
        i = min_idx;
      }
    
[/code]


CC BY-SA 4.0
2021-01-13T12:59:45.700
73272
2021-01-13T13:32:45.820
2021-01-13T13:32:45.820
73248
answer