木構造

巡回処理は、
・先行順＝行きがけ順
・中間順＝対称順＝通りがけ順（二分木のみ）
・後行順＝帰りがけ順
の３タイプ。


再帰呼び出しで関数を定義すれば、以下のように記述位置だけで使い分けができる。

＜先行順＞

巡回処理(現在要素)
{
現在要素処理
巡回処理(左要素)
巡回処理(右要素)
}

＜中間順＞

巡回処理(現在要素)
{
巡回処理(左要素)
現在要素処理
巡回処理(右要素)
}

＜後行順＞

巡回処理(現在要素)
{
巡回処理(左要素)
巡回処理(右要素)
現在要素処理
}


一般木について、
・リストとは別モノなので先頭にダミーは不要。
・再帰呼び出しを使わない場合はやや煩雑。

＜先行順＞

1.処理
2.子ノード有なら子ノードへ移動し1.へ
3.親ノード有なら親ノードへ移動し3.へ
4.弟ノード有なら弟ノードへ移動し1.へ
5.親ノード無・弟ノード無で終了

＜後行順＞

1.子ノード有なら子ノードへ移動し1.へ
2.処理
3.親ノード有なら親ノードへ移動し2.へ
4.弟ノード有なら弟ノードへ移動し1.へ
5.親ノード無・弟ノード無で終了

合コン座席計算システム

奈良先端科学技術大学院のベンチャー企業「ホープフル・モンスター」が開発した「ザ・セキガエ」という計算システム。合コン参加者のなるべく多くが、不公平なくそれぞれの好みの異性の近くに座れるように席を決める計算システムである。国際会議の査読を通過したれっきとした論文である。研究目的・背景の部分を読んでみたいものである。

S. Kuroiwa, Y. Murata, T. Kitani, K. Yasumoto and M. Ito: "A Method for Assigning Men and Women with Good Affinity to Matchmaking Parties through Interactive Evolutionary Computation（対話型進化計算に基づく男女の相性を考慮した合コンへの割当手法）," Proc. of the 7th Int'l Conf. on Simulated Evolution and Learning. 2008（to appear）

全文→奈良先端科学技術大学 伊藤実研究室

＜仕組み＞

（１）参加者に番号を割り振る
（２）参加者が近くに座りたいと思った相手の番号を第１～３希望まで選び、自分の携帯電話のメールで「ザ・セキガエ」に送信
（３）全員の希望に最も近い席順をサーバーが数学の「組み合わせ」を応用した情報処理学を使い計算
（４）数秒後に携帯メールに座席表を返信する。

男女５人ずつが横一列に向かい合って座る場合、約１００万通りの席順があるが、９８％以上の確率で第１～３希望の異性が自分の正面に座る席順をはじき出せる。男女１５人ずつまでならこの確率を維持できるという。好みが１人に集中するような場合は、希望に添えないこともある。