宝箱(2)

n=3のとき、
全ての箱で全てのアイテムの出現を見るまでに平均16.5回かかる。


ここからが問題。
プレーヤーは箱を開ける直前に、
箱にどのアイテムが入っているか分かるとする。
その情報を開ける箱の選択に使ってよいとする。
このとき、箱を選択する最適なアルゴリズムは?
そして、全ての箱で全てのアイテムの出現を見るまでにかかる回数は?


アルゴリズムでまず簡単なのは、
普通に1つの箱を攻めていき、
その箱に今まで見てないアイテムが出てこないときは、
隣の箱を見に行く、
というようなことをする。


例えば、
箱1はアイテム1、アイテム3をもう見た、
箱2はアイテム2をもう見た、
箱3はまだ見ていない、
という状態で、
次は箱1、箱2、箱3に
それぞれアイテム3、アイテム2、アイテム1が入っているとすると、
箱1はだめ、箱2もだめ、
だから箱3を開ける、
というもっとも単純なアルゴリズム


昨日と同じように求めたいが、うまくいかない。
n=3でもとにかくややこしいことが多すぎる。
しかたがないので、Perlでシミュレートする。
昨日のプログラムをちょっと改変して動かしてみた。


平均12.23回くらいらしい。
意外と減るもんだ。
最後とその前を考えると、
どのアルゴリズムでも11.5回はかかるはず。