今後の研究課題、展望

8 ^結論

8.1 研究成果のまとめ

ペブルゲームに関して、0. . .0を0122. . .2にする最小深さペブルゲーム戦略、012233. . .3に する最小深さペブルゲーム戦略、任意の自然数µ, νに対して0以上がµ個とν . . . ν以上のペブル 状態にする最小深さペブルゲーム戦略が求まった。また、値が0^{のペブルが}1^{つだけになった時} の比較に制限を加えた修正ペブルゲームについて、0. . .0を0122. . .2にする最小深さ修正ペブル ゲーム戦略が求まった。

セレクションネットワークに関して、入力数が2のべき乗数である場合のn入力V 型2セレク ションネットワークとn^入力U ^型2セレクションネットワークの最小深さが、それぞれlog₂n+

⌈log₂log₂n⌉^とlog₂n+⌈log₂log₂n⌉ −1であると求まった。また入力数が2^の2^{のべき乗乗であ} る場合のn入力V 型4セレクションネットワークの最小深さの下界として、log₂n+ log₂log₂n+

⌊log₂(2^{(log2log2n)−1}−log₂log₂n)⌋ −2が得られた。加えて、任意の自然数n, k^{に対して、}n^入力 V型2セレクションネットワーク、n入力V型4セレクションネットワーク、n入力U型2^kセ レクションネットワークのタイトな下界を得る方法が求まった。

U型セレクションネットワークに対応するペブルゲームについては、任意のセレクションする 数に対して一般化された最小深さ戦略が求まっている一方、その深さがいくつになるかの解析が 終わっていない。最小深さペブルプレイ戦略の深さがわかればU型セレクションネットワークの 最小深さの下界が得られるため、任意のセレクションする数に対しての最小深さを一般化して求 めることに繋がる。

4つめとして、3セレクションネットワークの最小深さの下界を求めることが上げられる。

V ^型3^{セレクション} ネットワークの

出力の最小値 min 1 min 2 min 3 min 4 min 4 min 4

min 4

ペブルゲームの 出力の最小値

⌈log₂1⌉= 0

⌈log₂2⌉= 1

⌈log₂3⌉= 2

⌈log₂4⌉= 2

⌈log₂4⌉= 2

⌈log₂4⌉= 2

⌈log₂4⌉= 2 図47: V 型3セレクションネットワークのペブルゲーム解析の出力下界

図47^のようにV ^型3セレクションネットワーク・U ^型3セレクションネットワークをペブル ゲーム解析した際の出力の最小値は、2セレクションネットワークと同じく0122. . .22,0022. . .22 となる。そのため、ペブルゲーム解析を行うだけでは良い下界を得ることができない。この点を 解決することが、3セレクションネットワークの下界を更新するために重要だと考えられる。

謝辞

本研究の遂行におよんで、終始熱心なご指導を頂いた修士論文指導教員の垂井淳准教授に心よ り感謝申し上げます。