車両ソート問題とバブルソートとその一般化
- こちらで車両ソート問題における車両の移動をHakellで一般的に取り扱うことを試してみた
- この問題は「ソート」の問題である
- では、いわゆる「１次元配列のソート」と同じ枠組みで考えて、「１次元ソートと車両ソートとを同じルール」で取り扱うことを考えたい
- Haskellでは、「やりたいこととして同じ(抽象的に同じ仕事)」ものを同一のクラスとして表して、条件依存の部分は、その修飾として取扱いたい、という精神になっているらしい(こちらを参照)
- なので、まずは、車両ソートと１次元ソートとの「やりたいこととして同じ」部分を抜き出して、それをもっと一般的に「ソートと呼ばれるやりたいこととは」という部分にしてやってみるための頭の体操をしてみよう
- 車両ソートでは、下の図の斜めの直線が引き込み線、●は１台の車両が移動しようとしているときに納まるスペース、カーブの曲がりは、移動車両に許された移動を表している。ここで、車両は１台ずつ動かすことを考えている
- では、これと同じ考え方で１次元ソートを考えるとどうなるだろうか
- １次元ソートで、隣り合う要素の交換のみを許しているとき、個々の引き込み線には、ただ１つの要素しか入れない。また、交換にあたっては、ある要素は、●(移動しようとするときに納まるスペース)に移動し、移動先の「●納まるスペース」に移動し、さらに、もう１ステップ移動する。その後で、交換の相手が、自身の引き込み線の●に出て、今は空席になっている隣の引き込み線へと移動する。その後で、待機中になっていた要素が、新たに空いた引き込み線に納まる。これで、隣接する２要素の交換が可能である
- いくつかの制約が出た。そしてそのゴールは？
- 引き込み線の要素数は１
- すべての引き込み線には要素が必ず１個入っている
- 交換は隣同士のみ
- 交換は１個-１個のペアずつ
- これはバブルソート(Wiki)
- ゴールは、引き込み線に入っている要素の並びが求めているものであること
- では車両ソートにある制約は何だろう。そしてそのゴールは？
- 引き込み線の要素数は０を含めて任意
- 交換は隣同士のみ
- 交換は(複数でやってもよいが、考え方としては)１個-１個のペアずつ
- ゴールは、すべての車両が一つの引き込み線にあって、その中での車両の並びが求めているものであること
- ゴールは書き換えることができて、1,2,3,4,5という並びで一つの引き込み線にする、という作業は、相並んだ５つの引き込み線に１つずつの車両を入れ、その並びが4,2,1,3,5のように、偶数群と奇数群とに分かれて、偶数群は降順、奇数群は昇順にすることとしてもよい。そこからは、単純な移動ルールのみで、単一引き込み線に求めた並びを作ることができるから
- 後者のゴールにしてあれば、バブルソートのゴールと同一のゴール設定にすることができて、統一性が高くなる
- １次元ソートには、クイックソートWiki)のようなものもある
- ある１つの要素を、あるルールで別の場所に移す
- 移す先は、隣から順に探して行って、ここだ、という基準で行く先を決める
- これを実施するためには、車両ソートのモデル線路配置では無理である
- 移動車両の待機点から、すべての引き込み線に移動できるように作る必要がある
- 絵にするとこんな感じだろうか
