いちおう最適解は分かったが、
最適アルゴリズムは結局どういうものか分かっていない。
どういう状態に遷移すればいいのか、
見たアイテムの数が同じならどのような状態がよいのか、
これを調べる。
状態は512個ある。
しかし、箱1,2,3を入れ換えた状態、
およびアイテム1,2,3入れ換えた状態は
同じとみなすことができる。
例えば、
状態 111 010 111 と 001 111 111
代数の言葉で書くと、
状態s1とs2に対して、
S3×S3の元σが存在して、
s2 = σ(s1)となるなら
同値関係にあるとする。
すなわち、同値関係にある状態は同じものとみなし、
代表元だけで考える。
具体的には代表元は状態を2進数と読みかえて、
最小の元とでも考える。
E(111 111 111) = 0
- -
E(111 111 110) = 3
- -
E(111 110 110) = 4.5
E(111 111 100) = 4.5
E(111 101 110) = 5
- -
E(110 110 110) = 5.5
E(111 111 000) = 5.5
E(111 110 100) = 5.9
E(111 011 100) = 6.25
E(101 110 110) = 6.25
E(011 101 110) = 6.5
- -
E(110 110 100) = 6.88333333333333
E(111 110 000) = 6.88333333333333
E(111 100 100) = 6.9
E(101 110 100) = 7.24
E(111 010 100) = 7.24
E(011 110 100) = 7.36
E(011 011 100) = 7.75
- -
E(110 100 100) = 8.00222222222222
E(111 100 000) = 8.00222222222222
E(101 110 000) = 8.10166666666667
E(110 010 100) = 8.10166666666667
E(110 110 000) = 8.17222222222222
E(011 100 100) = 8.20666666666667
E(101 010 100) = 8.566
- -
E(111 000 000) = 9.00222222222222
E(100 100 100) = 9.00222222222222
E(110 100 000) = 9.14109259259259
E(011 100 000) = 9.2232962962963
E(010 100 100) = 9.2232962962963
E(001 010 100) = 9.766
- -
E(110 000 000) = 10.0948024691358
E(100 100 000) = 10.0948024691358
E(010 100 000) = 10.2726450617284
- -
E(100 000 000) = 11.1540833333333
- -
E(000 000 000) = 12.1540833333333
同じ値になっている状態のペアがいくつかあることが分かる。
この項、つづく。
