北京地下鉄駅線路計画
774 ワード
プロジェクトの内容
北京地下鉄路線の計画プログラムを設計する
開発言語
java
需要分析
1.ユーザーは線路計画状況を見ることができ、自分で線路を選択することができる
2.ユーザーは始点と終点を入力してサイトの最低と乗り換えの最低のルートを調べることができる
実装方法
1.サイト情報を2 D配列に格納する
2.Dijkstraアルゴリズムを用いて最短経路を得る
3.得られた最短パスを1枚のテーブルに格納する
4.テーブルに格納されている最短パス情報をユーザーにフィードバックする
5.再帰アルゴリズムで最低乗り換え路線を得る
6.最低乗り換え路線が通過する駅の総数を計算し、小さい総数で大きい総数をカバーし、ユーザーにフィードバックする
試験例
入力
しゅつりょく
実験のまとめ
サイト数が多くない場合は,最適解を事前に保存しておき,ユーザはデータを取得する際に繰り返し計算ではなく直接データを読み取ることができる.
北京地下鉄路線の計画プログラムを設計する
開発言語
java
需要分析
1.ユーザーは線路計画状況を見ることができ、自分で線路を選択することができる
2.ユーザーは始点と終点を入力してサイトの最低と乗り換えの最低のルートを調べることができる
実装方法
1.サイト情報を2 D配列に格納する
2.Dijkstraアルゴリズムを用いて最短経路を得る
3.得られた最短パスを1枚のテーブルに格納する
4.テーブルに格納されている最短パス情報をユーザーにフィードバックする
5.再帰アルゴリズムで最低乗り換え路線を得る
6.最低乗り換え路線が通過する駅の総数を計算し、小さい総数で大きい総数をカバーし、ユーザーにフィードバックする
試験例
入力
: 1
: 2
しゅつりょく
:
1-> 1->......-> 2
:
1-> 1->......-> 2
実験のまとめ
サイト数が多くない場合は,最適解を事前に保存しておき,ユーザはデータを取得する際に繰り返し計算ではなく直接データを読み取ることができる.