セレクションネットワークの最小深さ ―ペブルゲームによる解析―

修 士 論 文 の 和 文 要 旨

研究科・専攻 大学院 情報理工学研究科 情報・ネットワーク工学専攻 博士前期課程 氏 名 中野 吾朗 学籍番号 １９３１１０１ 論 文 題 目 セレクションネットワークの最小深さ―ペブルゲームによる解析― 要 旨

セレクションネットワークという、小さい値を探すネットワークが存在する。このネットワー

クは 2 つの値を比べて小さい順に並び替える操作を決められた順に行うことで小さい値

を取り出す。セレクションネットワークが小さい値を探すのに必要な最小比較回数（最小

サイズ）の研究は進んでいるが、それに比べると最小並列計算時間（最小深さ）の研究

はあまり進んでいない。本研究では、セレクションネットワークの最小深さを求めた。

Yao の先行研究により、任意の取り出す小さい値の数と入力数に対する最小深さのオー

ダーはすでに明らかになっている。本研究では、よりタイトな最小深さの下界を求めるこ

とを目標とした。

本研究ではセレクションネットワークのタイトな最小深さを求めるため、ペブルゲーム解析

を行った。これは値が自身より小さい値と比較する回数(ペブル値)に着目する、Alekseev

が考案した解析手法である。本研究では、ペブル値の組み合わせ(ペブル状態)がセレク

ションネットワークのペブル状態の必要条件を満たすための最小深さとその戦略を求め

ることにより、セレクションネットワークのタイトな最小深さを求めた。

ペブルゲームに関して、ペブル状態

_{00 … 00から0122 … 22以上、012233 … 33以上、任}

意の

_{𝜈𝜈に対して0 … 0𝜈𝜈 … 𝜈𝜈以上にする最小深さペブル戦略が得られた。またペブルゲーム}

のバリエーションである修正ペブルゲームに関して、ペブル状態

_{00 … 00から0122 … 22}

以上にする最小深さ修正ペブルゲーム戦略が得られた。

セレクションネットワークに関して、2 のべき乗個の値から小さい 2 つの値を区別して取り

出す V 型 2 セレクションネットワークと、区別せずに取り出す U 型 2 セレクションネットワ

ークの最小深さが決まった。また 2 の 2 のべき乗乗個の値から小さい 4 つの値を区別し

て取り出す V 型 4 セレクションネットワークの下界が得られた。加えて V 型 2 セレクショ

ンネットワーク・V 型 4 セレクションネットワーク・U 型 2 のべき乗セレクションネットワーク

修士論文

2020

年度（令和

2

年度）

セレクションネットワークの最小深さ

―ペブルゲームによる解析―

2021

年

3

月

10

日

電気通信大学大学院

情報理工学研究科 情報・ネットワーク工学専攻

中野 吾朗

学籍番号

1931101

指導教員 垂井 淳

目 次

1 序論 1 1.1 研究の背景 . . . . 1 1.2 研究の目的 . . . . 1 1.3 研究の結果 . . . . 1 1.4 本論文の構成 . . . . 2 2 必要な定義 3 3 関連動向調査分析と問題点・課題の提示 8 4 セレクションネットワークの最小深さに関する結果 10 5 ペブルゲームの最小深さに関する結果 14 5.1 V 型2セレクションネットワークに対応するペブルゲーム . . . . 14 5.2 U 型セレクションネットワークに対応するペブルゲーム. . . . 17 5.3 V 型4セレクションネットワークに対応するペブルゲーム . . . . 21 5.4 V 型2セレクションネットワークに対応する修正ペブルゲーム . . . . 25 6 証明の方針 27 6.1 セレクションネットワークの最小深さに関する結果の証明の方針 . . . . 27 6.2 ペブルゲームの最小深さに関する結果の証明の方針 . . . . 30 7 証明 32 7.1 セレクションネットワークの最小深さに関する結果の証明 . . . . 32 7.2 ペブルゲームの最小深さに関する結果の証明 . . . . 42 (1) V型2セレクションネットワークに対応するペブルゲームの証明 . . . . 42 (2) U型セレクションネットワークに対応するペブルゲームの証明 . . . . 47 (3) V型4セレクションネットワークに対応するペブルゲームの証明 . . . . 52 7.3 V 型2セレクションネットワークに対応する修正ペブルゲームの証明 . . . . 60 8 結論 66 8.1 研究成果のまとめ . . . . 66 8.2 今後の研究課題、展望 . . . . 66 謝辞 68

図 目 次

1 比較ネットワークのワイヤー. . . . 3 2 比較ネットワークの比較器 . . . . 3 3 4入力V型2セレクションネットワークの例 . . . . 3 4 4入力U型2セレクションネットワークの例 . . . . 4 5 深さ3の比較ネットワークの例 . . . . 4 6 ペブルゲーム . . . . 5 7 ペブル状態の足し算 . . . . 6 8 ペブル状態の掛け算 . . . . 6 9 0123以上の状態の例 . . . . 6 10 0000を0123にする深さ3のペブルゲーム戦略の例 . . . . 7 11 ペブルゲーム解析でのワイヤー . . . . 8 12 ペブルゲーム解析での比較器. . . . 8 13 V 型4セレクションネットワークとペブルゲーム解析の関係 . . . . 9 14 8入力V 型2セレクションネットワークの例 . . . . 10 15 16入力U 型2セレクションネットワークの例 . . . . 11 16 16入力V 型4セレクションネットワークの例 . . . . 12 17 目標状態が0122222のペブルプレイ戦略5.1の例. . . . 14 18 補題5.3のイメージ図. . . . 15 19 目標状態が0022222のペブルプレイ戦略5.6の例. . . . 17 20 補題5.8のイメージ図. . . . 18 21 目標状態が0122333のペブルプレイ戦略5.11の例 . . . . 21 22 補題5.13のイメージ図 . . . . 22 23 目標状態が0122222の修正ペブルプレイ戦略5.16の例 . . . . 25 24 補題5.18のイメージ図 . . . . 26 25 V 型2セレクションネットワークとペブルゲーム解析の関係 . . . . 27 26 目標状態が01222222の最小深さ修正ペブルプレイ戦略5.16の例 . . . . 28 27 8入力V 型2セレクションネットワークの例 . . . . 29 28 補題5.3のイメージ図. . . . 30 29 補題5.2の証明のイメージ図 . . . . 31 30 V 型2セレクションネットワークのペブルゲーム解析の出力下界 . . . . 32 31 U 型2mセレクションネットワークのペブルゲーム解析の出力下界 . . . . 33 32 V 型4セレクションネットワークのペブルゲーム解析の出力下界 . . . . 34

33 深さk +⌈log₂k⌉の2k入力V 型2セレクションネットワークの例 . . . . 37 34 深さk +⌈log₂k⌉ − 1の2k入力U型2セレクションネットワークの例 . . . . 39 35 22k入力V 型4セレクションネットワークの例 . . . . 41 36 目的状態が0122 . . . 2で0を1にする比較が優先される図 . . . . 42 37 Aの値がBの値を超えない戦略のプレイ後のペブル状態の下界. . . . 45 38 Aの値がBの値を超える深さのペブル状態 . . . . 45 39 目的状態が0· µ + ν . . . νでa(≤ b)をa + 1にする比較が優先される図 . . . . 47 40 Aの値がBの値を超えない戦略のプレイ後のペブル状態の下界. . . . 50 41 Aの値がBの値を超える深さのペブル状態 . . . . 50 42 目的状態が01223 . . . 3で0を1にする比較が優先される図 . . . . 52 43 Aの値がBの値を超えない戦略のプレイ後のペブル状態の下界. . . . 56 44 最後の1が2になる深さのペブル状態の下界 . . . . 57 45 Aの値がBの値を超える深さのペブル状態 . . . . 59 46 目的状態が0122 . . . 2で0を1にする比較が優先される図 . . . . 60 47 V 型3セレクションネットワークのペブルゲーム解析の出力下界 . . . . 67

表 目 次

1 D(0· n, 0122 . . . 2)ごとのnの上下界 . . . . 16

2 D(0· n, 0022 . . . 2)ごとのiの上下界. . . . 20

3 D(0· n, 00003 . . . 3)ごとのiの上下界 . . . . 20

1

序論

1.1

研究の背景

並列処理に特化した比較処理である、”2つの値を比べて小さい順に並び替えるという”操作を 決められた順に行う比較ネットワークというものが存在する。セレクションネットワークは小さ い値を探す比較ネットワークのことであり、小さい値を探すために必要な比較回数（最小サイズ） や並列計算時間（最小深さ）の研究がされている。 先行研究により、2つの値を探す2セレクションネットワークの最小サイズ[1][2][3]、3つの値 を探す3セレクションネットワークの最小サイズ[4]が求まり、4つの値を探す4セレクション ネットワークの最小サイズは上界と下界の差が1になっている[5]。これに比べると、最小深さの 研究はあまり進んでいない。Yaoの先行研究[2]によって最小深さのオーダーは求められている が、オーダー記号で表される項の係数の上界や下界についてわからない部分が残っている。 セレクションネットワークを解析する手法として、Alekseevが考案したペブルゲームによる解 析[1]が存在する。これは値が出力されるまでに自身より小さい値と比較する回数（ペブル値）に 着目する手法である。ペブル値の組み合わせ（ペブル状態）がセレクションネットワークのペブ ル状態の必要条件を満たすまでの最小サイズや最小深さを調べることにより、セレクションネッ トワークの最小サイズや最小深さの下界を得ることができる。

1.2

研究の目的

本研究の目的は、セレクションネットワークの最小深さのタイトな下界を求めることである。

1.3

研究の結果

ペブルゲームに関して、0 . . . 0を0122 . . . 2にする最小深さペブルゲーム戦略、012233 . . . 3に する最小深さペブルゲーム戦略、任意の自然数µ, νに対して0以上がµ個とν . . . ν以上のペブル 状態にする最小深さペブルゲーム戦略が求まった。また、値が0のペブルが1つだけになった時 の比較に制限を加えた修正ペブルゲームについて、0 . . . 0を0122 . . . 2にする最小深さ修正ペブル ゲーム戦略が求まった。 セレクションネットワークに関して、入力数が2のべき乗数である場合のn入力V 型2セレク ションネットワークとn入力U 型2セレクションネットワークの最小深さが、それぞれlog₂n +

⌈log2log2n⌉とlog2n +⌈log2log2n⌉ − 1であると求まった。また入力数が2の2のべき乗乗であ る場合のn入力V 型4セレクションネットワークの最小深さの下界として、log₂n + log₂log₂n + ⌊log2(2(log2log2n)−1− log2log2n)⌋ − 2が得られた。加えて、任意の自然数n, kに対して、n入力

V型2セレクションネットワーク、n入力V型4セレクションネットワーク、n入力U型2kセ

1.4

本論文の構成

本論文は本章を含む全7章から構成されている。 第2章では、議論を始める上で必要な定義を行う。 第3章では、先行研究で明らかになっていることと、どのような課題が残っていることを示す。 第4章では、本研究によりセレクションネットワークの最小深さについて新たにわかったこと を示す。 第5章では、本研究によりペブルゲームについて新たにわかったことを示す。 第6章では、第4章・第5章で述べる結果の証明を示す。 第7章では、本研究の成果をまとめ、今後の研究課題や展望について述べる。

2

必要な定義

本セクションでは、議論を始める前に必要な定義を行う。 定義2.1 比較ネットワークとは、値を伝搬するワイヤーと値を比較して並び替える比較器によっ て構築される、任意の数列を入力すると一意の数列を出力するネットワークである。 入力 a b 出力 a b 図 1: 比較ネットワークのワイヤー 入力 a b 出力 min(a, b) max(a, b) 図 2: 比較ネットワークの比較器 比較ネットワークのワイヤーとは図1のように、入力から出力まで値を伝搬するものである。 比較ネットワークの比較器とは、図2のように比較器が接続されている両端のワイヤーに伝搬 されている値を比較し、小さい値が上になるよう並び替えるものである。 定義2.2 nを任意の自然数とする。 比較ネットワークの入力数とは、比較ネットワークに入出力する数列の長さのことである。 n入力比較ネットワークとは、入力数がnである比較ネットワークのことである。 定義2.3 iを任意の自然数とする。 入力列のmin iとは、入力列の中でi番目に小さい値のことである。 入力列のmax iとは、入力列の中でi番目に大きい値のことである。

例として、入力列が1, 6, 7, 3の場合、min 1 = 1, min 2 = 3, min 3 = 6, min 4 = 7である。 max 1 = 7, max 2 = 6, max 3 = 3, max 4 = 1である。

定義2.4 tを任意の自然数とする。 入力 出力 min 1 min 2 図3: 4入力V型2セレクションネットワークの例 V型tセレクションネットワークとは、任意の入力列に対してその中で小さい方からt個の値 を、出力列の最初のt個に小さい方から順番に並ぶよう、並び替える比較ネットワークである。 定義2.5 tを任意の自然数とする。

入力 出力 min 1 or min 2 min 1 or min 2 図4: 4入力U型2セレクションネットワークの例 U型tセレクションネットワークとは、任意の入力列に対してその中で小さい方からt個の値 を、出力列の最初のt個に無作為な順番で並ぶよう、並び替える比較ネットワークである。 定義2.6 比較ネットワークの深さとは、1つの比較器が値を比較して並び替えるのに要する時間 を単位とする、比較ネットワークの処理時間である。 入力 a b c d 出力 深さ1 深さ2 深さ3 図5: 深さ3の比較ネットワークの例 例として、図5の比較ネットワークの深さは3である。 図5の比較ネットワークははじめにbとcの比較を行う。これは深さ1での比較になる。 深さ1での比較の結果によって、上下の比較器がそれぞれaとb,cとdの比較を行うか、aとc, bとdの比較を行うかが変わるため、この2つの比較は深さ1での比較より後で行われる。よっ て、上下の比較器による比較は深さ2で行われる。 右側の比較は深さ2の比較の結果によって何を比較するかが変わるため、深さ2の比較より後 で行われる。よって、右の比較器による比較は深さ3で行われる。したがって、図5の比較ネッ トワークの深さは3とわかる。 定義2.7 n, tを任意の自然数とする。 V Depth(t, n)とは、最も深さが小さいn入力V型tセレクションネットワークの深さである。 これを、n入力V型tセレクションネットワークの最小深さと呼ぶ。 定義2.8 n, tを任意の自然数とする。 U Depth(t, n)とは、最も深さが小さいn入力U型tセレクションネットワークの深さである。 これを、n入力U型tセレクションネットワークの最小深さと呼ぶ。

定義2.9 ペブルゲームとは、複数個存在するペブルに対して「ペブル同士の値を比較して値が大 きいペブルの値を1大きくする」という操作を行い、ペブルの値の組み合わせ（ペブル状態）が 特定の状態になることを目指すゲームである。 プレイとは、ペブル同士の値を比較して値が大きいペブルの値を1大きくする操作を行うこと である。比較したペブルの値が同じの場合、片方のペブルの値を1大きくしてもう片方はそのま まにする。 ペブルとは、非負整数からなる値を1つ持つ物体である。 ペブル状態とは、ペブルゲームのペブルの値の組み合わせである。 ペブル状態 ペブル状態 aとb, cとdの 比較をプレイ a b c d e min{a, b} max{a, b} + 1 min{c, d} max{c, d} + 1 e 図6: ペブルゲーム 定義2.10 P, Qを任意のペブル状態、a, bを任意の自然数とする。 ペブル状態aは、値がaのペブルが1つだけあり、他にペブルが無いペブル状態である。 ペブル状態a . . . aは、値がaのペブルが任意の数だけあり、他にペブルが無いペブル状態で ある。 ペブル状態P Q, P + Qは、ペブル状態Pに含まれるペブル全てと、ペブル状態Qに含まれる ペブル全てからなるペブル状態である。 ペブル状態P· bは、ペブル状態Pに含まれるペブル全てがb個づつ存在するペブル状態である。 定義2.11 P, Qを任意のペブル状態とする。 PがQ以上の状態とは、任意の自然数iに対して次のいずれかが成り立つということである。 1. P の中で値がi番目に小さいペブルPiの値が、Qの中で値がi番目に小さいペブルQiの値 以上である。 2. P の中で値がi番目に小さいペブルPiの値が、Qの中で値が最も大きいペブルの値以上で ある。 定義2.12 ペブルプレイ戦略とは、ペブルゲームにおいてある状態から別の状態にするための、プ レイの手順を纏めたものである。

ペブル状態 P Q P + Q + = p1 p1 p2 p2 p3 p3 q1 q1 q2 q2 q3 q3 図7: ペブル状態の足し算 ペブル状態 P P· 3 · 3 = p1 p1 p1 p1 p2 p2 p2 p2 p3 p3 p3 p3 図8: ペブル状態の掛け算 ≤ ≤ 状態0123 0123以上の状態 0 1 2 3 0 2 2 3 3 4 4 図9: 0123以上の状態の例

初期状態とは、ペブルプレイ戦略に従ってプレイする際の最初の状態と定めた、プレイ開始時 の状態である。 目的状態とは、ペブルプレイ戦略に従ってプレイする際にこの状態以上になったら終わると定 めた、プレイ終了時の状態である。 深さ1 深さ2 深さ3 0と0 0と0 を比較 0と0 1と1 を比較 0と1 1と2 を比較 初期状態 目標状態 0 0 0 0 0 0 1 1 0 1 1 2 0 1 2 3 図10: 0000を0123にする深さ3のペブルゲーム戦略の例 定義2.13 ペブルゲームの深さとは、用いるペブルが重複しないプレイを比較ネットワークの比 較のように並列で処理するとしたときの、ペブルをプレイする時間を単位とする、ペブルプレイ 戦略の処理時間である。 定義2.14 P, Qを任意のペブル状態とする。 D(P, Q)とは、ペブル状態P からQ以上の状態になるために必要なペブルプレイ戦略の最小深 さである。 定義2.15 修正ペブルゲームとは、「値が0のペブルがひとつだけとなったペブル状態では、値が 0のペブルと他のペブルの比較を行わない」という制約を追加したペブルゲームである。 定義2.16 修正ペブルプレイ戦略とは、修正ペブルゲームの制約を満たすペブルプレイ戦略である。 定義2.17 P, Qを任意のペブル状態とする。 DF(P, Q)とは、ペブル状態P からQ以上の状態になるために必要な修正ペブルプレイ戦略の 最小深さである。

3

関連動向調査分析と問題点・課題の提示

Alekseevの先行研究[1]によれば、比較ネットワーク上でペブルゲームを行った際の出力につ いて、面白い事実がわかっている。 入力 a b 出力 a b 図11: ペブルゲーム解析でのワイヤー 入力 a b 出力 min(a, b) max(a, b) + 1 図 12: ペブルゲーム解析での比較器 比較ネットワーク上でペブルゲームを行う際は、比較ネットワークの入力部には値が0のペブル が入力され、比較ネットワークの値の代わりにペブルが移動し比較されて出力される。ワイヤー は図11のように入力から出力までペブルを伝搬する。比較器は図12のように、比較器が接続さ れている両端のワイヤーに伝搬されている値を比較し、値が大きいペブルの値を1大きくした後、 小さい値が上になるよう並び替える。 Alekseevの先行研究[1]によれば、比較ネットワーク上でペブルゲームを行った際の出力につ いて、次の補題が成り立つ。 補題3.1 [1] Aを任意の比較ネットワークとする。nをAの入力数とする。pebble_iをA上でペブ ルゲームを行った際の、i番目のワイヤーが出力するペブルの値とする。compmin_iをAに1から nまでの自然数全てを含む数列を入力する際の、i番目のワイヤーが出力する値の最小値とする。 この時、次の式が成り立つ。

pebble_i≥ log₂compmin_i (1)

この補題3.1を用いることで、例3.2のように比較ネットワークとペブルゲームを関連付けるこ とができる。 例3.2 V 型4セレクションネットワークには、それぞれ1∼4番目に小さい値を出力する4つの ワイヤーと、1∼4番目に小さい値を出力しないワイヤーが存在する。 任意のV 型4セレクションネットワーク上でペブルゲーム解析を行う。 V 型4セレクションネットワークの出力の最小値は図13 のようになることから、V 型4セレ クションネットワーク上でペブルゲーム解析を行った場合、2番目に小さい値を出力するワイヤー に出力されるペブルの値は1以上である。3, 4番目に小さい値を出力するワイヤーに出力される ペブルの値は2以上である。1∼4番目に小さい値を出力しないワイヤーに出力されるペブルの値 は3以上である。 Yaoの先行研究[2]より、U型セレクションネットワークの最小深さについての以下の定理がわ かっている。

V 型4セレクション ネットワークの 出力の最小値 min 1 min 2 min 3 min 4 min 5 min 5 min 5 ペブルゲームの 出力の最小値 ⌈log21⌉ = 0 ⌈log22⌉ = 1 ⌈log23⌉ = 2 ⌈log24⌉ = 2 ⌈log25⌉ = 3 ⌈log25⌉ = 3 ⌈log25⌉ = 3 図13: V 型4セレクションネットワークとペブルゲーム解析の関係 定理3.3 [2] n, tを任意の自然数とする。 この時、n入力U型tセレクションネットワークの最小深さU Depth(t, n)について次の式が成 り立つ。 t⌈log₂(t + 1)⌉ ≥ n 2U Depth(t,n) ⌊log∑2t⌋ i=0 [ (⌈log₂(t + 1)⌉) ( U Depth(t, n) i )] (2)

U Depth(t, n)≥ log₂n + log₂

[ 1 t⌊log₂(t + 1)⌋ ( U Depth(t, n) ⌊log2t⌋ )] (3) 定理3.4 [2] tを2以上の自然数、nを十分に大きい自然数とする。 この時、n入力U 型tセレクションネットワークの最小深さU Depth(t, n)、n入力U 型2セレ クションネットワークの最小深さU Depth(2, n)について次の式が成り立つ。

U Depth(2, n) = log2n + log2log2n +O(1) (4)

U Depth(t, n) = log₂n +⌊log₂t⌋ log₂log₂n +O(log₂log₂log₂n) (5)

Yaoの先行研究[2]の定理3.3, 4を使うことで、探す小さい値の数がいくつのセレクションネッ

トワークでも、最小深さのオーダーを求めることができる。しかし、2セレクションネットワー

クの最小深さの定数項や、tセレクションネットワークの最小深さのO(log₂log₂log₂n)項の係数

の上下界にわからない部分が残っている。

本研究では、セレクションネットワークが探す小さい値の数を特定の値に固定した場合の、セ レクションネットワークの最小深さのオーダー記号を使わない一意の下界を求める。

4

セレクションネットワークの最小深さに関する結果

任意の入力数のV 型2セレクションネットワーク・U 型2mセレクションネットワーク・V 型 4セレクションネットワークの最小深さについて、それぞれに対応するペブルゲーム戦略の深さ を数えることで、新たな下界が得られることがわかった。またV 型2セレクションネットワーク については、対応する修正ペブルゲーム戦略の深さを数えることによってさらに良い下界が得ら れることがわかった。 命題4.1 nを任意の自然数とする。 この時、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· n としてペブルプレイ戦略5.1をプレイした時の深さ以上である。 命題4.2 n, mを任意の自然数とする。 この時、n入力U 型2mセレクションネットワークの最小深さU Depth(2m, n)は、初期状態を 0· nかつ自然数µ, νをµ = 2m, ν = m + 1としてペブルプレイ戦略5.6をプレイした時の深さ以 上である。 命題4.3 nを任意の自然数とする。 この時、n入力V 型4セレクションネットワークの最小深さV Depth(4, n)は、初期状態を0· n としてペブルプレイ戦略5.11をプレイした時の深さ以上である。 命題4.4 nを任意の自然数とする。 この時、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· n として修正ペブルプレイ戦略5.16をプレイした時の深さ以上である。 出力の最小値 min 1 min 2 min 3 min 3 min 3 min 3 min 3 min 3 図14: 8入力V 型2セレクションネットワークの例 入力数が2のべき乗で表されるとき、命題4.4・命題4.2より得られる最小深さの下界と同じ深 さの、図14のようなV 型2セレクションネットワーク・図15のようなU型2セレクションネット

ワークが存在する。これにより、入力数が2のべき乗で表されるV 型2セレクションネットワー ク・U 型2セレクションネットワークの最小深さを決定した。 命題4.5 kを任意の自然数とする。 この時、2k入力V 型2セレクションネットワークの最小深さについて次の式が成り立つ。 V Depth(2, 2k) = k +⌈log₂k⌉ (6) 出力の最小値 min 1 min 1 min 3 min 3 min 3 min 3 図15: 16入力U型2セレクションネットワークの例 命題4.6 kを任意の自然数とする。 この時、2k_{入力U 型2セレクションネットワークの最小深さについて次の式が成り立つ。} U Depth(2, 2k) = k +⌈log₂k⌉ − 1 (7) 入力数が2の2のべき乗乗で表されるとき、命題4.3より最小深さの下界が得られる。また、図 16のようなV 型4セレクションネットワークより最小深さの上界が得られる。これにより、入力 数が2の2のべき乗乗で表されるV 型4セレクションネットワークの最小深さの下界と上界が得 られた。

1 セレクション _{ネットワーク} V 型 2 セレクションネットワーク 出力の最小値 min 1 min 2 min 3 min 4 min 5 min 5 min 5 min 5 図16: 16入力V 型4セレクションネットワークの例 命題4.7 kを任意の自然数とする。この時、22k入力V 型4セレクションネットワークの最小深 さについて、次の式が成り立つ。 2k+ k + ⌈ log₂(2k−1− k) ⌉ − 2 (8) ≤ V Depth(4, 22k ) (9) ≤ 2k_{+ k +}⌈_log 2(22k−1− 2k−1− 1) ⌉ + ⌈ log₂ ⌈ log₂(22k−1− 2k−1− 1) ⌉⌉ (10) V 型4セレクションネットワークの上界についてはあまり調べられていないため、今後の研究 でより良い上界が得られると予想される。 セレクションネットワークの最小深さは入力数に比例するため、命題4.5・命題4.6・命題4.7の 系として、任意の入力数に対してのV 型2セレクションネットワーク・U型2セレクションネッ トワーク・V 型4セレクションネットワークの最小深さの次の下界と上界が得られた。（証明略） 系4.8 nを任意の自然数とする。 この時、n入力V 型2セレクションネットワークの最小深さについて次の式が成り立つ。

系4.9 nを任意の自然数とする。

この時、n入力U 型2セレクションネットワークの最小深さについて次の式が成り立つ。

⌊log2n⌋ + ⌈log2⌊log2n⌋⌉ − 1 ≤ UDepth(2, n) ≤ ⌈log2n⌉ + ⌈log2⌈log2n⌉⌉ − 1 (12)

系4.10 nを任意の自然数とする。

この時、n入力V 型4セレクションネットワークの最小深さについて次の式が成り立つ。

2⌊log2log2n⌋₊⌊log

2log2n⌋ + ⌊log2(2⌊log2log2n⌋−1− ⌊log2log2n⌋)⌋ − 2 (13)

≤ V Depth(4, n) (14)

≤ 2⌈log2log2n⌉₊⌈log

2log2n⌉ + ⌈log2(22⌈log2log2n⌉−1− 2⌈log2log2n⌉−1− 1)⌉ +⌈log₂⌈log₂(22⌈log2log2n⌉−1− 2⌈log2log2n⌉−1− 1)⌉⌉

5

ペブルゲームの最小深さに関する結果

セレクションネットワークの最小深さの下界を求めるために、ペブルゲームについて解析を 行った。

5.1

V 型 2 セレクションネットワークに対応するペブルゲーム

ペブル状態0122 . . . 22以上の状態にする、次のペブルプレイ戦略5.1が存在する。 ペブルプレイ戦略5.1 1. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さいペブル の値が2以上なら、比較を終了する。 2. そうでないなら下記の比較を同じ深さで行い、次の深さへ進む。 (a) 0同士の比較を可能な限り多く行う。 (b) 上記の比較で0が余り、1が1個以上あるなら、0と1の比較を1回行う。 (c) 上記の比較に用いない1同士の比較を可能な限り多く行う。 0と0 0と0 0と0 を比較 0と0 0と0 1と1 を比較 0と0 1と1 1と1 を比較 0と1 1と1 を比較 初期状態 目標状態以上 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 2 0 1 1 1 2 2 2 0 1 2 2 2 2 2 図17: 目標状態が0122222のペブルプレイ戦略5.1の例 このペブルプレイ戦略は、値が0のペブルを含む任意の状態から、0122 . . . 22以上の状態にす る最小深さのペブルプレイ戦略であることがわかった。 補題5.2 ペブルプレイ戦略5.1は、値が0のペブルを含む任意のペブル状態から、ペブル状態 0122 . . . 2以上の状態にする最小深さペブルプレイ戦略である。 補題5.2を証明するために、よく似た2つのペブル状態から目的状態0122 . . . 2までの最小深さ を比べる次の補題5.3を証明した。 補題5.3 a, bを任意のa≤ bを満たす自然数、P を任意のペブル状態とする。 この時、ペブル状態P + a + bとP + (a− 1) + (b + 1)がどちらも値が0のペブルを含んでいる 状態ならば、次の式が成り立つ。 D(P + a + b, 0122 . . . 2)≤ D(P + (a − 1) + (b + 1), 0122 . . . 2) (16)

a− 1→aが 1回多い b→ b + 1が 1回多い P0 a− 1 b 目的状態 必要深さ 少ない 多い P a b P a− 1 b + 1 0122 . . . 2 図18: 補題5.3のイメージ図 最小深さペブルプレイ戦略5.1をプレイした時の深さを数えることにより、補題5.2の系とし て、いくつかの状態から0122 . . . 2以上の状態までの最小深さが得られた。（証明略） 系5.4 kを任意の自然数とする。 この時、次の式が成り立つ。 D(0 + 1, 0122 . . . 2) = 0 (17) D(0 + 1· k, 0122 . . . 2) = 1 + D ( 0 + 1· ⌊ k 2 ⌋ , 0122 . . . 2 ) (18) =⌊log₂k⌋ (19) D(0· 2k, 0122 . . . 2) = k + D(0 + 1· k, 0122 . . . 2) (20) = k +⌊log₂k⌋ (21) ペブルゲームの最小深さは入力数に比例するため、系5.4より補題5.2の系として、任意の数の 値が0のペブルのみからなる状態から、0122 . . . 2以上の状態までの最小深さの下界と上界が得ら れた。（証明略） 系5.5 nを任意の自然数とする。 この時、n個の値が0のペブルのみからなる状態から0122 . . . 2以上の状態までの最小深さにつ いて、次の式が成り立つ。

⌊log2n⌋ + ⌊log2⌊log2n⌋⌋ ≤ D(0 · n, 0122 . . . 2) ≤ ⌈log2n⌉ + ⌊log2⌈log2n⌉⌋ (22)

補題5.2とプログラムによる計算により、D(0· n, 0122 . . . 2)が0∼19になるnの上界と下界の

深さD(0· n, 0122 . . . 2) 入力数n 下界 上界 0 1 1 1 2 2 3 3 4 4 5 8 5 9 12 6 13 20 7 21 32 8 33 64 9 65 128 10 129 224 11 225 384 12 385 736 13 737 1312 14 1313 2432 15 2433 4480 16 4481 8192 17 8193 16384 18 16385 32768 19 32769 61056 表1: D(0· n, 0122 . . . 2)ごとのnの上下界

5.2

U 型セレクションネットワークに対応するペブルゲーム

任意の自然数µ, νに対して、µ個の値が0のペブルとそれ以外の値がνのペブル状態以上の状 態にする、次のペブルプレイ戦略が存在する。 ペブルプレイ戦略5.6 1. 値がµ + 1番目に小さいペブルの値がν以上なら、比較を終了する。 2. そうでないなら下記の比較を同じ深さで行い、次の深さへ進む。 (a) 値が1番目に小さいペブルと、値がµ + 1番目に小さいペブルを比較する。 (b) 値が2番目に小さいペブルと、値がµ + 2番目に小さいペブルを比較する。 (c) . . . (d) 値がi番目に小さいペブルと、値がµ + i番目に小さいペブルを比較する。 (e) . . . (f) 値がµ番目に小さいペブルと、値が2µ番目に小さいペブルを比較する。 (g) 値が2µ + 1番目に小さいペブルと、値が2µ + 2番目に小さいペブルを比較する。 (h) 値が2µ + 3番目に小さいペブルと、値が2µ + 4番目に小さいペブルを比較する。 (i) . . . (j) 値が2µ + 2i− 1番目に小さいペブルと、値が2µ + 2i番目に小さいペブルを比較する。 (k) . . . 0と0 0と0 0と0 を比較 0と0 0と0 1と1 を比較 0と1 0と1 1と1 を比較 0と1 0と2 2と2 を比較 初期状態 目標状態以上 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 2 0 0 1 2 2 2 2 0 0 2 2 2 3 3 図19: 目標状態が0022222のペブルプレイ戦略5.6の例 このペブルプレイ戦略は、値が0のペブルをµ個以上含む任意の状態から、µ個の値が0のペ ブルとそれ以外の値がνのペブル状態以上の状態にする最小深さのペブルプレイ戦略であること がわかった。 補題5.7 ν, µを任意の自然数とする。 この時、ペブルプレイ戦略5.6は、値が0のペブルをµ個以上含む任意のペブル状態から、µ個 の値が0のペブルとそれ以外の値がνのペブル状態以上の状態にする最小深さペブルプレイ戦略 である。

補題5.7を証明するために、よく似た2つのペブル状態から目的状態0· µ + ν . . . νまでの最小 深さを比べる次の補題5.8を証明した。 補題5.8 ν, µを任意の自然数、a, bを任意のa≤ bを満たす自然数、Pを任意のペブル状態とする。 a− 1→aが 1回多い b→ b + 1が 1回多い P0 a− 1 b 目的状態 必要深さ 少ない 多い P a b P a− 1 b + 1 0· µ ν . . . ν 図20: 補題5.8のイメージ図 この時、次の式が成り立つ。 D(0· µ + P + a + b, 0 · µ + ν . . . ν) ≤ D(0 · µ + P + (a − 1) + (b + 1), 0 · µ + ν . . . ν) (23) 最小深さペブルプレイ戦略5.6をプレイした時の深さを数えることにより、補題5.7の系とし て、いくつかの状態から0022 . . . 2以上、00003 . . . 3以上の状態までの最小深さが得られた。（証 明略） 系5.9 kを任意の自然数とする。 この時、目標状態が0022 . . . 2の場合の最小深さについての次の式が成り立つ。 D(00, 0022 . . . 2) = 0 (24) D(00 + 1· k, 0022 . . . 2) = 1 + D ( 00 + 1· ⌈ k 2 − 1 ⌉ , 0022 . . . 2 ) (25) =⌈log₂(k + 2)⌉ − 1 (26) D(0· 2k, 0022 . . . 2) = k− 1 + D(00 + 1 · (2k − 2), 0022 . . . 2) (27) = k− 1 + ⌈log₂(2k)⌉ − 1 (28) = k +⌈log₂k⌉ − 1 (29) また、目標状態が00003 . . . 3の場合の最小深さについての次の式が成り立つ。 D(0000, 00003 . . . 3) = 0 (30) D(0000 + 2· k, 00003 . . . 3) = 1 + D ( 0000 + 2· ⌈ k 2 − 2 ⌉ , 00003 . . . 3 ) (31) =⌈log₂(k + 4)⌉ − 2 (32)

D(0· 2k, 00003 . . . 3) (33) = D(0000 + 1· (4k − 8) + 2 · 3 · (2(k − 3)(k − 2)), 00003 . . . 3) + k − 2 (34) ペブルゲームの最小深さは入力数に比例するため、系5.9より補題5.7の系として、任意の数の 値が0のペブルのみからなる状態から、0022 . . . 2以上の状態までの最小深さの下界と上界が得ら れた。（証明略） 系5.10 nを任意の自然数とする。 この時、n個の値が0のペブルのみからなる状態から0022 . . . 2以上の状態までの最小深さにつ いて、次の式が成り立つ。

⌊log2n⌋ + ⌈log2⌊log2n⌋⌉ − 1 ≤ D(0 · n, 0022 . . . 2) ≤ ⌈log2n⌉ + ⌈log2⌈log2n⌉⌉ − 1 (35)

補題5.7とプログラムによる計算により、D(0· n, 0022 . . . 2)が0∼18になるnの上界と下界の

深さD(0· n, 0022 . . . 2) 入力数n 下界 上界 0 1 2 2 3 4 3 5 6 4 7 8 5 9 16 6 17 24 7 25 44 8 45 76 9 77 128 10 129 256 11 257 448 12 449 800 13 801 1536 14 1537 2784 15 2785 5120 16 5121 9504 17 9505 17696 18 17697 32768 表2: D(0· n, 0022 . . . 2)ごとのiの上下界 深さD(0· n, 00003 . . . 3) 入力数n 下界 上界 0 1 4 1 5 5 3 6 8 4 9 12 5 13 18 6 19 32 7 33 52 8 53 88 9 89 160 10 161 276 11 277 512 12 513 896 13 897 1664 14 1665 3072 15 3073 5632 16 5633 10240 17 10241 19456 表3: D(0· n, 00003 . . . 3)ごとのiの上下界

5.3

V 型 4 セレクションネットワークに対応するペブルゲーム

ペブル状態01223 . . . 3以上の状態にする、次のペブルプレイ戦略5.11が存在する。 ペブルプレイ戦略5.11 1. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さいペブ ルの値が2以上かつ、5番目に小さいペブルの値が3以上なら、比較を終了する。 2. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さいペブルの値が2以上なら、下 記の比較を同じ深さで行い、次の深さへ進む。 (a) 0と2の比較を1回行う。 (b) 1と2の比較を1回行う。 (c) 上記の比較に用いない2同士の比較を可能な限り多く行う。 3. どちらでもないなら下記の比較を同じ深さで行い、次の深さへ進む。 (a) 0同士の比較を可能な限り多く行う。 (b) 上記の比較で0が余り、1が1個以上あるなら、0と1の比較を1回行う。 (c) 上記の比較に用いない1同士の比較を可能な限り多く行う。 (d) 上記の比較で1が余り、2が1個以上あるなら、1と2の比較を1回行う。 (e) 上記の比較に用いない2同士の比較を可能な限り多く行う。 0と0 0と0 0と0 を比較 0と0 0と0 1と1 を比較 0と0 1と1 1と1 を比較 0と1 1と1 2と2 を比較 0と2 1と2 2と2 を比較 初期状態 目標状態以上 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 2 0 1 1 1 2 2 2 0 1 2 2 2 2 3 0 1 2 3 3 3 3 図 21: 目標状態が0122333のペブルプレイ戦略5.11の例 このペブルプレイ戦略が、値が0のペブルを1個と1以下のペブルを2個以上含んでいる任意 の状態から、01223 . . . 3以上の状態にする最小深さのペブルプレイ戦略であることがわかった。 補題5.12 ペブルプレイ戦略5.11は、ペブル状態012233 . . . 3以上の状態にする最小深さペブル プレイ戦略である。 補題5.12を証明するために、よく似た2つのペブル状態から目的状態01223 . . . 3までの最小深 さを比べる次の補題5.13を証明した。

a− 1→aが 1回多い b→ b + 1が 1回多い P0 a− 1 b 目的状態 必要深さ 少ない 多い P a b P a− 1 b + 1 01223 . . . 3 図22: 補題5.13のイメージ図 補題5.13 a, bを任意のa≤ bを満たす自然数、Pを任意のペブル状態とする。 この時、ペブル状態P + a + bとP + (a− 1) + (b + 1)がどちらも値が0のペブルを1個含んで いて、1以下のペブルを2個以上含んでいる状態ならば、次の式が成り立つ。 D(P + a + b, 012233 . . . 3)≤ D(P + (a − 1) + (b + 1), 012233 . . . 3) (36) 最小深さペブルプレイ戦略5.11をプレイした時の深さを数えることにより、補題5.12の系とし て、いくつかの状態から01223 . . . 3以上の状態までの最小深さが得られた。（証明略） 系5.14 kを任意の自然数とする。 この時、次の式が成り立つ。 D(01 + 22, 01223 . . . 3) = 0 (37) D(01 + 2· k, 01223 . . . 3) = 1 + D ( 01 + 2· ⌈ k 2 − 1 ⌉) (38) =⌈log₂(k + 2)⌉ − 2 (39) D ( 0 + 1· 2k+ 2· ( 2k ( 2k−1−1 2 )) , 01223 . . . 3 ) (40) = k + D ( 01 + 2· ( 2k−1− k − 2 ) , 01223 . . . 3 ) (41) = k + ⌈ log₂(2k−1− k) ⌉ − 2 (42) D(0· 22k, 01223 . . . 3) = 2k+ D ( 0 + 1· 2k+ 2· ( 2k ( 2k−1−1 2 )) , 01223 . . . 3 ) (43) = 2k+ k + ⌈ log₂(2k−1− k) ⌉ − 2 (44)

ペブルゲームの最小深さは入力数に比例するため、系5.14より補題5.12の系として、任意の 数の値が0のペブルのみからなる状態から、01223 . . . 3以上の状態までの最小深さの下界と上界 が得られた。（証明略） 系5.15 nを任意の自然数とする。 この時、n個の値が0のペブルのみからなる状態から01223 . . . 3以上の状態までの最小深さに ついて、次の式が成り立つ。 2⌊log2log2n⌋₊⌊log

2log2n⌋ + ⌈

log₂(2⌊log2log2n⌋−1− ⌊log

2log2n⌋) ⌉

− 2 (45)

≤ D(0 · n, 01223 . . . 3) (46)

≤ 2⌈log2log2n⌉₊⌈log

2log2n⌉ + ⌈

log₂(2⌈log2log2n⌉−1− ⌈log

2log2n⌉) ⌉

− 2 (47)

補題5.12とプログラムによる計算により、D(0· n, 01223 . . . 3)が0∼21になるkの上界と下界

深さD(0· n, 01223 . . . 3) 入力数n 下界 上界 0 1 1 1 2 2 3 3 4 4 5 6 5 7 8 6 9 12 7 13 20 8 21 32 9 33 52 10 53 96 11 97 152 12 153 256 13 257 440 14 441 736 15 737 1312 16 1313 2432 17 2433 4276 18 4277 7680 19 7681 13568 20 13569 24576 21 24577 45440 表4: D(0· n, 01223 . . . 3)ごとのnの上下界

5.4

V 型 2 セレクションネットワークに対応する修正ペブルゲーム

修正ペブルゲームとは「値が0のペブルがひとつだけとなったペブル状態では、値が0のペブ ルと他のペブルの比較を行わない」という制約を追加したペブルゲームである（定義2.15）。この 修正ペブルゲームの制約を満たしてペブル状態0122 . . . 22以上の状態にする、次の修正ペブルプ レイ戦略5.16が存在する。 ペブルプレイ戦略5.16 1. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さいペブ ルの値が2以上なら、比較を終了する。 2. そうでなく、値が2番目に小さいペブルの値が1以上ならば、下記の比較を同じ深さで行い 次の深さへ進む。 (a) 1同士の比較を可能な限り多く行う。 3. そうでないなら下記の比較を同じ深さで行い、次の深さへ進む。 (a) 0同士の比較を可能な限り多く行う。 (b) 上記の比較で0が余り、1が1個以上あるなら、0と1の比較を1回行う。 (c) 上記の比較に用いない1同士の比較を可能な限り多く行う。 0と0 0と0 0と0 を比較 0と0 0と0 1と1 を比較 0と0 1と1 1と1 を比較 1と1 を比較 1と1 を比較 初期状態 目標状態以上 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 2 0 1 1 1 2 2 2 0 1 1 2 2 2 2 0 1 2 2 2 2 2 図23: 目標状態が0122222の修正ペブルプレイ戦略5.16の例 この修正ペブルプレイ戦略は、値が0のペブルを含む任意の状態から、0122 . . . 22以上の状態 にする、最小深さの修正ペブルプレイ戦略である。 補題5.17 ペブルプレイ戦略5.16は、値が0のペブルを含む任意のペブル状態から、ペブル状態 0122 . . . 2以上の状態にする最小深さペブルプレイ戦略である。 補題5.17を証明するために、よく似た2つのペブル状態から目的状態0122 . . . 2までの最小深 さを比べる次の補題5.18を証明した。 補題5.18 a, bを任意のa≤ bを満たす自然数、Pを任意のペブル状態とする。

a− 1→aが 1回多い b→ b + 1が 1回多い P0 a− 1 b 目的状態 必要深さ 少ない 多い P a b P a− 1 b + 1 0122 . . . 2 図24: 補題5.18のイメージ図 この時、ペブル状態P + a + bとP + (a− 1) + (b + 1)がどちらも値が0のペブルを含んでいる 状態ならば、次の式が成り立つ。 DF(P + a + b, 0122 . . . 2)≤ DF(P + (a− 1) + (b + 1), 0122 . . . 2) (48) 最小深さ修正ペブルプレイ戦略5.16をプレイした時の深さを数えることにより、補題5.17の系 として、いくつかの状態から0122 . . . 2以上の状態までの修正ペブルプレイ戦略の最小深さが得 られた。（証明略） 系5.19 kを十分に大きい任意の自然数とする。 この時、次の式が成り立つ。 D(0 + 1, 0122 . . . 2) = 0 (49) D(0 + 1· k, 0122 . . . 2) = 1 + D ( 0 + 1· ⌈ k 2 ⌉ , 0122 . . . 2 ) (50) =⌈log₂k⌉ (51) D(0· 2k, 0122 . . . 2) = k + D(0 + 1· k, 0122 . . . 2) (52) = k +⌈log₂k⌉ (53) ペブルゲームの最小深さは入力数に比例するため、系5.19より補題5.17の系として、任意の 数の値が0のペブルのみからなる状態から、0122 . . . 2以上の状態までの修正ペブルプレイ戦略の 最小深さの下界と上界が得られた。（証明略） 系5.20 nを任意の自然数とする。 この時、n個の値が0のペブルのみからなる状態から0122 . . . 2以上の状態までの修正ペブルプ レイ戦略の最小深さについて、次の式が成り立つ。

6

証明の方針

本セクションでは、本研究で導かれた各命題をどのように証明するのか、その方針を示す。V 型2セレクションネットワーク・U型セレクションネットワーク・V 型4セレクションネットワー クの最小深さおよび、それぞれに対応するペブルゲームの最小深さペブルプレイ戦略の証明の方 針は、同じ構成になっている。そのため本セクションでは、V 型2セレクションネットワークに 対しての命題を例にとって説明を行う。

6.1

セレクションネットワークの最小深さに関する結果の証明の方針

本サブセクションの目的は、セレクションネットワークの最小深さのタイトな下界を求め、可 能ならば最小深さを決定することである。セレクションネットワークの最小深さのタイトな下界 を得るために、セレクションネットワーク上でペブルゲーム解析を行ったときのペブル状態の必 要条件を調べ、セレクションネットワークの最小深さはそのペブル状態にするための最小深さペ ブルプレイ戦略の深さ以上であること（補題4.1）を示す。さらにタイトな下界を得るために、セ レクションネットワークの最小深さはそのペブル状態にするための最小深さ修正ペブルプレイ戦 略の深さ以上であること（補題4.4）を示す。可能ならば最小深さを決定するために、最小深さペ ブルプレイ戦略の深さが計算しやすい入力数に着目し、その入力数でのセレクションネットワー クの最小深さの上界との差（補題4.5）を示す。 命題 4.1(抜粋) nを任意の自然数とする。 n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· nとして ペブルプレイ戦略5.1をプレイした時の深さ以上である。 V 型2セレクション ネットワークの 出力の最小値 min 1 min 2 min 3 min 3 min 3 ペブルゲームの 出力の最小値 ⌈log21⌉ =0 ⌈log22⌉ =1 ⌈log23⌉ = 2 ⌈log23⌉ = 2 ⌈log23⌉ = 2 図25: V 型2セレクションネットワークとペブルゲーム解析の関係 Alekseevの先行研究[1]の補題3.1により、V 型2セレクションネットワーク上でペブルゲーム 解析を行った時の出力は0, 1, 2, 2, . . . , 2となることが得られる（図25）。「ペブルゲームの最小深

さに関する結果」の補題5.2よりペブルプレイ戦略5.1は0122 . . . 2以上の状態になる最小深さペ ブルプレイ戦略であるため、補題4.1は示される。 命題 4.4(抜粋) nを任意の自然数とする。 この時、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· n として修正ペブルプレイ戦略5.16をプレイした時の深さ以上である。 Alekseevの先行研究[1]の補題3.1により、V 型2セレクションネットワーク上でペブルゲーム 解析を行った時に値が0のペブルはmin 1候補に対応していることがわかる。値が0のペブルが

1つだけの深さではmin 1が確定しており、min 1とmin 2をセレクションするためには既に確定

したmin 1を他の値と比較する必要がないことから、値が0のペブルが1つだけの深さではその ペブルを他のペブルと比較しない戦略、すなわち修正ペブルプレイ戦略が最小深さV 型2セレク ションネットワーク上でペブルゲーム解析を行ったときの戦略となる。「ペブルゲームの最小深さ に関する結果」の補題5.17より修正ペブルプレイ戦略5.16は0122 . . . 2以上の状態になる最小深 さ修正ペブルプレイ戦略であるため、補題4.4は示される。 命題 4.5(抜粋) kを任意の自然数とする。この時、2k入力V 型2セレクションネットワークの 最小深さについて、次の式が成り立つ。 V Depth(2, 2k) = k +⌈log₂k⌉ (55) 0と0 0と0 0と0 0と0 を比較 0と0 0と0 1と1 1と1 を比較 0と0 1と1 1と1 を比較 1と1 を比較 1と1 を比較 初期状態 目標状態以上 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 2 2 0 1 1 1 2 2 2 2 0 1 1 2 2 2 2 2 0 1 2 2 2 2 2 2 図26: 目標状態が01222222の最小深さ修正ペブルプレイ戦略5.16の例 2k入力V 型2セレクションネットワークの最小深さの下界については、ペブルプレイ戦略5.16 の各深さでのペブル状態を追っていくことで求まる。値が0のペブルの数（以降は0の数）が2 以上の深さでは、深さが1増える度に0,1の数が半分になり、減った0の数だけ1の数が増加す る。0の数が1になってからは、深さが1増える度に1の数が半分（端数切り上げ）になる。これ により、補題4.5の下界が求まる。 2k入力V 型2セレクションネットワークの最小深さの上界についても、下界の時と同じように

2セレクションネットワークの各深さでのmin 1候補と非min 1候補だがmin 2候補の数を追って

出力の最小値 min 1 min 2 min 3 min 3 min 3 min 3 min 3 min 3 図27: 8入力V 型2セレクションネットワークの例 うセレクションネットワークを考えた場合、min 1候補の数が2以上の深さでは、深さが1増える

度にmin 1候補・min 2候補の数が半分になり、減ったmin 1候補の数だけmin 2候補の数が増加 する。min 1候補の数が1になってからは、深さが1増える度にmin 2候補の数が半分（端数切り

6.2

ペブルゲームの最小深さに関する結果の証明の方針

本サブセクションの目的は、セレクションネットワークに対応するペブルゲームの最小深さを 決定することである。最小深さを求めるためにはペブルプレイ戦略（ペブルプレイ戦略5.1）を1 つ決めて、それより深さが小さいペブルプレイ戦略が無いこと（補題5.2）を示せば良い。そのた めの手段として、よく似た2つのペブルプレイ戦略の深さに大小関係が成り立つこと（補題5.3） を示す。 補題 5.3(抜粋) a, bを任意のa≤ bを満たす自然数、Pを任意のペブル状態とする。 この時、ペブル状態P + a + bとP + (a− 1) + (b + 1)がどちらも値が0のペブルを含んでいる 状態ならば、次の式が成り立つ。 D(P + a + b, 0122 . . . 2)≤ D(P + (a − 1) + (b + 1), 0122 . . . 2) (56) a− 1→aが 1回多い b→ b + 1が 1回多い P0 a− 1 b 目的状態 必要深さ 少ない 多い P a b P a− 1 b + 1 0122 . . . 2 図28: 補題5.3のイメージ図 補題5.3の目的は、「小さい値を1大きくする比較と大きい値を1大きくする比較のうち、前者 を優先するペブルプレイ戦略の方が目的状態に達するまでの必要深さが小さくなる」ということ を示すことである。大きい値を1大きくした後のペブル状態P + (a− 1) + (b + 1)を0122 . . . 22 にする任意のペブルプレイ戦略Sに対して、小さい値を1大きくした後のペブル状態P + a + b を0122 . . . 22にする同じ深さのペブルプレイ戦略が存在することを示して証明される。 Sの内a− 1, b + 1のペブルを使う比較でa, bを代わりに使うペブルプレイ戦略をS′と置くと、 S, S′のプレイ中にa, bの大小関係が逆転しないあいだは、SによるP + (a− 1) + (b + 1)のペブ ルの値の変化とS′によるP + a + bのペブルの値の変化は同じように起こる。そのためa, bの大 小関係が最後まで逆転しないならば、P + (a− 1) + (b + 1)がSによって目的状態に達するのと 同様に、P + a + bはS′によって目的状態に達する。S, S′のプレイ中にa, bの大小関係が逆転す る場合、P + (a− 1) + (b + 1)とP + a + bはa, bの大小関係が逆転する深さで全く同じペブル状 態になる。P + a + bがP + (a− 1) + (b + 1)と同じ状態になるまでS′の比較を行い、同じ状態 になって以降Sの比較を行うことで、P + a + bは目的状態に達する。 これにより、P + (a− 1) + (b + 1)を0122 . . . 22にする任意のペブルプレイ戦略Sに対して、 P + a + bを0122 . . . 22にする同じ深さのペブルプレイ戦略が存在することが示されるため、補 題5.3は証明される。

ペブルプレイ戦略 5.1(抜粋) 1. 値が2番目に小さいペブルの値が1以上かつ、3番目に小さ いペブルの値が2以上なら、比較を終了する。 2. そうでないなら下記の比較を同じ深さで行い、次の深さへ進む。 (a) 0同士の比較を可能な限り多く行う。 (b) 上記の比較で0が余り、1が1個以上あるなら、0と1の比較を1回行う。 (c) 上記の比較に用いない1同士の比較を可能な限り多く行う。 補題 5.2(抜粋) ペブルプレイ戦略5.1は、値が0のペブルを含む任意のペブル状態から、ペブル 状態0122 . . . 2以上の状態にする最小深さペブルプレイ戦略である。 0→1が 最も多い 0→1が 1回多い 1→2が 1回多い P0 0 1 目的状態 必要深さ 最小 少ない 多い P 1 1 P 0 2 0が一番 少ない 0122 . . . 2 図29: 補題5.2の証明のイメージ図 補題5.2の目的は「ペブルプレイ戦略5.1が最小深さペブルプレイ戦略であり、この戦略より深 さが小さい戦略は無い」ということを示すことである。ペブルプレイ戦略5.1は0を1にする比 較を常に最優先する戦略であることから、補題5.3を使って簡単に証明できる。

7

証明

本セクションでは、本研究で導かれた各命題の証明を行う。

7.1

セレクションネットワークの最小深さに関する結果の証明

命題 4.1(抜粋) nを任意の自然数とする。 n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· nとして ペブルプレイ戦略5.1をプレイした時の深さ以上である。 4.1の証明 補題3.1より、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、 ペブル状態0· nから0122 . . . 2になるペブル戦略の最小深さD(0· n, 0122 . . . 2)以上である。補 題5.2より、D(0· n, 0122 . . . 2)は、0がn個あるペブル状態を初期状態としてペブルプレイ戦略 5.1をプレイした際の深さに等しい。よってn入力V 型2セレクションネットワークの最小深さ V Depth(2, n)は、初期状態を0· nとしたときのペブルプレイ戦略5.1の深さ以上である。 V 型2セレクション ネットワークの 出力の最小値 min 1 min 2 min 3 min 3 min 3 min 3 min 3 ペブルゲームの 出力の最小値 ⌈log21⌉ = 0 ⌈log22⌉ = 1 ⌈log23⌉ = 2 ⌈log23⌉ = 2 ⌈log23⌉ = 2 ⌈log23⌉ = 2 ⌈log23⌉ = 2 図30: V 型2セレクションネットワークのペブルゲーム解析の出力下界

命題 4.2(抜粋) n, mを任意の自然数とする。 n入力U型2mセレクションネットワークの最小深さU Depth(2m, n)は、初期状態を0· nかつ 自然数µ, νをµ = 2m, ν = m + 1としてペブルプレイ戦略5.6をプレイした時の深さ以上である。 4.2の証明 補題3.1より、n入力U型2mセレクションネットワークの最小深さU Depth(2m, n) は、ペブル状態0· nから0· 2m + (m + 1) . . . (m + 1)になるペブル戦略の最小深さD(0· n, 0 · 2m+ (m + 1) . . . (m + 1))以上である。補題5.7より、D(0· n, 0 · 2m+ (m + 1) . . . (m + 1))は、0 がn個あるペブル状態を初期状態自然数µ, νをµ = 2m, ν = m + 1としたときの、ペブルプレイ 戦略5.6をプレイした際の深さに等しい。よってn入力U 型2mセレクションネットワークの最 小深さU Depth(2m, n)は、初期状態を0· nとして自然数µ, νをµ = 2m, ν = m + 1としたとき の、ペブルプレイ戦略5.6の深さ以上である。 U 型2mセレクション ネットワークの 出力の最小値 min 1 min 1 min 1 min 2m+ 1 min 2m+ 1 min 2m+ 1 ペブルゲームの 出力の最小値 ⌈log21⌉ = 0 ⌈log21⌉ = 0 ⌈log21⌉ = 0 ⌈log22m+ 1⌉ = m + 1 ⌈log22m+ 1⌉ = m + 1 ⌈log22m+ 1⌉ = m + 1 図31: U 型2m_{セレクションネットワークのペブルゲーム解析の出力下界}

命題 4.3(抜粋) nを任意の自然数とする。 n入力V 型4セレクションネットワークの最小深さV Depth(4, n)は、初期状態を0· nとして ペブルプレイ戦略5.11をプレイした時の深さ以上である。 4.3の証明 補題3.1より、n入力V 型4セレクションネットワークの最小深さV Depth(4, n)は、 ペブル状態0· nから012233 . . . 3になるペブル戦略の最小深さD(0· n, 012233 . . . 3)以上である。 補題5.12より、D(0· n, 012233 . . . 3)は、0がn個あるペブル状態を初期状態としてペブルプレイ 戦略5.11をプレイした際の深さに等しい。よってn入力V 型4セレクションネットワークの最小 深さV Depth(4, n)は、初期状態を0· nとしたときのペブルプレイ戦略5.11の深さ以上である。 V 型4セレクション ネットワークの 出力の最小値 min 1 min 2 min 3 min 4 min 5 min 5 min 5 ペブルゲームの 出力の最小値 ⌈log21⌉ = 0 ⌈log22⌉ = 1 ⌈log23⌉ = 2 ⌈log24⌉ = 2 ⌈log25⌉ = 3 ⌈log25⌉ = 3 ⌈log25⌉ = 3 図32: V 型4セレクションネットワークのペブルゲーム解析の出力下界

命題 4.4(抜粋) nを任意の自然数とする。 この時、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、初期状態を0· n として修正ペブルプレイ戦略5.16をプレイした時の深さ以上である。 4.4の証明 補題3.1より、V 型2セレクションネットワーク上でペブルゲーム解析を行った時に 値が0のペブルは、比較ネットワークの出力の最小値がmin 1である値に対応するペブルである。 従って値が0のペブルが1つだけの深さは、比較ネットワークの出力の最小値がmin 1である値

が1つだけである深さ、すなわちmin 1が確定している深さである。min 1とmin 2をセレクショ

ンするためには既に確定したmin 1を他の値と比較する必要がないことから、任意の入力数nに 対して、min 1が確定している深さで他の値と確定したmin 1を比較しない最小深さn入力V 型 2セレクションネットワークが存在する。 この最小深さV 型2セレクションネットワーク上でペブルゲーム解析を行った時、出力の最小 値がmin 1である値に対応するペブルは値が0であることから、値が0のペブルが1つだけの深 さでは、値が0のペブルと他の比較は行われない。この戦略が修正ペブルプレイ戦略の条件を満 たしていることから、n入力V 型2セレクションネットワークの最小深さV Depth(2, n)は、ペ ブル状態0· nから0122 . . . 2になる修正ペブル戦略の最小深さDF(0· n, 0122 . . . 2)以上である。 補題5.17より、DF(0· n, 0122 . . . 2)は、0がn個あるペブル状態を初期状態として修正ペブル プレイ戦略5.16をプレイした際の深さに等しい。よってn入力V 型2セレクションネットワーク の最小深さV Depth(2, n)は、初期状態を0· nとして修正ペブルプレイ戦略5.16をプレイした時 の深さ以上である。

命題 4.5(抜粋) kを任意の自然数とする。この時、2k入力V 型2セレクションネットワークの 最小深さについて、次の式が成り立つ。 V Depth(2, 2k) = k +⌈log₂k⌉ (57) 4.5の証明 kを任意の自然数とする。2k_{入力V 型2セレクションネットワークの最小深さについ} て、次の式が成り立つことを証明する。 V Depth(2, 2k) = k +⌈log₂k⌉ (58) • V Depth(2, 2k_{)≥ k + ⌈log} 2k⌉について 補題4.4と系5.20より、V Depth(2, 2k)≥ k + ⌈log₂k⌉が成り立つ。 • V Depth(2, 2k_{)≤ k + ⌈log} 2k⌉について 任意の自然数kに対し、ある1つのワイヤーにmin 1を出力しk個のワイヤーのいずれかに min 2を出力する、深さkの2k入力比較ネットワークが次の手順により構築できる。 1. 1度も負けていないワイヤーが1つだけになるまで、各深さで次の比較を行う。 (a) min 1が含まれるかもしれない、1度も負けていないワイヤー同士の比較を可能な 限り多く行う。 (b) min 1は含まれないがmin 2が含まれるかもしれない、ちょうど1度だけ負けたワ イヤー同士の比較を可能な限り多く行う。 2. 唯一残った1度も負けていないワイヤーに出力されるのがmin 1であり、k個残った ちょうど1度だけ負けたワイヤーのいずれかに出力されるのがmin 2である。 また任意の自然数kに対し、ある1つのワイヤーにmin 1を出力する深さ⌈log₂k⌉のk入力 1セレクションネットワークが次の手順により構築できる。 1. 1度も負けていないワイヤーが1つだけになるまで、各深さで次の比較を行う。 (a) min 1が含まれるかもしれない、1度も負けていないワイヤー同士の比較を可能な 限り多く行う。 2. 唯一残った1度も負けていないワイヤーに出力されるのがmin 1である。 したがって任意の自然数kに対し、図33のような深さk +⌈log₂k⌉ − 1の2k入力V 型2セ レクションネットワークが次の手順により構築できる。 1. 深さkの2k入力比較ネットワークをつなげて、ただ1つのmin 1とk個のmin 2候補 を絞る。 2. 深さ⌈log₂k⌉のk入力1セレクションネットワークを使い、k個のmin 2候補の中で最 も小さい値を絞る。 したがってV Depth(2, 2k)≤ k + ⌈log₂k⌉が成り立つ。 上記により、次の式が成り立つ。