interprism's blog

インタープリズム株式会社の開発者ブログです。

javaを使って離散的ディリクレ問題を数値的に解く

この投稿は インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる! Advent Calendar 2016 - Qiitaの13日目 の記事です。

こんにちはabeです。 早速本題に入りますが、今回はjavaを使った遊びとしての、離散的ディリクレ問題について書いていきます。

離散的ディリクレ問題とは

簡単に言えば数字を埋めるゲームです。 (自然数であれば何次元でも構いませんが)2次元の場合について説明すると、無限に広がる碁盤の上に、碁石ではなく数字によってが作られています。これに対して、のすべてのに対して、その数字が上下左右の目の数字の平均値になるように数字を埋めることができれば、問題が解けたことになります。

…という説明で理解することは非常に難しいため、具体例を出します。

f:id:interprism:20161211012714j:plain

色々とクォリティの低い図で恐縮ですが、この図は離散的ディリクレ問題の具体例の1つを表しています。ご覧の通り、数字に囲まれた目が2つあるということがわかります。 では、このディリクレ問題を解いてみましょう。

f:id:interprism:20161211013510j:plain

左の目に2、右の目に3を入れるのが正解。 実際、0,1,3,4の平均値は2であり、2,0,6,4の平均値は3です。 これ以外に正解がないことは数学的に保証されています。詳しくは Principles of Random Walk - Springer あたりに書いてあります。先ほど検索をかけてみましたところ、電子版だと70ドルくらいで購入できるみたいですね。高い。

近似値を計算する

はじめ、数字を埋めるゲームと、紹介しましたが、実際に問題を解こうとすると非常に苦労します。下の図の問題は単純そうに見えますが、私は解答を見つけるのに1時間以上かかりました。

f:id:interprism:20161211223913j:plain

お気づきの方も多いとは思いますが、これは結局のところ連立一次方程式ですので、式を立てて、解けば、終わりです。ただの線形代数の具体的な計算問題とみなすことができます。一方で、確率論的な考え方として、Spiter(1964)では、それぞれの目の値は、そこからランダムに動く点が最初に接触する数字の期待値に等しいという事実が紹介してあります。したがって、(元々のゲームのコンセプトが崩壊しますが)完全な解答を出すことをあきらめて、近似値を求めようとすれば、javaの力を借りて実現できると考え、やってみました。方法は以下の通り:

  1. 数字を埋めたいから、上下左右に等確率で動く動点を出発させる
  2. を取り囲む数字の場所に移動するするのを待つ。移動したら、その場所数字を記録する。
  3. 1,2の手順を適当な回数、繰り返し、数字の平均値を計算する。

実際に動かしたコードの一部を恥を忍んで公開したいと思います。

package randomWalk;

class D2MovingPoint {
    int x;
    int y;

    D2MovingPoint(int x, int y){
        this.x = x;
        this.y = y;
    }

    void moveUpward(){
        this.x++;
    }

    void moveDownward(){
        this.x--;
    }

    void moveRight(){
        this.y++;
    }

    void moveLeft(){
        this.y--;
    }

    int getXCoodinate(){
        return this.x;
    }

    int getYCoodinate(){
        return this.y;
    }

    void step(int direction){
        switch(direction){
            case 0:
                this.moveRight();
                break;
            case 1:
                this.moveLeft();
                break;
            case 2:
                this.moveUpward();
                break;
         default:
                this.moveDownward();
        }
    }
}
package randomWalk;

public class D2Inner {

    public static boolean isInbounds(int x, int y){
        if(x < -1 || x > 1){
            return false;
        }

        if(y < -1 || y > 1){
            return false;
        }

        return true;
    }

    public static boolean isInbounds(D2MovingPoint point){
        return isInbounds(point.getXCoodinate(), point.getYCoodinate());
    }

    public static double getScore(D2MovingPoint point){
        if(point.getYCoodinate() >1){
            return 5;
        }

        return 0;
    }
}
package randomWalk;

import java.util.Random;

public class WalkingController {
    private final long numberOfTrials = 10000;

    public double getAverageScore(int x, int y){
        double score = 0;

        for(int round = 0; round<numberOfTrials; round++){
             score += walk(x, y);
        }

        return score/numberOfTrials;
    }

    private double walk(int x, int y){
        Random random = new Random();
        D2MovingPoint point = new D2MovingPoint(x, y);
        int direction;

        while(D2Inner.isInbounds(point)){
            direction = random.nextInt(4);
            point.step(direction);
        }

        return D2Inner.getScore(point);
    }

    public long getNumberOfTrials(){
        return numberOfTrials;
    }
}

クラス名、メソッドの場所、変数の型など突っ込みどころはあるかもしれませんが、ひとまず

  • 座標が定義してあってあとは誰かから言われるがままにその座標を変えていくクラス
  • とその周囲に関する定義クラス
  • 点をランダムに動かし"score"を集計するクラス

ができました。 あとは、値を求めたい目の座標を入れて getAverageScore メソッドを呼べば、終わりです。

試行回数10,000回はさすがに少なすぎたのか、若干値にぶれが出ますが、概ね正解に近い値が出てきます。最後に、私が先ほど1時間以上かけて求めた解答を貼っておきますので、興味のある方は動かして確かめてみてください。 f:id:interprism:20161212004157j:plain

インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる! Advent Calendar 2016 - Qiita14日目の記事

PAGE TOP