課題４/５/６

課題４/５
課題６　ダイクストラ法とA＊の比較（加点課題）

資料④へ

課題４/５

2011年 ICPC 2010年アジア予選福岡大会の問題D(pdf)をベースに

簡単化した問題を課題４として、
本来の問題を課題５（オプション課題）として解いてみましょう.

本来の問題の説明

タクシーが長い距離を移動する。

都市の距離関係を示すグラフが与えられている
- タクシーは開始点からゴールに移動
- ガスステーションは少数
- 満タンにしても、指定した距離しか移動できない(cap x 10 しか移動できない, cap: タンクの容量)
質問：移動距離を最小にするには？(到達不能の場合は -1 を返す)

入力例：

6 3 34                  //道路は６つ，ガソリンスタンドにある都市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

下記の状況とのことです：

Sample figure

ガソリンタンクは34Lなので，ガソリンスタンドに給油せずに，340Kmを走れる．上記の状況だと， Tokyo -> Shizuoka -> Nagoya -> Kyoto のルートは一番短いなのに，TokyoからNagoyaに着くのが不可能です．最短ルートは Tokyo -> Niigata -> Toyama -> Kyoto となり，回答は 846です．

同じ状況でガソリンタンクは30Lだった場合は，Kyotoに着くのが出来ません（NagoyaやNiigataにも届けない)．回答は -1 です．

この問題は難しいです．例えば，下記の状況を観ていて下さい．

Difficult map

ガソリンタンクは50Lの場合は，Paris -> Reims -> Metz -> Strasbourg 直接に走って，距離は500Kmとなる．
ガソリンタンクは49Lの場合は，最短ルートは Paris -> Reims -> Metz -> Nancy -> Metz -> Strasbourgになる．

ソースコードの説明

taxi/longDistTaxi.c

都市が文字列として与えられていますが、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では，本来の問題をもう少し簡単にする：ガソリンタンクは無限であることを前提する．
つまり，通常の最短ルートアルゴリズムで計算する．

課題４提出

正解プログラム例の公開までに以下を提出してください（途中でも構いません）

プログラムファイル 123456t_longDistTaxi.c
レポート 123456_longDistTaxi_kadai4.pdf
- 学番＋氏名＋実行結果（debug 出力が混ざっていても構いません）
- 課題４は、追加したデータ構造などの簡単な説明を入れてください
- アピールポイントがある人は、その旨解説入れてください
- ほとんどのデータで正解しているが、一部データでバグが取れない場合は、その旨記述して、考察を記載してください

正解例を参考にレポートを再提出する場合

まず、未完成でも、その自作プログラムを提出すること
自分が作成できなかった部分がどの部分か、正解例ではどのように実現されていたか、解説すること
正解プログラム例の実行を、デバッガなどでトレースし、正しく動作していることを説明すること．今回の例では，sample.in の最初の例について解説すれば OK です。

課題４の締め切り：2023年1月18日12時00分
回答例を公開：2023年1月18日12時00分
課題４の再提出締め切り：2023年1月25日12時00分

課題５（加点課題）

本来の問題を解けましょう．

taxi/longDistTaxi.c#L208に，int optionF = 1に変更して下さい．そうする，ガソリンタンクを入りの回答の比較を行う．

/*******
 * こちらで用意したmain 関数。
 * 問題準備してから、solve() をよび、正解比較もおこなう。
 */
int main(int argc, char* argv[]) {
  int optionF = 0; // optionF = 1; に変更して下さい
  ...

余力のある人は是非取り組んで下さい．難易度はかなり上がるので，まず解け方の基本方針を考えて下さい．１月の授業でいくつかのヒントを出す予定ですが，早めに提出しても構いません。

課題５提出

プログラムファイル 123456_longDistTaxi.c
レポート 123456_longDistTaxi_kadai5.pdf
- 実行結果
- 基本的な考え方の解説
- アピールすべきことがあればどうぞ
- 一部プログラムでバグがのこってしまう場合は，その旨連絡を

課題５の締め切り：2023年1月26日23時59分

課題６　ダイクストラ法とA＊の比較（加点課題）

もう一度課題２を観てみましょう．

kadai2-revisited

当時，幅優先案策で解けたのですが，A＊アルゴリズムを使うともう少し効率的な実装が出来そうじゃないですか？

課題内容

幅優先探索の実装をベースに，A＊を実装して，正常に実行していることを確認してから，ゴールを見つかるまでの反復回数あるいは実行時間を比較してください．

課題６の提出

プログラムファイル kadai2_a-star.c
レポート(PDF)
- この問題だと，なぜ幅優先探索とダイクストラ法の実行結果が同じかを説明
- 任意の座標からゴールまでのペナルティ
- キューの優先度
- 計算時間/反復回数の比較と考察

課題６の締め切り：2023年1月26日23時59分