課題4/5/6
課題4/5
2011年 ICPC 2010年アジア予選 福岡大会の問題D(pdf)をベースに
- 簡単化した問題を課題4として、
- 本来の問題を課題5(オプション課題)として解いてみましょう.
本来の問題の説明
タクシーが長い距離を移動する。
- 都市の距離関係を示すグラフが与えられている
- タクシーは開始点からゴールに移動
- ガスステーションは少数
- 満タンにしても、指定した距離しか移動できない(cap x 10 しか移動できない, cap: タンクの容量)
- 質問:移動距離を最小にするには?(到達不能の場合は -1 を返す)
入力例:
6 3 34 //道路は6つ,ガソリンスタンドにある都市3つ,ガソリンタンクの容量は34L
Tokyo Kyoto // Tokyoから,Kyotoへ行きたい
Tokyo Niigata 335 // 道路の情報
Tokyo Shizuoka 174
Shizuoka Nagoya 176
Nagoya Kyoto 195
Toyama Niigata 215
Toyama Kyoto 296
Nagoya // ガソリンスタンドがある都市
Niigata
Toyama
下記の状況とのことです:
ガソリンタンクは34Lなので,ガソリンスタンドに給油せずに,340Kmを走れる.
上記の状況だと, Tokyo -> Shizuoka -> Nagoya -> Kyoto
のルートは一番短いなのに,TokyoからNagoyaに着くのが不可能です.
最短ルートは Tokyo -> Niigata -> Toyama -> Kyoto
となり,回答は 846
です.
同じ状況でガソリンタンクは30Lだった場合は,Kyotoに着くのが出来ません(NagoyaやNiigataにも届けない).回答は -1
です.
この問題は難しいです.例えば,下記の状況を観ていて下さい.
- ガソリンタンクは50Lの場合は,
Paris -> Reims -> Metz -> Strasbourg
直接に走って,距離は500Kmとなる. - ガソリンタンクは49Lの場合は,最短ルートは
Paris -> Reims -> Metz -> Nancy -> Metz -> Strasbourg
になる.
ソースコードの説明
都市が文字列として与えられていますが、C でこの種の処理は大変なので、先に都市番号を割り振ってあります.
都市の数はcityNum
に格納し,都市には,起点を 0
, 終点が 1
, それ以外の都市には、2
以上 cityNum-1
以下の整数値を出現順に割り当ててあります:
- struct roadinfo (roadinfo_t): 各都市につながる道の情報を保持
num
: 道の数struct { int dest; int dist; } roads[]
: 道の配列。dest
は行き先、dist
は距離
- 大域配列
roadinfo_t roadinfo[MAX_N_CITIES]
: 上記の配列 - 大域配列
cityNames[]
: 各都市の名前を格納(デバッグ用途以外では使わない) - 大域配列
bool withGas[MAX_N_CITIES]
:withGas[index]
の値は、都市番号(index)の都市に、ガスステーションあるか(値:1
)、ないか(値:0
)を示す。(オプション課題でのみ利用)
/**********************
* map の情報
*/
#define MAX_N_ROADS 3000
#define MAX_N_CITIES 2 * MAX_N_ROADS
#define MAX_LENGTH_CITYNAME 15
#define MAX_N_GAS 300
char cityNames[MAX_N_CITIES][MAX_LENGTH_CITYNAME + 1];
typedef struct roadInfo {
int num;
struct {
int dest;
int dist;
} roads[MAX_N_ROADS];
} roadinfo_t, *roadinfo_tp;
roadinfo_t roadinfo[MAX_N_CITIES];
bool withGas[MAX_N_CITIES];
int cityNum;
main
関数で正解チェックをおこなっています.
皆さんの作成する関数はint solve(int n, int m, int cap)
- 関数
int solve(int n, int m, int cap)
n
: 道の数m
: ガスステーションの数(オプション課題でのみ利用)cap
: ガスタンクの容量(移動可能距離はcap*10
, 都市間距離がcap*10
以下であれば到達可能)(オプション課題でのみ利用)- 返り値:起点から終点まで到達可能なら最小経路長を返す.到達不能な場合は、
-1
を返す.
大域変数として下記が準備してあります。当然,各自でデータ構造を追加・拡張してもらっても構いません.
課題4
課題4では,本来の問題をもう少し簡単にする:ガソリンタンクは無限であることを前提する.
つまり,通常の最短ルートアルゴリズムで計算する.
課題4提出
正解プログラム例の公開までに以下を提出してください(途中でも構いません)
- プログラムファイル
123456t_longDistTaxi.c
- レポート
123456_longDistTaxi_kadai4.pdf
- 学番+氏名+実行結果(debug 出力が混ざっていても構いません)
- 課題4は、追加したデータ構造などの簡単な説明を入れてください
- アピールポイントがある人は、その旨解説入れてください
- ほとんどのデータで正解しているが、一部データでバグが取れない場合は、その旨記述して、考察を記載してください
正解例を参考にレポートを再提出する場合
- まず、未完成でも、その自作プログラムを提出すること
- 自分が作成できなかった部分がどの部分か、正解例ではどのように実現されていたか、解説すること
- 正解プログラム例の実行を、デバッガなどでトレースし、正しく動作していることを説明すること.今回の例では,
sample.in
の最初の例について解説すれば OK です。
課題4の締め切り:2023年1月18日12時00分
回答例を公開:2023年1月18日12時00分
課題4の再提出締め切り:2023年1月25日12時00分
課題5(加点課題)
本来の問題を解けましょう.
taxi/longDistTaxi.c#L208に,int optionF = 1
に変更して下さい.
そうする,ガソリンタンクを入りの回答の比較を行う.
/*******
* こちらで用意したmain 関数。
* 問題準備してから、solve() をよび、正解比較もおこなう。
*/
int main(int argc, char* argv[]) {
int optionF = 0; // optionF = 1; に変更して下さい
...
余力のある人は是非取り組んで下さい.難易度はかなり上がるので,まず解け方の基本方針を考えて下さい. 1月の授業でいくつかのヒントを出す予定ですが,早めに提出しても構いません。
課題5提出
- プログラムファイル
123456_longDistTaxi.c
- レポート
123456_longDistTaxi_kadai5.pdf
- 実行結果
- 基本的な考え方の解説
- アピールすべきことがあればどうぞ
- 一部プログラムでバグがのこってしまう場合は,その旨連絡を
課題5の締め切り:2023年1月26日23時59分
課題6 ダイクストラ法とA*の比較(加点課題)
もう一度課題2を観てみましょう.
当時,幅優先案策で解けたのですが,A*アルゴリズムを使うともう少し効率的な実装が出来そうじゃないですか?
課題内容
幅優先探索の実装をベースに,A*を実装して,正常に実行していることを確認してから,ゴールを見つかるまでの反復回数あるいは実行時間を比較してください.
課題6の提出
- プログラムファイル
kadai2_a-star.c
- レポート(PDF)
- この問題だと,なぜ幅優先探索とダイクストラ法の実行結果が同じかを説明
- 任意の座標からゴールまでのペナルティ
- キューの優先度
- 計算時間/反復回数の比較と考察
課題6の締め切り:2023年1月26日23時59分