どマイナーな場所の最短経路を探索する(MATLAB＋Excel)

はじめに

時間やコストを最小限にして行きたい場所がある！
けれどもgoogleマップや、Yahoo!乗換案内では取り扱いがない・・・
そんな困りごとも簡単に解決できます、そうMATLABならね。

と茶番はさておき、MATLABの便利な関数の一つに最短経路探索があります。
面白そう ＆ MATLAB布教に役立ちそうなのでMATLAB芸を考えました。

〇想定する読者
　MATLAB初心者、MATLAB芸人を志す人

〇この記事で覚えて頂きたいこと
・shortestpath関数マジ便利
・Figureの機能「データヒント」の存在
・table型の便利さおよび扱い方
・ExcelファイルをMATLAB table型に読み込むためのコツ(地味に重要)

なおMATLABのバージョンは2015b以降で、ツールボックスは一切不要です。
また下記、解説の都合上コードが途切れ途切れなので、１つのファイルで見たいかたはGitHubを参照下さい。

①座標データの作成

まずはMATLABに画像データを読み込みます。
今回はイオン東根店のマップを作ります。
岩手に住んでる訳ではないですが、丁度いい感じのマップだったので。。。

東根駅側からイオンに入り、見切り品の刺身を買ってくる最短経路とか気になりますよね？気になれ。（ちなみに過去には、某夢の国を題材に同様のMATLAB芸をEXPOでやった人がいました）

img = imread('https://trip-yamagata-japan.com/barrier-free/images/higashine12-0-1.jpg');
f = figure;
imshow(img);
f.OuterPosition = [100 100 700 600];%画像が小さいので大きめに表示、なくてもOK

hold on;
axis on;

次に、座標データを作成します。
どうやってやるかというと、Figure上の座標を読み、それをExcelに写経します。
この作業はMATLABだけでも出来ますが、MATLAB初心者であるなら積極的にExcelを使うべきと思います。

Figure上の座標を読むのは、「データヒント」をクリックした上で所望の場所をクリックすることで可能です。
「データヒント」の表示場所はバージョンにより異なる場合があるので注意下さい。
最近のバージョンなら画像の右上にカーソルを持っていくと浮かび上がると思います。

[X,Y]をエクセルに写経しましょう。
なおシフト押しながら所望の場所をクリックすれば複数の座標が同時に見れます。

座標のエクセルファイルについては、下記のルールで作成しましょう。
下記のルールは「table型」で読ませる際に推奨するものです。
・ファイル名は英数字のみにする。今回は「address.xlsx」
・１行目はデータ名で、ここも英数字のみにする。今回は「No x y」
・２行目以降はデータ

参考までに

エクセル写経を拒否したい方は右クリック→カーソルデータを~　でMATLABに直接読み込めます。
ただしこの場合、読み込んだ場合のデータの型が構造体で、後処理が面倒になる点注意下さい。
(struct2table関数を使うとよさげ)

②パスデータの作成

MATLAB上にマップ画像と場所ナンバーを重ねて表示した上で、パスをExcelに記入します。
前準備として、①で作成したaddress.xlsxをMATLABに読み込みます。
これにはMATLAB上でaddress.xlsxをダブルクリックして

「選択のインポート」をクリックします。出力タイプがtableとなっている点に注目しましょう。
①に示したルールでExcelファイルを作ったおかげで、MATLABに読み込んだ後の定数名が自動設定されます。超便利。

場所ナンバーの表示は、下記コマンドで表示させます。
暫定のパスを作成することで作業を楽にします。

G = graph(address.No(1),address.No(end)); %暫定のパスの作成
p = plot(G,'XData',address.x,'YData',address.y);

繰り返しになりますが、①に示したルールでExcelファイルを作ったおかげで場所ナンバーをaddress.Noで、x,y座標をaddress.x,address.yで呼ぶことが出来ます。

上記の1（ナンバー最小値）から42（最大値）のパスは暫定的なもので、本来不要ですが
p = plot(G,'XData',address.x,'YData',address.y);
のコマンドは、グラフGの中に最小値および最大値を含むパスが少なくとも１回ないとエラーが出るので暫定パスを設定することでこれを回避しています。

パスのエクセルファイルは下記のルールで作成します。
エラー回避の目的で、上記の暫定パス（1から42）も書いておくと後が楽です。
・ファイル名は「path.xlsx」
・１行目はデータ名「A B」
・２行目以降はデータ

ある程度作りこんだら、MATLABにインポートしてパスを表示させましょう。

G = graph(path.A , path.B); %暫定のパスの作成
p = plot(G,'XData',address.x,'YData',address.y);

暫定パスである1-42が邪魔です。また37-6,6-1が不足、8-38が余分です。
ここまでくるとExcel編集面倒なので、MATLAB上で直接修正します。
色々な方法がありますが、データ数がそれほど多くないなら手作業でいいでしょう。

graph型はよく分からん！という場合はtable型のpathを修正、再度
G = graph(path.A , path.B);
でgraph型を作り直してもよいでしょう。

③２点間の距離を計算、最短経路を探索

dx = address.x(path.A) - address.x(path.B);
dy = address.y(path.A) - address.y(path.B);
Dist = hypot(dx,dy);
G = graph(path.A, path.B,Dist); %距離を重みに設定
p = plot(G,'XData',address.x,'YData',address.y);

path1 = shortestpath(G,29,16); %ダイクストラ法による最短経路探索
highlight(p,path1,'EdgeColor','g','LineWidth',2); %ハイライト表示

hypotは２乗ルートの計算です。ベクトルを引数に出来るので超便利。

なんだか無難な結果になってしまいましたが、今回はここまで。
「通路に人がいる場所は通りにくいので極力避ける」等の制約を加えると楽しそうです。

参考

この最短経路探索は、ダイクストラ法によるものです。
ダイクストラ法の解説は、ヨビノリさんの動画が超分かり易いので皆見ましょう。
https://www.youtube.com/watch?v=X1AsMlJdiok