« Javaアプレット(22) 行列とは | トップページ | Javaアプレット(24) 言語による配列の違い »

2012/02/02

Javaアプレット(23) グラフ理論とは

2進行列とは何か。一言で言えば2進数の行列です。

普段使っている10進数は0から9までの数(digit)を使いますが、2進数は0と1(bit)のみを使います。つまり2進行列は0と1のみで表される行列です。なぜそのような行列を使うのか?

これは碁盤を数学的にどのように表現するか、というところから来ています。以前のプログラムでは空点が0、黒石が1、白石が2、盤外が3と定義して碁盤は整数の2次元配列で表現していました。数学的には10進数の行列といってよいでしょう。これは盤面が正方形(長方形でも構いません)であることを前提としています。

もっと一般的な盤としてダイヤモンドゲームのような形でも表せるように、グラフ理論という数学を導入しようと思いました。グラフとは点を線でつないだ形のことをいいます。グラフ理論とはこのグラフを扱う数学です。
図:グラフと表による表現
【図31 グラフと表による表現】

上図ではグラフとその各点が結ばれている場合はチェックを入れた表の例を示しています。つまりグラフは表のような形式で表すことができます。これをさらにチェックのところを1、チェックのないところを0として行列で表せば、次のような2進行列になります。
(0 1 1 0 0 0↓1 0 1 1 1 0↓1 1 0 0 1 1↓0 1 0 0 1 0↓0 1 1 1 0 1↓0 0 1 0 1 0)、(0 1 0 1 0 0 0 0 0↓1 0 1 0 1 0 0 0 0↓0 1 0 0 0 1 0 0 0↓1 0 0 0 1 0 1 0 0↓0 1 0 1 0 1 0 1 0↓0 0 1 0 1 0 0 0 1↓0 0 0 1 0 0 0 1 0↓0 0 0 0 1 0 1 0 1↓0 0 0 0 0 1 0 1 0)

今回のプログラミングではまずこの2進行列をクラスとして作ろうとしています。ビット(bit)の並びとして表現しようと思います。Javaのint型の変数には整数では-2147483658~2147483657まで表せますが、内部は0と1のビットになっているため、32ビットのビット並びになっています。

したがって19路盤の碁盤を上記のようなグラフとして2進行列で表すには361ビット×361行の配列、つまり32ビットのint型を12個並べたものを361行分用意すればいいわけです。つまり、
int[][] cell = new int[361][12];
で表すことができます。

当面6路盤を対象とする予定なので、
int[][] cell = new int[36][2];
としておきましょう。

(つづく)

|

« Javaアプレット(22) 行列とは | トップページ | Javaアプレット(24) 言語による配列の違い »

Java」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: Javaアプレット(23) グラフ理論とは:

« Javaアプレット(22) 行列とは | トップページ | Javaアプレット(24) 言語による配列の違い »