C言語での巡回路の生成

Question

前提・実現したいこと

51個の都市すべてを回る巡回路を生成して、移動した場所に足跡を残したい。

アルゴリズムとしては
１:全ての都市を未訪問にする。
２:ランダムな一都市に巡回する対象を配置する。
３:未訪問な都市の中から確率pro[i]で都市を選択して移動する。
４：すべての都市を巡回するまで３を繰り返す。
５：最初に配置された都市に帰ってくる。
というのを考えています。

発生している問題・エラーメッセージ

すべての都市を巡回せず、存在しないはずの都市を訪れている。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>




int main(void)
{
  int i;
  int step;
  int rn;
  double pro[51];
  double sm_pro;
  double rnd;
  double sm_sol;
  int visited[51];
  int tour[52];
  int n;
   
  step=0;

  n=51;
  sm_pro=0;

  for(i=0;i<n;i++){
    visited[i]=0;
  }

  srand((unsigned)time(NULL));

  rn=rand()%n;


  visited[rn]=1;

  tour[step]=rn;
 
  while(step<n-1){
    step++;
    for(i=0;i<n;i++){

      pro[i]=0;
      if(visited[i]){
      }
      else{
        pro[i]=1;
        sm_pro +=pro[i];
      }
    }
    i=0;
    rnd=(double)rand()/RAND_MAX;
    rnd *=sm_pro;
    sm_sol=0;
    while(sm_sol<=rnd){
      i++;
      sm_sol+=pro[i]; 
    }
  tour[step]=i;
  visited[i]=1;
  }


  tour[51]=tour[0];

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

試したこと

式を見直してみたりしたり少しいじったりしたのですがどうにも想定した値を出してくれません。

Comments

[ttyp03]

どういうアルゴリズムなのかを書かないと答えようがない。
あとコードが見づらい。インデントくらいちゃんとしましょう。

[ro_tose]

失礼しました。回答について修正させていただきました。

Answer 1

ざっと見ても意図不明なコードが。
＃２回めの乱数は使われてないし

も一度どういう動作をさせたいのか、コードの動作を追いかけながらチェックしてみよう

Comments

[ro_tose]

2回目の乱数は次にどこの都市に行くかを決めるために使っているつもりです。
動作の追いかけはprintfで変数を確認していけばいく形でいいんでしょうか？

[y_waiwai]

それでいいとおもいますよ。
どういうふうに動かせたいのか、実際はどう動くのか、をチェックしましょう

[y_waiwai]

問題の有りそうなところを書いておきます
> srand((unsigned)time(NULL));
こいつの実行はプログラムの最初に一回だけにしておくべし、複数実行する意味はないし、下手をすると（ヘタしないでも）rand関数が乱数を返さないようになる

[ro_tose]

ありがとうございます！一つ一つ確認していってみます。

[ro_tose]

解決できました。
sm_proがwhile分の中で初期化せずに外で初期化していたので堆積していったことと、sm_solにpro[i]をいれずに０を代入していたせいで求めていたデータが出なかったようです。
アドバイスしていただいてありがとうございました。

Answer 2

アルゴリズムがわからないので何ともいえませんが、for文を抜けた後にiを0で初期化してるのはいいのでしょうか？

Comments

[ttyp03]

いや、いいのか？
よくわからん。

[ro_tose]

一度iを初期化して、そのあとwhile内でiを加算していってpro[i]の配列を呼び出しています。