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

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

新規登録して質問してみよう
ただいま回答率
85.42%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

0回答

528閲覧

ダイクストラの評価について

towa-wato

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2023/05/03 15:27

実現したいこと

最小ホップ経路を用いた固定経路で、呼損率による評価を行う。

前提

通信の発生
ランダムに送受信ノードを決定する.

通信の確立
与えられた送受信ノード間の経路を決定し,その経路上のリンクの空き容量を 1Mbps だけ減少させる.ただし,経路上に空き容量のないリンクが存在する場合,この通信は確立しなかったものとして,何も行わない.

通信の終了
n 回前に発生した通信の経路上の空き容量を 1Mbps だけ増加させる.ただし,その通信が確立 していなかった場合には何も行わない.

呼損率の評価
10,000 回の通信を発生させ,そのうちで確立できなかった通信の割合(呼損率)を求める.

試行の繰り返し
パラメタ n を変化させながら,上記の試行を繰り返し行う.パラメタ n を変化させたときのグラフ・表を作成する。

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

,
,
,
「上記も続いている」
,
,
src=7, dest=4
src=5, dest=7
src=3, dest=5
src=0, dest=6
src=3, dest=7
src=0, dest=0
送受信ノードが一致している
src=2, dest=3
src=0, dest=0
送受信ノードが一致している
src=1, dest=9
src=4, dest=0
src=4, dest=3
src=9, dest=7
src=0, dest=7
src=4, dest=3
src=7, dest=5
何回前の通信の経路上の空き容量を増加させますか?: 3
3回前の情報はありません。

average = 0.141000

該当のソースコード

C言語

1#include <stdio.h> 2#include <stdlib.h> 3#include <time.h> 4 5#define NODE_NUM 10 /* 総ノード数 */ 6#define MAX 9999 /* 無限大に相当する数 */ 7 8#define FLAG 1 /* Dijkstraのテストの場合は0に、シミュレーション評価を行う場合は1にする */ 9 10int main() 11{ 12/* Dijkstraのアルゴリズム部分で必要な変数 */ 13 int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */ 14 int path[NODE_NUM]; /* 前ノード表 */ 15 int dist[NODE_NUM]; /* 距離を格納 */ 16 int chk[NODE_NUM]; /* 最短距離確定のフラグ */ 17 int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */ 18 int src, dest; /* 始点・終点ノード */ 19 int a, b, c, d, i, j; 20 int fin; /* 未確定ノードが残っているかどうかのフラグ */ 21 FILE *fp; /* 距離の入ったファイルを示すポインタ */ 22 23 /* シミュレーション評価の部分で必要な変数 */ 24 int link[NODE_NUM][NODE_NUM]; /* リンク容量 */ 25 int bandwidth[NODE_NUM][NODE_NUM]; /* リンクの空き容量 */ 26 int miss; /* 呼損を表すフラグ */ 27 int success; /* 確立できた通信回数 */ 28 int sum_success; /* 確立できた通信回数の合計 */ 29 int sim_time; /* 評価の回数をカウント */ 30 31 32/* 33距離行列の作成 34*/ 35 for(i=0; i<NODE_NUM; i++){ 36 for(j=0; j<NODE_NUM; j++){ 37 graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */ 38 link[i][j] = -1; /* 接続されていないノード間のリンク容量を-1にする */ 39 if(i==j){graph[i][j] = 0; link[i][j] = -1;}/* そのノード自身への距離は0とし、リンク容量は-1とする */ 40 } 41 } 42 fp=fopen("./distance.txt", "r"); 43 while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */ 44 { 45 graph[a][b]=c; /* 接続されているノード間の距離を設定 */ 46 graph[b][a]=c; /* 逆方向も等距離と仮定 */ 47 link[a][b]=d; /* 接続されているノード間のリンクを設定 */ 48 link[b][a]=d; /* 逆方向も同じ容量と仮定 */ 49 } 50 fclose(fp); 51 52 53 54/* 55始点・終点ノードを標準入力から得る (評価の場合は、実行しない) 56*/ 57 if (FLAG == 0){ 58 printf("Source Node?(0-%d)", NODE_NUM-1); 59 fscanf(stdin, "%d", &src); 60 printf("Destination Node?(0-%d)", NODE_NUM-1); 61 fscanf(stdin, "%d", &dest); 62 } 63 64 if (FLAG == 1) srand((unsigned)time(NULL)); /* 乱数の初期化, これ以降、rand()で乱数を得ることができる */ 65 66 67 68/****************************/ 69/* シミュレーション評価開始 */ 70/****************************/ 71 72 success = 0; sum_success = 0; /* 評価指標を初期化 */ 73 for (sim_time=0; sim_time<1000; sim_time++){ 74 75 miss = 0; /* 空きリンクが存在しない場合のフラグをOFFにする */ 76 success = 0; /* 確立できた通信回数を初期化する */ 77 78 for (i=0; i<NODE_NUM; i++){ /* 全リンクの空き容量を初期状態に戻す */ 79 for (j=0; j<NODE_NUM; j++){ 80 link[i][j]= link[i][j]; 81 } 82 } 83 84 85 86 while(miss == 0){ /* 呼損が発生するまで繰り返す*/ 87 /* 評価の場合、送受信ノードをランダムに決定 */ 88 if (FLAG == 1){ 89 /* ランダムに送受信ノードを決定 */ 90 src = rand()%10; 91 dest = rand()%10; 92 printf("src=%d, dest=%d\n", src, dest); /* 送受信ノードを表示 */ 93 if (src==dest) printf("送受信ノードが一致している\n"); 94 } 95 96 97 98 /****************************************/ 99 /* ここからdijkstraのアルゴリズムを記述 */ 100 /* 最初はこの部分を記述し、作成すること */ 101 /****************************************/ 102 103 /* 104 初期化 105 */ 106 for(i=0; i<NODE_NUM; i++){ /* 何も確定していない状態にする */ 107 dist[i] = MAX; 108 chk[i] = 0; 109 path[i] = NODE_NUM; 110 } 111 path[src] = src; /* 始点ノードへの経路上の前ノードはそれ自身とする */ 112 dist[src] = 0; /* 始点ノード自身への距離は0である */ 113 chk[src] = 1; /* 始点ノードへの最短距離は確定 */ 114 tmp_node = src; /* 始点ノードから探索を始める */ 115 fin = 0; 116 117 118 /* 119 経路探索 120 */ 121 122 /* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */ 123 for(i=0; i<NODE_NUM; i++){ 124 if(graph[src][i]==1){ 125 dist[i] = graph[src][i]; 126 path[i] = src; 127 } 128 } 129 130 131 132 /* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */ 133 134 for(i=0; i<NODE_NUM; i++){ 135 if(graph[src][i]==1 && dist[i]<dist[tmp_node]){ 136 dist[tmp_node]= dist[i]; 137 tmp_node = i; 138 } 139 } 140 chk[tmp_node] = 1; 141 142 143 while(fin==0){ /* finフラグが立つまで繰り返す */ 144 /* 4.*/ 145 /* 確定したノードに接続している全てのノードについて */ 146 /* srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 */ 147 /* これまでの距離より短ければ */ 148 /* distとpathを更新する */ 149 150 for(i=0;i<NODE_NUM;i++){ 151 if(graph[tmp_node][i] == 1 && dist[tmp_node]+graph[tmp_node][i] < dist[i]){ 152 dist[i] = dist[tmp_node]+graph[tmp_node][i]; 153 path[i] = tmp_node; 154 } 155 } 156 157 158 159 160 /* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/ 161 162 dist[tmp_node] =MAX; 163 for(i=0;i<NODE_NUM;i++){ 164 if(chk[i]==0 && dist[i]<dist[tmp_node]){ 165 dist[tmp_node] = dist[i]; 166 tmp_node = i; 167 } 168 } 169 chk[tmp_node] = 1; 170 171 172 173 if(chk[dest] == 1) fin = 1; /* 終点ノードへの最短距離が確定したら終了 */ 174 } 175 176 177 178 179 /* 180 結果出力(Dijkstra作成時のみ実行する) 181 */ 182 if(FLAG == 0){ 183 if(dist[dest]>=MAX){ 184 printf("No path from node%d to node%d.\n",src,dest); 185 }else{ 186 printf("Shortest path from node%d to node%d is as follows.\n",src,dest); 187 printf("%d <- ",dest); 188 i=dest; 189 for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */ 190 printf("%d <- ",i); 191 } 192 printf("%d\n",src); 193 printf("Shortest distance is %d.\n", dist[dest]); 194 } 195 return 0; /* Dijkstraの作成時は結果を出力したらプログラムを終了する */ 196 } 197 198 199 /************************************/ 200 /* ここまでがdijkstraのアルゴリズム */ 201 /************************************/ 202 203 /**********************************************************************/ 204 /* この下にdijkstraで決定した経路を評価するためのプログラムを記述する */ 205 /**********************************************************************/ 206 207/* 2-(a) その経路上の全てのリンクに空き容量がある場合、それらを1Mbpsだけ 208 減少させ、「確立できた通信回数」を1増やす 209*/ 210 for(i=dest; i!=src; i=path[i]){ 211 if(bandwidth[i][path[i]] != 0){ 212 bandwidth[i][path[i]] -= 1; 213 success += 1; 214 } 215 } 216 217 218 219/* 220 2-(b) その経路上に空き容量のないリンクが存在する場合、呼損とし、 221 その時点までの「確立できた通信回数」をsum_successに足して、while文をbreakする 222*/ 223 int lost =0; 224 for(i=dest; i!=src; i=path[i]){ 225 if(bandwidth[i][path[i]] == 0){ 226 lost = 1; 227 break; 228 } 229 } 230 if(lost){ 231 sum_success += success; 232 break; 233 } 234 235 236 }/* while(1) */ 237}/* 1~3の手続きを1000回行うためのfor文 */ 238 239 240int history[NODE_NUM] = {0}; 241int n; 242 243printf("何回前の通信の経路上の空き容量を増加させますか?: "); 244scanf("%d", &n); 245 246if (n <= 0) { 247 printf("通信が確立していません。\n"); 248 return 0; 249} 250 251if (n > NODE_NUM) { 252 printf("%d回前の情報は記録されていません。\n", n); 253 return 0; 254} 255 256// n回前の情報がある場合、容量を増加させる 257if (history[n-1] > 0) { 258 history[n-1] += 1; 259 for (i = dest; i != src; i = path[i]) { 260 if (bandwidth[i][path[i]] > 0) { 261 bandwidth[i][path[i]] += 1; 262 } 263 } 264 printf("%d回前の通信の経路上の空き容量を1Mbpsだけ増加させました。現在の容量は%dMbpsです。\n", n, bandwidth[i][path[i]]); 265} else { 266 printf("%d回前の情報はありません。\n", n); 267} 268 269 270/* 271シミュレーション評価の結果出力 272*/ 273 printf("\naverage = %f\n", sum_success / 1000.0); 274/* 初めて呼損が起こるまでに確立できた通信回数の平均を表示 */ 275 return 0; 276}

試したこと

何回前の通信の経路上の空き容量を増加させますか?の質問にどんな値を入れても、n回前の情報はありませんと表示されるのですが、評価ができているのか。
また、試行を繰り返してパラメタ n を変化させたときのグラフ・表を作成する方法がわからない。修正点があれば教えてください。

補足情報(FW/ツールのバージョンなど)

distance.txtの内容は
0 1 1 3
0 3 1 3
1 2 1 3
1 3 1 4
2 4 1 4
2 5 1 3
3 4 1 5
3 7 1 3
4 5 1 5
4 7 1 4
5 6 1 3
5 8 1 4
6 8 1 3
7 8 1 4
7 9 1 3
8 9 1 3

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

towa-wato

2023/05/05 08:44

同一人物です。前のアカウントがログインできなくなってしまいました。
actorbug

2023/05/08 20:57 編集

正直、問題を解決するための手順を検討する前にコードを書いているように見えてしまいます。 int history[NODE_NUM] = {0}; 上記コードを実行してから「history」に何も代入せずに if (history[n-1] > 0) { のような判定をしたら、「n回前の情報はありません。」と表示されるのは当たり前ではないでしょうか。 それ以外にも、以下のようにlinkにlinkを代入するという明らかに意味のないコードを書いていることも、最初の疑いを深める原因となっています。 for (i=0; i<NODE_NUM; i++){ /* 全リンクの空き容量を初期状態に戻す */ for (j=0; j<NODE_NUM; j++){ link[i][j]= link[i][j]; } }
jimbe

2023/05/06 17:19

>評価ができているのか。 それを先ずはご自身で確認してください。 評価している箇所でその値を表示してみるとか出来ると思います。 それと、機能毎に関数化し、インデントを適切にしてください。 分かり易い読み易いコードは、バグが入り難く確認し易く修正し易いです、
jbpb0

2023/05/06 23:33

> 同一人物です。 https://teratail.com/legal の「第7条(禁止事項)」に書かれてるように、「複数のユーザーIDを1人で保有する行為」は禁止されてます > 前のアカウントがログインできなくなってしまいました。 https://teratail.com/users/towawato https://teratail.com/users/towa-wato を見たら、アカウントを作成したのは同じ「2022/07/15」なので、 「ログインできなくなったから別のアカウントを作った」 のではないですよね
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.42%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問