質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.13%

C言語での巡回路の生成

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 195

ro_tose

score 8

前提・実現したいこと

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

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

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

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

該当のソースコード

#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]);
}

試したこと

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • ttyp03

    2019/11/29 20:12

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

    キャンセル

  • ro_tose

    2019/11/29 22:53

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

    キャンセル

回答 2

checkベストアンサー

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/29 21:10

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

    キャンセル

  • 2019/11/29 22:56

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

    キャンセル

  • 2019/11/29 23:23

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/29 20:23

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

    キャンセル

  • 2019/11/29 22:55

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.13%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る