甘味処。

甘いものの話はたぶんしません。

ゼミの冬期課題の話

はじめに

今日も寒いですね。 1日で追い込んだゼミ課題の話をします。 秋学期は指定された教科書を使ってPythonに触れていました。

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers)

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers)

ゼミ課題は「Pythonを使ってオリジナルなプログラムを作る」でした。 授業の共同課題で自分の担当だった経路探索アルゴリズムの説明をしました。

動機

授業課題で作成した作品は、電車の乗り換え経路と駅周辺の飲食店を提示するWebサービスでした。経路探索アルゴリズムの選定基準では、運賃及び距離の条件を無視しました。処理の高速化とユーザーに「時間を気にさせない」ことを目的にしていたためです。結果的に「幅優先探索」を採用しました。

班員にアルゴリズムを説明したものの理解してもらえず、ゼミ課題でも発表することにしました。 ついでに深さ優先探索も実装して比較しました。

アルゴリズムの説明

まずは道を作ります。道がないことには経路探索は始まりません。適当に作ります。

f:id:kanzarashi:20180119131653p:plain:w300

次に探索を行います。先ほど作ったネットワークでAからZに移動する場合について考えます。 幅優先探索深さ優先探索も開始ノードから終了ノードが見つかるまで隣接するノードをすべて取得し、照合を行うアルゴリズムです。

幅優先探索では開始ノードに隣接するノードを全て調べ切ってから隣接するノードに対して照合を行います。

f:id:kanzarashi:20180119133725p:plain:w300

深さ優先探索では開始ノードに隣接するノードを一つ見つけるとさらに隣接するノードに対して照合を行います。

f:id:kanzarashi:20180119133727p:plain:w300

入力したデータをどの順番で取り出すかが異なっているため、幅優先探索ではキュー構造、深さ優先探索ではスタック構造が用いられます。

最後に経路の作成を行います。 終了ノードから直前のノードを再帰的に調べて開始ノードに行きつくまでのルートを作成します。

コード

まとめ

スタック、キュー構造や再帰等の考え方が入ってくるので弊学科のB2の勉強に向いていると感じました。 結局班員には理解してもらえませんでした。