目次ページに戻る / 前 / 次

さて、アイデアはアイデアとして、問題はどうやって経路を辿るかです。

最初はデータの整形 3 のときのように辿っていけばええんやろ？と素朴にやってみてたんですがうまくいかず……。

問題に向き合って正攻法でやらないとダメっぽい、真面目に経路探索しないといけないようだぞ、という雰囲気が漂ってきたので、観念して調べることにしました。

こういう場合は気持ちを切り替えるのが吉。通電判定処理の部分がこのアプリケーションの心臓部になるだろうと漠然と考えていたこともあり、重要度に見合った手間だと思うことにしました。急がば廻れでここをちゃんと作っとけばこの後安心して進められるだろうと。

それに、こういう状況は勉強のチャンスです。今まさに自分が作っているもののために必要なためモチベーションが高く（必要性についてすでに理解していて切実）、調査と学習の効率がよくなります。グラフのアルゴリズムや経路探索についてまともに考えたり使ったりしたことがなかったので良い機会でした。

はい。それで、ダイクストラ法を使うことにしました。

ダイクストラ法そのものについてはネット上にも多くの解説コンテンツがありますので説明は省きます。私が下手に説明するよりもそちらを見てもらった方がよいと思います。たとえば次のもの。

他にも、探すと Ruby による実装もたくさん見つかります。

できたものがこれです。300行ちょい。

https://github.com/sonota88/kairo-gokko/blob/step15/tuden.rb

さきほど書いた通り基本はダイクストラ法ですが、いくつか考慮すべき点があります。

たとえば……と説明しだすと話が長くなるので、

とにかくこれで動くようになったんや、

ということにして細かい話は飛ばして次に進みます（気が向いたらあとで別途書くかもしれません）。

（※ ネタバレっぽくなりますが、この部分の処理は最終的に不要になりました。先に読みたい方はステップ36 へどうぞ。）

プロトタイプのときに書きなぐった汚いコードを少し手直しした程度なのでいろいろ怪しいですが、これ以上のリファクタリング・最適化は後まわしにします。先に進みたい。

備考

以下、いくつか備考です。

物理回路との違い

今の時点で物理回路と挙動が違うと分かっているところがあります。

f:id:sonota88:20200305061500p:plain

こういう回路の場合、 A と B 間で電位差がない場合は A-B のエッジには電流が流れないそうです（知りませんでした）。

参考: ホイートストンブリッジを復習 - 始める電子回路

今回作った通電判定器ではこの場合も「通電する」と判定してしまいます。そもそも電位差という概念がないんですよね。この点に関してはすぐに解決策が思い浮かばないので「この世界ではそういうルールなのだ」ということにして目をつぶります。

プロトタイプのとき

今回作っているのは2周目です。

プロトタイプのときは自動テストなしでゴリゴリ書いてました。いくつかのケースを手で動かして確認して、あとはランダムな回路を生成して通電判定器にかけ、 graphviz で可視化して目で見て確認して、だいたい良さそうな感じだと思えるようなところまで持っていく。

たとえば次の図はノード数＝10 でランダムに生成したもので、

行き止まりになっている 4-7 のエッジは通電しない
- 通電 1 で挙げていたパターンが解決されている
3-10 のエッジは、スイッチはすべて ON（--）になっているが、 10-8、 10-6 のエッジ上にあるスイッチが OFF（x, xx）なので通電しない

となっていることが確認できます。

f:id:sonota88:20200305063659p:plain

……ということをやっていたんですが、ここはめんどくさい（ちょっといじるとすぐ壊れる）ので今回はさすがに自動テストを書きました。

ちなみに、プロトタイプを作っていたときはここだけ（やり方を考えるところから実装して十分満足できるまで）で 3週間くらいかかりました。今考えると不必要な最適化をしたりしてたので 1週間くらいは無駄だった気がします。まあ、趣味で楽しんでやってたので、よいのですが。次からは多少は要領よくやれたり勘が働くようになるでしょう。いい経験になりました。

競プロ勢の人たちとか、こういうの朝飯前なんでしょうねー。