週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICFP contest チームぴゅあぴゅあこーどで私が作った車は、非常に簡単なものでした。しかしなぜかほとんど解けません。なぜ解けないのかは自分でも理解していませんが、何を作ったかを簡単に解説します。

問題の解説

まず問題を簡単に説明します。やるべきことは「車」と、それを動かす「燃料」を提出することです。車はそれにあった特定の燃料しか受け付けません。他のチームからは提出された車だけが見えていて、それを動かす燃料を推測することになります。車を提出したチームは、それを動かす燃料を他のチームが出さない限りは、その車からすべての収益をまるまる手に入れることができます。一方その車を動かす燃料が他のたくさんのチームから提出されてしまうと、車からの収益はそれらのチームと折半することになってしまうので、非常に美味しくありません。なので、車を提出するチームは、なるべくそれを動かす燃料を推測されにくい車を提出する必要があります。

「車」は条件式N個の集まりで、各条件式は次のような形をしています;

  • 例1: ABBCBABCABB - ABCBABCBABCABCB (≥) 0.
  • 例2: BABBEBC - AFDBCBDBEBFBC (>) 0.
    • A から FはN x N 行列が入る変数。たかだか6種。
    • (≥) 0 は「行列の要素全てが0以上」という不等式。
    • (>) 0 は (≥) 0 かつ行列の(1,1)要素が正であるという不等式。
    • つまり、たくさんの行列の積二つの差分が、すべて非負である、という条件。

行列を使った不等式です。ただし、車には行列の要素数は指定されていません。

「燃料」は、非負の整数からなるNxN行列 k個で表現されます。ただし行列の(1,1)要素はすべて正である必要があります。燃料の行列をk個を車の変数に代入して、車の持つ条件式をすべて同時に満たすことができるなら、その車はその燃料で動かすことができます。

車が要求する変数の数は固定なので、燃料はそれと同じ数の変数を提供する必要があります。一方、行列の次元は指定されていないので、燃料を作る側は自由に大きな行列を使うことができます。1x1次元の行列を考えて車をデザインしても、2x2以上の行列を持ってくると容易に解けたりします。

pure pure code ++の車

pure pure code ++のアイデアは以下のもので全部です。最初のものはyuizumiさんのアイデア、真ん中のはソルバ班chunのアイデアだったと思います。

  • 燃料を与えて、それを受け取る車をランダムに生成する。
  • 条件式を厳しいものだけ採用する。
  • 焼きなまし法で解けない車だけ採用する。

まず答えとなる燃料を用意します。次に条件式をランダムに生成して、そのうち設定した燃料が満たす条件式だけ採用します。これを決められた数だけ集めて車を作ります。基本はこれだけです。

条件式は最終的には99本いれていましたが、車を生成するときにはもっと多く作っていて、そのうち一部だけを入れてあります。具体的には、条件式をその左辺の行列の要素の最小値でソートして、小さい方から取っています。これで選ばれる条件式は、与えられた行列でギリギリ満たせるような厳しい条件です。左辺の要素がすべて大きいゆるい条件は採用から外れます。こういう条件だけを採用することで、条件全体を満たす解空間を狭めているつもりです。これは、解きにくい車の条件として、ソルバ班chunから教えてもらったものです。

さらに、得られた車をチームの車ソルバにかけて、解が見つからないものだけを頑丈な車として選んでいます。ソルバにかけた車の1/3がソルバに解かれています。

ここまでが車の作り方です。上の記述では入力として与えられている燃料も、実際にはランダムに生成しています。必要なパラメータは次の通り。

  • chamberの数は2000作って99だけ採用。
  • 各chamberは上下各20個のsectionを持つ。
  • 答えの燃料は変数2--6種、行列の次元は2x2か3x3、要素の値は平均12の指数分布。
    • 今から考えるともっと大きい方が良かったかも。よくこれで全探査を回避できたものです。
  • ソルバは焼きなまし2種類を3分ずつ。

なぜこんな簡単な方法で、非常に強いソルバで1/3しか落とせない問題が出来たのかはよく理解していません。ただ、この問題は車制作の方が自由に難しい問題を作れて圧倒的に有利なので、そもそもあまり解けなくても問題はないのかもしれません。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/474-3ce56a14
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。