授業で示した最長経路問題を解くプログラムについて、与えられたグラフ中に最長経路でのコストと、それを実現する経路（訪れるべき頂点の順）を示すようにプログラムを改良せよ。
訪れるべき頂点の順は、それが分かる形であれば出力形式はどのような形でもよい。
提出するプログラムについては、与えるグラフはSAMPLE_G120だけでよい。
・出力結果が読みやすくなるように、テキスト出力部分を工夫してあるほうがポイントが高いです。
| グラフ名 | SAMPLE_G120 | SAMPLE_G130 | |||
| 隣接行列 |
#define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,0,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,2,0},
{0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0}
};
|
#define N 8
int edge[N][N] = {
{0,4,0,0,2,0,0,0},
{0,0,0,0,0,0,1,0},
{0,0,0,3,0,0,3,0},
{0,0,0,0,0,0,0,5},
{0,0,0,0,0,2,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,4,0,1},
{0,0,0,0,0,0,0,0}
};
|
- 提出物〔2A-1〕：Ｃソースファイル（コメント必須）
SAMPLE_G120での動作確認ができる状態で提出すること。(SAMPLE_G130を同時に表示できる必要はない)
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
プログラムで工夫した行について、必ず何かしらの説明をコメントの形でプログラム中に書き込むこと。
コメントがないようなプログラムは提出とはみなさないので注意すること。
【状況】
【指示】
誰かに教えてもらった場合：
その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
誰かに教えてあげた場合：
その学生（氏名・学籍番号）をプログラム先頭に記すこと。
お互いに相談した場合：
お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。
- 提出物〔2A-2〕：SAMPLE_G120に対して、出力結果を保存したテキストファイル
授業で示した最長経路問題を解くアルゴリズムとプログラムは、以下のようなグラフが与えられた時、解を与えることが可能か。はい、いいえを理由とともに答えよ。
(1) グラフ中に閉路が１つ以上存在する場合
(2) グラフ中のエッジで、コスト０のものが１つ以上存在する場合
(3) グラフ中のエッジで、コスト負のものが１つ以上存在する場合
(4) グラフ中のエッジで、閉路がありかつその閉路中にコスト負のエッジが含まれている場合
- 提出物〔2B-1,2B-2,2B-3,2B-4〕：テキスト。(1)-(4)に対応
moodle上で編集して提出してください。バックアップを各個人で別に持っておくことを薦めます。
課題２Ａで用いたプログラムについて、グラフ中にコスト０のエッジが含まれていても最長経路を示せるよう改良せよ。
また同時に、同一コストをもつ最長経路が２つ以上見つかる場合は、頂点数の多い経路を答えるようにせよ。
・一般性を失わない限り、隣接行列の表現形式に変更を加えても良い。
・出力結果が読みやすくなるように、テキスト出力部分を工夫してあるほうがポイントが高いであろう。
評価用サンプルとして、SAMPLE_G132とSAMPLE_G133を示す。
- 提出物〔2X-1〕：Ｃソースファイル（コメント必須）
SAMPLE_G131での動作確認ができる状態で提出すること。
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
教えた・教わった場合には、課題２Ａと同様に明記すること。
- 提出物〔2X-2〕：SAMPLE_G131の処理結果を保存したテキストファイル