クロスバ・スイッチ問題

ええっと、今回は、クロスバ・スイッチ問題ということなんですけど、Ｎクイーンの時のソースの説明が不十分だと思うところがあるので、説明しておきたいと思います。
ソース中に”揺らぎ”と称して、ＣＶａｌｕｅの値（ヒルクライミングタームの係数）を何回か置きに変えています。それはなぜかというと、解が極小解に陥らなくするためです。つまるところ、解が出ずにひたすら同じ動作を繰り返してるという状態をなるべく作らないようにするための工夫です。ニューロンにヒステリシスを使うのも解が出やすくするためです。

というわけで、クロスバ・スイッチいってみよう。

クロスバ・スイッチ問題とは

クロスバ・スイッチ問題とは、「Ｎ×Ｎのマスに縦横効き当たらないようにＮ個並べよ」といった感じのものです。これを読んで”こんな簡単やんけ”と思われた方もいらっしゃると思います。そうです、これだけを読む限りでは、極端な話、対角上に並べてしまえば、終わってしまうのです。しかし、そうではなくて、Ｎ×Ｎのマス目の中でおける場所が限られているのです。虫食いのマス目に並べると考えてもらえればいいと思います。具体的な例として、次のような場合をあげてみます。

あなたは、コンビニの店長です。アルバイトを雇いました。２４時間を８つに割って、８人にそれぞれ１つの時間帯に１人ずつ割り当てようとしています。アルバイト８人の都合を聞くと次のようなリクエストが返ってきました。

これを最適化すると、

まあ、これくらいなら自力でやっても大したことはないと思います。めんどくさいんで、プログラム使いましたが。

ニューラル表現

ニューラル表現は、Ｎクイーン問題と同じです。しかし、リクエストのあるニューロンだけを発火させなければなりません。そこで、リクエストのあるなしを２次元配列であらわすことにします。上の例でいうと、

int **R = { { 1,0,1,0,1,0,1,0 },
　　　　　　　{ 0,0,1,1,1,0,1,1 },
　　　　　　　{ 0,0,1,1,1,1,1,0 },
　　　　　　　{ 1,0,1,0,1,0,0,0 },
　　　　　　　{ 1,0,1,1,0,0,0,0 },
　　　　　　　{ 0,0,0,1,0,1,1,1 },
　　　　　　　{ 1,1,1,1,0,1,0,1 },
　　　　　　　{ 0,1,0,1,1,0,1,0 } };

という具合です。リクエストのないところのニューロンは、常に沈静させておきます。つまりＶ＝０。

動作式

動作式は、Ｎクイーン問題の斜めの条件をはずしたものです。
Ａ，Ｂは定数。

プログラミング

void MainProcess()
{
　int x, y;

　for ( x = 1; x <= NValue; x++ )
　{
　　for ( y = 1; y <= NValue; y++ )
　　{
　　　if ( R[x][y] )
　　　{
　　　　U[x][y] += dU( x, y );
　　　　if ( U[x][y] > UMAX )
　　　　　U[x][y] = UMAX;
　　　　if ( U[x][y] < -UMAX )
　　　　　U[x][y] = -UMAX;
　　　　if ( U[x][y] > UTP )
　　　　　V[x][y] = 1;
　　　　if ( U[x][y] < LTP )
　　　　　V[x][y] = 0;
　　　}
　　}
　}
}

Ｎクイーン問題にリクエストの部分を付け足しただけです。リクエストがあるニューロンのみＵの値を変化させていき（もちろんＶも）、解を求めていきます。リクエストのないニューロンは、ひたすら無視です。

ソースについて

Crossbar.lzh (15KB)

　Crossbar.c　　　　　ソースファイル
　Crossbar.exe　　　実行形式ファイル
　Cross_04.dat　　　例のデータファイル

リクエストの入力をファイルからします。形式は、上記の例では、

8
10101010
00111011
00111110
10101000
10110000
00010111
11110101
01011010

変なところにスペースなどを入れると動きません。きちっと入力してください。

動かすときは、Crossbar.exeにCross_04.datをドラッグしてください。もし動かなければ、ＤＯＳ窓から

Crossbar Cross_04.dat　　とタイプしてください。

データファイルを指定しなければ、Ｎの値を入力し、あとはランダムにリクエストを決めます。

出力

・　　　リクエストなし
◎　　リクエスト
●　　解

今回のプログラムは、ファイルの入力を除けば、ほとんどＮクイーン問題のソースと変わらない。ちょこちょこっと変えただけでできてしまいました。これからの問題をプログラムするに当たっても、大部分の変更なしにできてしますような気がしてきました。これからじゃんじゃんアップしていこうと思ってます。次回は、某Ｒ南高校付属中学数学研究クラブ９８年度文化祭問題（実際の名前を知らない）をやりたいと思います。って何じゃそりゃ。まあ、問題の説明など詳細は、次回のお楽しみです。

戻る　インデックスへ　次へ