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

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件ほど計算してみたけれどどれも最短経路予想と違わない結果になるのが気になる。何か問題あるんじゃないか。
これ以上のデバッグは後回しにして、次回は運賃表示とマップの保存に対応しよう。
仕事が苦しいので他のプログラム作成に情熱を燃やして発散しようと思っていたら仕事以外でもデバッグばかりする羽目になってしまった。

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

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

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


運賃表が欲しい。
駅に行くと、路線図と運賃一覧が書いてある表、あれ。
理想としては、路線図上の駅をクリックすると他のすべての駅に一度に運賃が表示されるのがよい。
昔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 日付(年月日で十分)

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

知っている人には当たり前のことかもしれないけれど、デバッグで一度躓いたので。
メモリ容量が足りないからreallocをして容量を拡張しようとすると、なんとポインタの位置が変わってしまう。したがって、

LPSTR p;

/*何か読み込み処理*/

if(/*バッファ不足*/)

{

p = realloc(p, MAX_SIZE);

}

のようなことをしてはいけない。pの中身を他の変数で参照していたら、reallocした瞬間に他の変数が参照している場所が不正な位置になって、下手するとメモリ破壊、アクセスバイオレーションエラーになる。
また、reallocに失敗すればNULLが返ってくるから、pが参照しているアドレスが誰からも見えなくなってしまう。

LPSTR p;

/*何か読み込み処理*/

if(/*バッファ不足*/)

{

LPSTR ptmp = realloc(p, MAX_SIZE);

if(!ptmp)

{

/*エラー処理*/

return;

}

p = ptmp;

}

とするべきだそうだ。

結局昨日寝たのは0時直前になった。しかもまだ仕事が終わっていない。
で、VB.NETのプロジェクトで起動オプションを解釈しなければいけないことになった、が、VB.NETはなんとデフォルトでMain関数がない！どこで起動する処理をしてるの！？

調べると、VB.NETはコンパイラが見えない位置に勝手にMain関数を作っているらしい。勝手に作られないようにするには、プロジェクトの設定で「アプリケーションフレームワークを有効にする」というチェックボックスを外せばよい。
http://dobon.net/vb/dotnet/programing/startupobject.html

その後、次のSub Mainを元々スタートアップに指定していたフォームの中に入れてやれば、変更前の動作と同じになる。Form1の名前は適宜変更のこと。

Public Shared Sub Main(ByVal CmdArgs() As String)

Application.Run(New Form1())

End Sub

あとはCmdArgs()を解釈してお好みの動作を加えてやればよい。

http://ruby.railstutorial.org/ruby-on-rails-tutorial-book#sec-bundler
現在読んでいるところ。linuxを使ったことがないからか、設定が複雑なのに辟易してきた。まだRubyのコードを一行も書いてないぞ。
どのPCでもブラウザで即使用が可能なJavaScriptや、Xamppのインストール一発で環境を構築できるPHPって手軽でいいよなぁ、と思う。動作する無料サーバも数多くあるし。

Eclipse という IDE(統合開発環境)を使うことにした。無料で、Ruby On Railsが使えるだけでなく、PHP, JavaScriptなども扱えることが理由だ。
インストールは難航した。なぜか起動時に
An internal error occurred during: “Start Ruble bundle manager”.
というメッセージが出て、さらにプロジェクトを作成すると
rails: command not found
と言われた。
http://www.kkaneko.com/rinkou/rubydb/index.html
ここを最初から参照していればよかった。とりあえず、RailsInstallerを実行してRailsを再インストールして、解決した。
開発はまた今度だね。

Try Rubyのコースを修了した。所要時間は15分と書いてあるが慣れないのと英語を読むのがのろいので45分程度かかった。一部ブラウザのバグかポップアップの出ない不具合があったが、どんな言語なのか感じは掴めた。どのメソッドも短く、簡潔。正規表現関連で非常に強力な機能があるので、勉強をしないといけなさそうだ。
Code AcademyでHTML/CSS, JavaScriptを学びなおしている。ここにもRubyのコースがあり、さらに以前使ったけれど概要を全く分かっていないJQueryもコースがある。半年くらいかければここのコースを全部修了できるかな。