最短経路導出

最短経路導出論理を作成した。考えた案は次の通り。


1)デフォルトで、前回作成した最短経路予想を最短経路とする
2)駅をノード化して、子ノード(複数)と親ノードを持てるようにする
−後楽園−本郷三丁目−御茶ノ水
  |
−飯田橋−九段下−
  |
市ケ谷
なら、
後楽園(親)
本郷三丁目(子1)
御茶ノ水(子1の子)
飯田橋(子2)
九段下(子2の子1)
市ケ谷(子2の子2)
のように。
3)開始駅を決めたら、隣接駅全部のノードを作り、子ノードとして追加
4)再帰処理で順次ノードを作るが、子ノードを追加してはいけないルールに合致したら追加しない
[4-a]親ノードに存在する駅(逆戻り、無限ループの防止)
[4-b]行き止まりの駅に着いたが目的地の駅と異なる場合
[4-c]現時点の最短経路と比べて運賃が高くなる場合、または同額だが積算キロ数が多くなる場合
5)運よく目的地の駅に着いたら、[4-c]の論理を使って最短経路と比べる。
最短経路より安い・短い場合は更新する
以上で、子ノードの追加が終わった時点で計算が終了するだろう、と考えて実装した。テストしていたら、東京メトロ内で最長区間の和光市→西船橋を計算したところでブラウザごとフリーズしてしまった。全然計算が終わらない。
で、3)の処理を変えて

3改)隣接する乗換駅 or 終点のノードを作り、子ノードとして追加
上の例なら乗換駅のない本郷三丁目とお茶の水はカット
と、ノードの数を減らしてみたら、劇的に早くなった。和光市→西船橋でも0.1秒くらいで終わる。
ただテストで10件ほど計算してみたけれどどれも最短経路予想と違わない結果になるのが気になる。何か問題あるんじゃないか。
これ以上のデバッグは後回しにして、次回は運賃表示とマップの保存に対応しよう。
仕事が苦しいので他のプログラム作成に情熱を燃やして発散しようと思っていたら仕事以外でもデバッグばかりする羽目になってしまった。


ラジオ

聞く力が足りないのでラジオを聴こうと思い立った。ラジオを録音するソフトとしてradikaがある。4月からradikoの仕様が変わって、一部のファイルを変更しないと再生も録音もできなくなったが、このソフトは非常に便利で、番組表をゲットして簡単に予約録音ができる。多重録音も可能だ。
早速、1週間分の気になる番組を全部録音した。合計30時間くらいあるのではと思われる。好きな番組ができたら、毎週録ってみよう。
また、GetAsfStreamを使えば、海外のラジオ番組も予約録音できる。これは番組表や時差と照らし合わせる必要があるので少々面倒だが、Clover.FMと組み合わせれば全世界のラジオの視聴と録音ができる。好きな放送局を選んだらページのソースを見て、mms://で始まるアドレスをGetAsfStreamにコピペしてやればよい。これで音声教材には困らなさそうだ。


戦力外通告

引っ越しの準備もたけなわ、段ボールがみるみる積みあがっていく。その数20個程度。毎回引っ越しに100個ほど使うので、これで1/5程度か。
しかし私は、荷造りをしていない。なぜか。
数日前、段ボールが来る前に本棚の掃除をしていた。ホコリを拭いておけば、あとは詰めるだけですむから。ところが、どれだけ注意力がないのか、部屋の隅っこの本棚がカビまるけなのを見逃してしまったり、本を拭いて戻す時に数冊角を曲げてしまったりしていた。
このためお叱りを受け、荷造り担当から外されることになった。


FareMap

六帖Webアプリに、FareMapを追加した。思ったよりも進まなかった。
・DB読み込み、データ構造作成
・座標情報を基に線路描画
・最短経路予想機能
・運賃計算(東京メトロ分のみ)
まで完成した。ただこの最短経路予想、都心部ではやはり乗り換え過ぎてしまい本当の最短経路になりにくい。まだ無限ループを防ぐ機能がなく、まだ試していないが全駅を対象にすると無限ループになる可能性がある。
線路描画はそれなりの形になったけれど、駅が密集している部分では駅名が重なってしまっている。これは編集機能を付ければなんとなかるだろう。
まだ実装しなければならないのは
・最安値経路算出
・路線図編集・保存・読み込み機能
・運賃一覧表示
・さらなる路線の追加、メトロ都営直通割引、JRの複雑な運賃計算
先は長い。日曜だというのに本業より遥かに面白いからのめり込んでしまって、疲れた。


FareMap(仮称)

地下鉄が複雑すぎるので、経路の組み合わせが天文学的に増えるおそれを解消するため、まず経路の予想を立ててから計算しよう、と考えた。
1.駅情報に、運賃計算のための営業キロに加えて、緯度と経度を導入する。
2.まず最短経路予想をする。始点から終点までの緯度と経度を比較して、上りと下りどっちに進めば目的地に付きそうかを判断しながら、1本経路を作る。
例えば丸ノ内線新宿駅から半蔵門線半蔵門駅に行きたければ、新宿と半蔵門を比較すると半蔵門は東北方向にあるから荻窪行きではなく池袋行き方面に進めばいいだろうなぁ、と予想する。
で、最短経路の運賃を先に計算しておく。
3.乗り換え駅ごとに分岐して経路探索する。ただし、探索中に最短経路の運賃をオーバーしたらそこの経路は捨てる。
4.乗り換えのない終点駅について、しかも目的地に到達しない経路は捨てる。
5.最短経路より運賃が安い経路があったら、最安値を更新してそれより運賃の高い経路を全部捨てる。
以上で、計算量をかなり減らせるのではないか。まず東京メトロ版から作ってみようと思う。


出勤

1か月に1回の東京への出勤日。今日は土曜なので、平日と小田急の客層が違う。平日は都心へ向かうリーマンばかりだが、今日は学生風ばかり。社内でスマホを見てる人の率が20%→40%と大幅に増える。本を読んでいる人の率は30%→10%に大幅ダウン。でも一番多いのは、寝てる人。
1時間半程度電車で過ごした後、職場まで徒歩25分。長距離通勤するのは、今日が最後となる。


仕事終わった。長時間嫌気がさしてくる中、次のようなことを妄想していた。


運賃表が欲しい。
駅に行くと、路線図と運賃一覧が書いてある表、あれ。
理想としては、路線図上の駅をクリックすると他のすべての駅に一度に運賃が表示されるのがよい。
昔JRでしかも首都圏に限ればあったんだけど、消費増税とともに公開停止してしまった。
主に必要な機能は、
・路線図の作成、保存
・運賃の計算
の2点。
どちらも複雑で大変だ。路線図は、ドラッグ&ドロップして線路を配置するような、凝ったGUIにしてみたい。
運賃計算は、田舎なら楽勝だけど都心の地下鉄網となると、乗り換えのパターンが膨大なのとJRの特例計算てんこ盛りなので、どこまでできるだろうか。検索したら大学の論文になってるくらい難しいようだ。論文だけ見ると簡単なif文があるだけのように見えるけれど。
JRだけでなく首都圏の鉄道全部を盛り込んでみたいものだ。


仕様変更

Ruby On Rails Tutorialが一向に進まない。
さらに、無料サーバーのHerokuの仕様を調べたところ、なんとデータベースが1万行までしか記録できないらしい。それは致命的だ。
これでは将来困るので、言語学習用ソフトはやはりJavaScript+PHPでの開発に切り替えた。
とはいえ、EclipseとGitの存在を知ったことは大きな収穫だった。いままでメモ帳で開発してたもんな。


仕様メモ
せっかく公開するので、マルチユーザー対応にしたい。なので、ユーザー名+パスワードでログインする形式にする。


[LTUser] ユーザー
UserID
UserName
Password

[LTTable] テーブル名
UserID
TableID
TableName

[LTElement]単語・意味・例文の1要素
UserID
TableID
ElementID
Word 単語
Meaning 意味
Example 例文

[LTLog]学習履歴
UserID
TableID
ElementID
Correct 正解したかどうか
Time 日付(年月日で十分)

[主に必要な機能]
ログイン機能
単語の登録
問題提出機能、ロジック
統計機能


特別支援相談室4日目、引っ越し準備1日目

今日は午後から特別支援相談室に子供たちが通った。
一番下の子の、体の動きの発達が遅いので、今日は作業療法士さんに2時間もみっちり体を動かす遊びをしていただいたそうだ。
自治体にはお金がなく、作業療法士さんはボランティアとのこと。


毎日仕事をしている六帖の部屋は、物置と書庫も兼ねている。5年経つうちに、床の足の踏み場がなくなるほど散らかってしまった。この部屋に引っ越しの荷物を詰めることになるので、片付けないといけない。今日は足の踏み場を作って、段ボールをいくつかおけるようなスペースを作った。