車両ソート問題とバブルソートとその一般化

  • こちらで車両ソート問題における車両の移動をHakellで一般的に取り扱うことを試してみた
  • この問題は「ソート」の問題である
  • では、いわゆる「1次元配列のソート」と同じ枠組みで考えて、「1次元ソートと車両ソートとを同じルール」で取り扱うことを考えたい
  • Haskellでは、「やりたいこととして同じ(抽象的に同じ仕事)」ものを同一のクラスとして表して、条件依存の部分は、その修飾として取扱いたい、という精神になっているらしい(こちらを参照)
  • なので、まずは、車両ソートと1次元ソートとの「やりたいこととして同じ」部分を抜き出して、それをもっと一般的に「ソートと呼ばれるやりたいこととは」という部分にしてやってみるための頭の体操をしてみよう
  • 車両ソートでは、下の図の斜めの直線が引き込み線、●は1台の車両が移動しようとしているときに納まるスペース、カーブの曲がりは、移動車両に許された移動を表している。ここで、車両は1台ずつ動かすことを考えている

  • では、これと同じ考え方で1次元ソートを考えるとどうなるだろうか
    • 1次元ソートで、隣り合う要素の交換のみを許しているとき、個々の引き込み線には、ただ1つの要素しか入れない。また、交換にあたっては、ある要素は、●(移動しようとするときに納まるスペース)に移動し、移動先の「●納まるスペース」に移動し、さらに、もう1ステップ移動する。その後で、交換の相手が、自身の引き込み線の●に出て、今は空席になっている隣の引き込み線へと移動する。その後で、待機中になっていた要素が、新たに空いた引き込み線に納まる。これで、隣接する2要素の交換が可能である
    • いくつかの制約が出た。そしてそのゴールは?
    • 引き込み線の要素数は1
    • すべての引き込み線には要素が必ず1個入っている
    • 交換は隣同士のみ
    • 交換は1個-1個のペアずつ
    • これはバブルソート(Wiki)
    • ゴールは、引き込み線に入っている要素の並びが求めているものであること
  • では車両ソートにある制約は何だろう。そしてそのゴールは?
    • 引き込み線の要素数は0を含めて任意
    • 交換は隣同士のみ
    • 交換は(複数でやってもよいが、考え方としては)1個-1個のペアずつ
    • ゴールは、すべての車両が一つの引き込み線にあって、その中での車両の並びが求めているものであること
    • ゴールは書き換えることができて、1,2,3,4,5という並びで一つの引き込み線にする、という作業は、相並んだ5つの引き込み線に1つずつの車両を入れ、その並びが4,2,1,3,5のように、偶数群と奇数群とに分かれて、偶数群は降順、奇数群は昇順にすることとしてもよい。そこからは、単純な移動ルールのみで、単一引き込み線に求めた並びを作ることができるから
    • 後者のゴールにしてあれば、バブルソートのゴールと同一のゴール設定にすることができて、統一性が高くなる
    • 1次元ソートには、クイックソートWiki)のようなものもある
    • ある1つの要素を、あるルールで別の場所に移す
    • 移す先は、隣から順に探して行って、ここだ、という基準で行く先を決める
    • これを実施するためには、車両ソートのモデル線路配置では無理である
    • 移動車両の待機点から、すべての引き込み線に移動できるように作る必要がある
    • 絵にするとこんな感じだろうか

  • では車両問題でのバブルソートはどうなる?
    • 図がバブルソートのそれであって
    • 引き込み線の要素数は0を含めて任意
    • 交換は1個-1個のペア
    • ゴールは車両問題なので、バブルソート型の車両問題のゴールと同じ
  • では、これを一般化すると・・・
    • 引き込み線がある
      • 引き込み線には0以上の要素が並ぶ
    • 引き込み線からは、移動待ちの席への矢印がある
      • 移動待ちの席は引き込み線の両側にあってもよい
      • 移動待ちの席から、べつの引き込み線の移動待ちの席へと移動できる
  • 移動待ちの席とその間の移動の可否をどのように一般化するかは、もう少し考える必要がある