下記で示すグラフ(MAP_A, MAP_B)について、各頂点には価値が配列変数 nodeval[] に格納されている。
頂点０からスタートして深さ優先探索を行い、新しく頂点に到達する度にその頂点の価値を獲得できるとする。
授業でのプログラムと同じく、ある頂点において複数の選択肢がある場合は、頂点番号の小さい方を優先すること。
その獲得の進行の様子と、頂点０からの探索による最終的な合計価値とを表示するプログラムを作成せよ。
提出するプログラムについては、MAP_Aだけでよい。
・合計価値を求める際に、大域変数を使わずに局所変数を使ったほうがポイントが高いです。
・出力結果が読みやすくなるように、（授業でも示したように）テキスト出力部分を工夫してあるほうがポイントが高いです。
| MAP_A | MAP_B |
#define N 10
int edge[N][N] = {
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 0, 0}
};
int nodeval[N] = { 6, 24, 3, 22, 5, 5, 22, 28, 21, 13};
|
int edge[10][10] = {
{0, 0, 1, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
{1, 0, 1, 0, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
};
int nodeval[N] = { 5, 11, 11, 12, 26, 27, 24, 1, 12, 23};
|
参考までに、MAP_Bによる頂点０からの実行の様子を示す。左が頂点番号、右がその時点での合計価値。
なお、これは最小限の表示例であるため、実際には各自読みやすくなるように工夫すること。
0 5 2 16 6 40 5 67 4 93 7 94 8 106 9 129 Total 129
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合： | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
深さ優先探索において、実行時に動的に確保される空間計算量が最小となるグラフの形とその始点を示せ。
理由も述べること。
MAP_A, MAP_B中に存在する全ての経路(MAP_Aでは３つ、MAP_Bでは２つ)について、その合計価値を出せるようにプログラムを改良すること。
始点は、各経路に含まれる頂点のうち、もっとも小さい番号とすること。
さらに、各MAPにおいて、もっとも合計価値が高い経路を選ぶためにどの頂点を選ぶべきか、プログラムによって最後に示すこと。