Skip to content

Latest commit

 

History

History
113 lines (73 loc) · 13 KB

README_ja.md

File metadata and controls

113 lines (73 loc) · 13 KB

解法

3種類のパズルのうち、wreathはシンプルなビームサーチで非常に短い解が見つかり、他と比較して合計点が低く優先度が低かったため、特に注力していない。 このため、残りの2種類、cubeとglobeの解法について解説する。 どちらのパズルに対する解法も同じ戦略に基づいている。

各操作は大量のピースを一度に動かしてしまうため、各操作をそのまま適用するだけではある程度揃った状態までは到達出来ても、最後まで揃えることは非常に難しい。 そのため、重要となるのは少数のピースのみを入れ替え、残りは一切変化しないような操作列を見つけることである。 実はどちらのパズルでも3ピースのみを入れ替え、残りは一切変化しないような操作列(3-rotと呼ぶことにする)が存在する。

  • cubeの場合の例: d3.f2.d2.-f2.-d3.f2.-d2.-f2
  • globeの場合の例: f0.r0.f0.r1.f0.-r1.f0.-r0

ピース全体のクラスタ分解(クラスタ:操作によって入れ替え可能なピースの集合)を考える。実はcubeの角など、特殊な部分を除くと、残りの全てのクラスタについて、その中の任意の3要素に対する3-rotが存在する。

  • cubeの場合: 角と面の中心と辺の中心が特殊ケース。それ以外のクラスタは対称性を考慮すると、4×4x4の対角部分(1,1)、5x5x5の十字部分(1,2)、6x6x6の対角でも十字でも無い部分(1,2)、4x4x4の辺の部分(0,1)について考えれば十分で、それぞれ両側探索を行うことにより任意の3要素に対する最短の3-rotを全列挙した。最も長いもので14手であった。

  • globeの場合: 行数が奇数の場合の中央部分が特殊ケース。それ以外のクラスタについては、行数を2、列数を2cとすると、R=f0.r0.f0.r1.f0.-r1.f0.-r0が((0,0) (1,c) (1,c-1))という3-rotに対応する。任意の3ピースに対する3-rotは、それら3ピースをRが適用可能な状態へと移動させる操作列A(他のピースは好きに移動して良い)を幅優先探索によって求め、A.R.-Aとすることによって得られる。

3-rotを用いて各クラスタを解く場合の注意点として、3-rotは全て偶置換であるため、全体も偶置換でなければならない。 これらをまとめると、以下のような解法を考えることが出来る。

  1. 特殊な部分を揃える
  2. 揃えた部分は崩さず、残りのクラスタが全て偶置換となるように操作する
  3. 3-rotを用いて各クラスタを独立に解く

上記の解法で全ての問題に対して解を得ることが出来るが、より短い解を得るためには以下が重要である。

  • 3-rotは最短で8手と長いため、3-rotを用いて解く前に、各基本操作や短い操作列によって、ある程度揃った状態まで持っていき、最後の仕上げとして3-rotを用いたほうが良い。
  • 現在構築中の操作列Aに操作列Bを追加する際には、Aの末尾とBの先頭での打ち消しを行うことで操作列が短くなる。例えばA=A'.ri、B=-ri.B'の場合、A.B=A'.ri.-ri.B'=A'.B'となり2手短くなる。
  • 現在構築中の操作列をA=a[0]...a[T-1]とすると、Aの末尾に(i j k)に対する3-rotであるBを追加してa[0]...a[T-1].Bとする代わりに、任意の時刻tに対して、ある(i' j' k')に対する3-rot B'を挿入して a[0]...a[t-1].B'.a[t]...a[T-1]としても同じ結果になる。適切に時刻tを選ぶことで、BよりB'の方が短くなったり、前後での打ち消しが多く発生したりするため、操作列は前から順番に構築していくのではなく、全ての時刻について挿入を試し、最も良い時刻を選択する方が良い。

以上のアイデアを元に、以下のような解法を用いた。

  1. 特殊な部分を揃える。
  2. 基本操作で偶にしつつ、大まかに揃える
  3. 短い操作列である程度まで揃える
  4. 3-rotを任意時刻挿入

以下では各パートの詳細について述べる

1. 特殊な部分を揃える

cubeでは、nが偶数の場合は8つの角、nが奇数の場合には追加で各面の中心6つと各辺の中心12個が特殊ケースに該当する。これらの部分はnが偶数の場合には2x2x2、奇数の場合には3x3x3の問題に帰着して揃えることが出来る。2x2x2は両側探索、3x3x3は既存の最適ソルバ ( https://www.cflmath.com/Rubik/optimal_solver.html )を用いて最適解を求めた。

globeでは、行数が奇数の場合の中央の行が特殊ケースに該当する。この行は左右にローテートするだけで解くことが出来、残りの操作では一切変化しないため、問題から除外できる。

2. 基本操作で偶にしつつ、大まかに揃える(cube)

面操作(r[0],r[n-1]など)とnが奇数の場合の中心操作(r[(n-1)/2]など)は1で揃えた部分を動かしてしまうため使用しない。 残りの各操作は、それによって変化するクラスタのうち、対角にあるもの以外の偶奇を反転させる。 従って、mod2での連立線形方程式を解くことにより、全てのクラスタを偶にする操作列を求めることが出来る。

1で求めた操作列の末尾に連立方程式を解くことで求めた操作列を追加したものから開始し、各クラスタを偶に保つ以下の操作を近傍として焼き鈍し法を行った。評価関数は「操作列の長さ+揃っていないピース数×α(1.5程度)」を使用した。

  • 一つの操作の変更。d[i].r[i] や d[i].r[n-1-i] といった操作は全てのクラスタの偶奇を変化させないため、d[i]をr[i]やr[n-1-i]に変化させることが出来る。
  • 隣接する2つの操作の順番を入れ替える。di.rj→rj.diへの順序入れ替えは-rj.-di.rj.diを適用することに対応し、この操作は実は3ピースの入れ替えを2つ行うことに対応しており、局所性が非常に高く有用である。
  • 2つの操作の追加。d[i]とr[i] や d[i]とr[n-1-i] などの組を任意の位置に挿入する。
  • 2つの操作の削除。d[i]とr[i] や d[i]とr[n-1-i] などの組を選んで一度に削除する。

2. 基本操作で偶にしつつ、大まかに揃える(globe)

globeでは最初から正しい位置に揃えようとするのではなく、最後に操作列の末尾に行シフト操作を追加することで正しい位置にする(例:450123の状態から左シフトを2回を行って012345の状態にする)ことにする。この場合、途中段階でどれだけ揃っているかの計算は、各行についてズレ幅を全通り試して最大値を取ることになる。ただし、全てのピースが異なる色の場合には、偶奇を考える必要がある。行シフト操作(ri)を行うとその行の属するクラスタの偶奇が反転するため、ズレを0にした後に偶置換となるためには、「現在の置換の偶奇」が「上の行と下の行のズレ幅の差の偶奇」と一致していなければならない。そのため、どれだけ揃っているかの計算では、各行についてズレ幅が偶数の場合の最大一致数と奇数の場合の最大一致数を計算し、上下で適切に組み合わせることで求める。

globeの場合、各基本操作によって影響をうけるピース数がcubeに比べて多く、少しだけ変化させることが難しい。そのため、焼き鈍し法ではなく、山登り+kickを行った。

評価関数として、以下の4つの和を用いた

  • 現在の操作列長
  • 間違った位置にあるピース数×3
  • 正しい行の間違った位置にあるピース数: 8手の3-rotでは反対の行へ移動するため、正しい行の間違った位置にある方が揃えにくい
  • 左右の隣接関係が間違っているペア(例:0の右隣に2がある)の数: 各操作は殆どの隣接ペアの関係を保つため、位置が間違っていても隣接関係が正しいと嬉しい

用いた近傍は以下の通り

  • 2つの操作の入れ替え
  • 1つの操作の変更
  • 1つの操作の追加
  • 1つの操作の削除

3. 短い操作列である程度まで揃える(cube)

di.rj.-di.-rj という長さ4の操作が、3ピースの入れ替えを2つ行うことに対応しており、短い上に局所性が高くて有用である。 更に、この操作はdi.rj.rk.-di.-rj.-rkとすることで、di.rj.-di.-rjとdi.rk.-di.-rkという2つの操作をより短い操作列で同時に実行することが可能である。 揃っていないピースが全体の一定割合(0.5程度)以下になるまでは、(操作列の長さの増加量/揃ったピース数の増加量)が最小となるような(操作列,挿入時刻)の組を求めて挿入する貪欲法を行った。

3. 短い操作列である程度まで揃える(globe)

cubeと違い、短くて局所性のある操作は発見できなかった。代わりに、f0.r0.f0という操作に着目した。この操作は上の行の右半分と下の行の左半分を繋げて1つシフトする操作であり、ある程度揃うまでは有用である。また、cubeの場合と違ってクラスタ数が少なく、各クラスタが大きいため、各クラスタ(上からi行目と下からi行目の組)について独立に操作列を求め、最後にそれらをマージすることにした。

各クラスタについて解く部分では、行シフト(ri)、3手シフト(fj.ri.fj)、3-rotの3通りの操作を用い、手順2と同じ評価関数を用いた。各手数について、評価関数値が小さい上位k個(100000程度)を保持するビームサーチを行い、最終的に「現在の操作列長+間違った位置にあるピース数×α(4程度)」が最小となったタイミングの操作列を出力とした。cubeの場合と違い、行シフトと3手シフトは大量のピースを一度に動かし局所性が低いため、任意時刻への挿入ではなく、末尾追加のみを行っている。

最後に、各クラスタについて求めた操作列を一つの操作列にマージし、行シフトを追加して各行のズレを0にする。 この際に、以下の 1. 回転操作の共有、2. 行操作の反転、を行うことで操作数を削減することが出来る。

  • 回転操作の共有: ある行でfj.r0.fjという操作を行い、別の行でfj.r1.fj.という操作を行っている場合、これらをまとめてfj.r0.r1.fjとすることで操作数が2削減される。
  • 行操作の反転: ある行でr0という操作を行う代わりに-r1という操作を行い、それ以降、その行に対するfjのインデックスを1ずらすと同じ結果が得られる。これにより回転操作が共有出来る頻度が上がり、更に最終的なズレ幅が減ってズレ修正のための操作数が削減される。

どの回転操作を共有するか、どの行操作を反転させるかに任意性があるが、列数をC、操作列の長さをLとすると、クラスタ数が2の場合にはO(C^2 L^2)の動的計画法により、最適なマージ方法が計算可能である。 クラスタ数が3以上の場合には、2つずつDPでマージを行った。

4. 3-rotを任意時刻挿入(cube)

このステップでは、ある程度揃った状態から開始し、3-rot の任意時刻への挿入を行うことで完成形まで揃える。以下のように「全て揃えるために必要な3-rotの最小挿入数」を計算し、この値が小さくなるような3-rotのみを挿入する。

各クラスタについて巡回置換分解を考える。同じ色のピースが複数ある場合、巡回置換分解は一意には定まらないが、各巡回置換の長さを(L1,L2,...,Lk)とすると、sum(floor(Li/2))回の3-rotが必要なため、この値が最小となるような巡回置換分解を求めたい。 各クラスタは24ピースしかなく、更に手順3である程度まで揃えてあるため、この最適な巡回置換分解は全探索により高速に計算が可能である。

各残必要数に対して、それを達成する操作列の長さが短い上位k個を順に求めていくビームサーチ(ビーム幅100000程度)と、挿入時刻付近にもう1つ追加で3-rotを挿入する1手先読み貪欲法の二種類を実装した。 nが小さい場合にはビームサーチが、nが大きい場合には1手先読み貪欲法が強かった。

4. 3-rotを任意時刻挿入(globe)

cubeと違い、クラスタが巨大なため、最適な巡回置換分解は大きいサイズの問題では計算することが出来なかった。そのため、「必要な3-rot数」ではなく、「揃っていないピース数」を用い、ビームサーチ(ビーム幅1000程度)を行った。