Edit of 課題 -- PakiWiki Web

* えくすぷおぷと

計算式の最適化を誰がうまくやるかという問題。

** 準備

Javaをインストールする必要がある。Javaコマンドにパスを通しておく。
私のPCでは、次のバージョンが動作している。
<@quot>
C:\work\prog>java -version
java version "1.6.0_03"
Java(TM) SE Runtime Environment (build 1.6.0_03-b05)
Java HotSpot(TM) Client VM (build 1.6.0_03-b05, mixed mode, sharing)
</>

プログラムについては以下のURLにアップロードしてあるので、ダウンロードしておく。
http://ikejima.org/tmp4/expopt.jar

** 数式
プログラムは自動的に数式を生成する。
このプログラムは次のような数式を生成する。

<@quot>
C:\work\prog>java -cp expopt.jar expopt.ExpressionGenerator
3*3+7*1+9/8+7/3-X+8*3
2/8/2-9/4+9/4/5-4/7+X
3/3*8-2/X-X+1*8/3+8-3
2*X-1+8+4-1-X/4+1*X+2
4-5-2+5/5*X/5*2-X+5+5
9/X-1/6*8+X+5/6-8-7-5
7/9/8+X-3/X-3+6-8/9-1
1-X+4*9+3-X/5*2/5+2/7
5+3*X+7/5*1+X+4+X+X+2
8-7+2/X-8+2/3/1*1-5-1
</>

数式には四則演算を含む。また変数Xを含む。

** 変換

これを等価な数式でより短い式に変換する。
より短かい式とは、文字数が少ない式の事である。
例えば、最初の数式「3*3+7*1+9/8+7/3-X+8*3」を「9+7*1+9/8+7/3-X+8*3」に変換すると、元の式が21文字、変換後の文字数が19文字であるので、スコアは0.90になる。
また、元の式には出現しないが括弧を含む式を作る事も許す事とする。

** サンプル

まず、expoptにはサンプルを準備してある。まず、最初のサンプルはDummyStrategyである。
これは次のように試す。

<@quot>
C:\work\prog>java -jar expopt.jar 10 expopt.DummyStrategy
Start test.
..........
Score: 1.0
</>

このソースはjarコマンドで取り出す事ができる。

<@quot>
C:\work\prog>jar xf expopt.jar
</>

こうして取り出したソースコードは、次のようになっている。

<@quot>
package expopt;

public class DummyStrategy implements OptimizeStrategy {
　　public String optimize(String old){
　　　　return old;
　　}
}
</>

optimizeメソッドがこの中心である。このプログラムの中身は何もせずそのまま返している。
そのため、先程の実行結果ではスコアは1.00になっている。

さらに、目標となるためのプログラムも用意してある。
目標用のプログラムは次のような0.5以下のスコアを出している。
これを目標に頑張って欲しい。

<@quot>
C:\work\prog>java -jar expopt.jar 10 ikeji.IkejiStrategy
Start test.
..........
Score: 0.46180952380952384
</>

** 注意

上記の章で引数として渡している10という数字は問題セット番号である。
これを変えると結果が変わる。
アルゴリズムを作成する場合は、様々な問題に対応するように組むべきである。