最適時間一般化一斉射撃アルゴリズムについて

The 18th Annual Conference of the Japanese Society for Artificial Intelligence, 2004

3H1-04

2 次元セルラーオートマトン上での

最適時間一般化一斉射撃アルゴリズムについて

A Design of Generalized Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Cellular Arrays

寺岡 正人 ^{∗ 1}

Masato Teraok

久岡 雅也 ^{∗ 1}

Masaya Hisaoka

前田 雅史 ^{∗ 2}

Masashi Maeda

梅尾 博司 ^{∗ 1}

Hiroshi Umeo

∗ 1 大阪電気通信大学大学院 工学研究科 情報工学専攻

Osaka Electro-Communication Univ., Graduate School of Engineering

∗ 2 （株）大真空

Daishinku, Inc.

In recent years cellular automata (CA) have been establishing increasing interests in the study of modeling real phenomena occurring in biology, chemistry, ecology, economy, geology, mechanical engineering, medicine, physics, sociology, public traffic, etc. Cellular automata are considered to be a nice model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in synchronous manner according to a uniform local rule. The synchronization in cellular automata has been known as firing squad synchronization problem since its development, in which it was originally proposed by J. Myhill to synchronize all parts of self- reproducing cellular automata [9]. The firing squad synchronization problem has been studied extensively for more than 40 years [1-20]. The present authors are involved in research on firing squad synchronization algorithms on two-dimensional (2-D) cellular arrays. In this paper, we propose a new optimum-time generalized synchronization scheme that can synchronize any m ×n array in m + n+max(m, n)−min(r, m −r + 1)−min(s,n− s + 1)−1 optimum steps, where ( r, s ) is the general’s initial position.

1. はじめに

1957

年

, Myhill

によりセルラーオートマトン上での同期問題 として一斉射撃問題

(Firing Squad Synchronization Problem, FSSP

と略す

)

が提唱された

.

セル間の局所通信のみでセル空間 全域を同期に導く問題が研究者の興味を引き

,

これまでに多く の研究がなされている

[1-20]. 2

次元セルラーオートマトン上 では

,

代表的な一般化一斉射撃アルゴリズムとして

, Szwerinski [14]

による最適時間で動作するアルゴリズムが知られている が

,

それを実現するためにセルラーオートマトンの内部状態が

25600

と非常に大きい

.

本稿では

, Szwerinski [14]

とは異なっ た制御手法を用いた同期アルゴリズムを提案する

.

2. 2 次元セルラーオートマトン上での一斉射 撃問題

2.1

セルラーオートマトン

2

次元セルラーオートマトンとは

2

次元格子状にセルと呼ば れる有限オートマトンを配置したものであり

,

図

1

のように

m

行

n

列に位置するセルを

C _mn

と表記する

.

また

,

各セルは有 限の内部状態と隣接する上下左右のセルとの間に通信経路を持 つ

.

セルは自分の内部状態と隣接するセルの内部状態を基に遷 移規則集合を参照し自分自身の内部状態を変化させる

.

全セル は同時に状態遷移を行い

, 1

度の状態遷移に必要な時間を

1

ス テップと呼ぶ

.

2.2

一般化一斉射撃問題

一斉射撃問題とはセルラーオートマトンでの同期問題であ る

.

局所的な通信のみを利用してセル空間全体の同期をとるこ とが目的である

.

時刻

t =0

において将軍状態と呼ばれるセル を

1

つ配置する

.

このセルから同期を取るための信号を周りの セルへ伝達していき

,

未来の時刻

t = α

^{に全セルが同じ状態へ} と遷移するように遷移規則を作成することである

.

初期状態で 将軍より伝達させる信号が到達するまで各セルは静止状態と

1 1

2 3 n

2

3

m

4

図

1: 2

次元セルラーオートマトン

いう状態となり

,

最終的に同期が完了したときになる状態を射 撃状態と呼ぶ

.

この射撃状態は同期完了のとき

1

度だけ遷移す る状態であり

,

それまでに射撃状態に遷移してはならない

.

通 常

,

一斉射撃問題は将軍状態のセルを左上の端に配置し遷移規 則を作成していくものだが

,

将軍を配置する位置をセル空間の 任意の位置に変更できるようにすることを一般化一斉射撃問題 と呼び

,

そのためのアルゴリズムを一般化一斉射撃アルゴリズ ムと呼ぶ

.

2.3

最適時間一斉射撃アルゴリズム

一斉射撃アルゴリズムにおいて同期完了までに必要な時間 はアルゴリズムによって異なる

.

将軍状態のセルがセル空間の 全セルの状態を把握するのに必要な時間が同期に必要な最低限 の時間となる

.

この時間を最適時間と呼び

,

これよりも早い時 間ではセル空間を同期に導くことはできない

.

サイズ

m × n

のセル空間において将軍を左上に配置した場合の最適動作時 間は

, t = m + n + max(m, n) − 3

となる

.

将軍を任意の位置

(r, s)

^{に配置した場合}

,

一般化一斉射撃アルゴリズムの最適動

作時間

:T (m, n, r, s)

^は

, T (m, n, r, s) = m + n + max(m, n) −

1

The 18th Annual Conference of the Japanese Society for Artificial Intelligence, 2004 min( r, m − r + 1) − min( s, n − s + 1) − 1

となる

.

ここで

r, s

はそれぞれ

, 1 ≤ r ≤ m , 1 ≤ s ≤ n

となる任意の整数である

.

3. 最適時間一般化一斉射撃アルゴリズム

本節では

,

新しい制御手法に基づく最適時間で動作する

2

次元 一般化一斉射撃アルゴリズムを示す

. 2

次元一般化一斉射撃アル ゴリズムについては

, Szwerinski [14]

が

m + n + max( m, n ) − min(r, m − r + 1) − min(s, n − s + 1) −1

ステップで動作する アルゴリズムを示し

,

これが最適なものであることを示してい る

.

ここで

2

次元アレイのサイズを

m × n

とし

, t = 0

時にお ける将軍の位置を

(r, s)

とする

.

但し

, 1 ≤ r ≤ m, 1 ≤ s ≤ n

である

.

 新しく提案するアルゴリズムは

,

サイズ

m × n

の

2

次元アレ イを

m

個の長さ

n

の

1

次元アレイ及び

, n

個の長さ

m

の

1

次 元アレイから構成されると考え

,

それぞれの行及び列上で従来 から知られている

1

次元一般化一斉射撃アルゴリズムを利用す るものである

. 1

次元一般化一斉射撃アルゴリズムについては

, Moore and Langdon [10], Settle and Simon [12], Szwerinski [14], Umeo, Hisaoka, Michisaka, Nishioka and Maeda [17],

Varshavsky [18]

らにより次のようなことが明らかにされて

いる

.

t=0

n

t=t

1

t=t

2

1 2

t 1/1

1/1

t=t

0

+(t

2

-t

1

)/2 +2n-2 t=t

0

1/1

t=0 n

t=t

1

t=t

2

1 2

t s

1/1 t=t

0

t=max(s, n-s+1)

t=t

0

+n-2+(t

2

-t

1

)/2 +max(s, n-s+1) 1/1

1/1

1/1

(a) (b)

図

2:

時間空間図式

[

定理

1] [10,12,14,17,18] N

^を任意の

1

次元最適時間一斉射撃アル ゴリズムを実行するセルラーオートマトンとする

. t = 0

時 にセル

C _s

に将軍を配置したとき

, N

は

T (s, n) = n − 2 + max(s, n − s + 1)

ステップで

n

個のセルからなるセル空間を 同期に導く

.

またこの時間計算量

T (s, n)

は最適である

.

次の

[

補題

2, 3]

は有用である

.

[

補題

2]A

を任意のセルラーオートマトンとする

. t 1 , t 2 , l

を 次の条件を満足する正整数とする

.

∆ t = t 2 − t 1 = 2 l, l ≥ 1 , t 2 ≥ t 1 ≥ 0 . (1)

時刻

t = t 1 , t 2

において

C ₁

に特別な信号を与えることによ り

, A

^{の動作を漸近的に}

l

^{ステップ遅延させ}

, A

^{の計算状況を}

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

S

¹0

S

¹1

S

¹2

S

¹3

S

¹4

S

¹5

S

¹6

S

¹7

S

¹8

S

¹9

S

¹10

S

¹11

S

¹12

S

¹13

S

¹14

S

²0

S

²1

S

²2

S

²3

S

²4

S

²5

S

²6

S

²7

S

²8

S

²9

S

²10

S

²11

S

²12

S

²13

S

²14

S

³0

S

³1

S

³2

S

³3

S

³4

S

³5

S

³6

S

³7

S

³8

S

³9

S

³10

S

³11

S

³12

S

³13

S

³14

S

⁴₀

S

⁴₁

S

⁴₂

S

⁴₃

S

⁴₄

S

⁴₅

S

⁴₆

S

⁴₇

S

⁴₈

S

⁴₉

S

⁴₁₀

S

⁴₁₁

S

⁴₁₂

S

⁴₁₃

S

⁴₁₄

S

⁴₀

S

⁵₁

S

⁵₂

S

⁵₃

S

⁵₄

S

⁵₅

S

⁵₆

S

⁵₇

S

⁵₈

S

⁵₉

S

⁵₁₀

S

⁵₁₁

S

⁵₁₂

S

⁵₁₃

S

⁵₁₄

S

⁵0

S

⁵1

S

⁶2

S

⁶3

S

⁶4

S

⁶5

S

⁶6

S

⁶7

S

⁶8

S

⁶9

S

⁶10

S

⁶11

S

⁶12

S

⁶13

S

⁶14

S

⁵0

S

⁶1

S

⁶2

S

⁷3

S

⁷4

S

⁷5

S

⁷6

S

⁷7

S

⁷8

S

⁷9

S

⁷10

S

⁷11

S

⁷12

S

⁷13

S

⁷14

S

⁶0

S

⁶1

S

⁷2

S

⁷3

S

⁸4

S

⁸5

S

⁸6

S

⁸7

S

⁸8

S

⁸9

S

⁸10

S

⁸11

S

⁸12

S

⁸13

S

⁸14

S

⁶0

S

⁷1

S

⁷2

S

⁸3

S

⁸4

S

⁹5

S

⁹6

S

⁹7

S

⁹8

S

⁹9

S

⁹10

S

⁹11

S

⁹12

S

⁹13

S

⁹14

S

⁷₀

S

⁷₁

S

⁸₂

S

⁸₃

S

⁹₄

S

⁹₅

S

¹⁰₆

S

¹⁰₇

S

¹⁰₈

S

¹⁰₉

S

¹⁰₁₀

S

¹⁰₁₁

S

¹⁰₁₂

S

¹⁰₁₃

S

¹⁰₁₄

S

⁷0

S

⁸1

S

⁸2

S

⁹3

S

⁹4

S

¹⁰5

S

¹⁰6

S

¹¹7

S

¹¹8

S

¹¹9

S

¹¹10

S

¹¹11

S

¹¹12

S

¹¹13

S

¹¹14

S

⁸0

S

⁸1

S

⁹2

S

⁹3

S

¹⁰4

S

¹⁰5

S

¹¹6

S

¹¹7

S

¹²8

S

¹²9

S

¹²10

S

¹²11

S

¹²12

S

¹²13

S

¹²14

S

⁹0

S

⁹1

S

⁹2

S

¹⁰3

S

¹⁰4

S

¹¹5

S

¹¹6

S

¹²7

S

¹²8

S

¹³9

S

¹³10

S

¹³11

S

¹³12

S

¹³13

S

¹³14

S

¹⁰0

S

¹⁰1

S

¹⁰2

S

¹⁰3

S

¹¹4

S

¹¹5

S

¹²6

S

¹²7

S

¹³8

S

¹³9

S

¹⁴10

S

¹⁴11

S

¹⁴12

S

¹⁴13

S

¹⁴14

S

¹¹₀

S

¹¹₁

S

¹¹₂

S

¹⁰₃

S

¹¹₄

S

¹²₅

S

¹²₆

S

¹³₇

S

¹³₈

S

¹⁴₉

S

¹⁴₁₀

S

¹⁵₁₁

S

¹⁵₁₂

S

¹⁵₁₃

S

¹⁵₁₄

S

¹¹0

S

¹¹1

S

¹¹2

S

¹¹3

S

¹¹4

S

¹²5

S

¹³6

S

¹³7

S

¹⁴8

S

¹⁴9

S

¹⁵10

S

¹⁵11

S

¹⁶12

S

¹⁶13

S

¹⁶14

S

¹²0

S

¹²1

S

¹²2

S

¹²3

S

¹²4

S

¹²5

S

¹³6

S

¹⁴7

S

¹⁴8

S

¹⁵9

S

¹⁵10

S

¹⁶11

S

¹⁶12

S

¹⁷13

S

¹⁷14

C

0

C

1

C

2

C

3

C

4

C

5

C

6

C

7

C

8

C

9

C

10

C

11

C

12

C

13

C

14 t = 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

S

¹³0

S

¹³1

S

¹³2

S

¹³3

S

¹³4

S

¹³5

S

¹³6

S

¹⁴7

S

¹⁵8

S

¹⁵9

S

¹⁶10

S

¹⁶11

S

¹⁷12

S

¹⁷13

S

¹⁸14

23

S

¹⁴0

S

¹⁴1

S

¹⁴2

S

¹⁴3

S

¹⁴4

S

¹⁴5

S

¹⁴6

S

¹⁴7

S

¹⁵8

S

¹⁶9

S

¹⁶10

S

¹⁷11

S

¹⁷12

S

¹⁸13

S

¹⁸14

24

S

¹⁵0

S

¹⁵1

S

¹⁵2

S

¹⁵3

S

¹⁵4

S

¹⁵5

S

¹⁵6

S

¹⁵7

S

¹⁵8

S

¹⁶9

S

¹⁷10

S

¹⁷11

S

¹⁸12

S

¹⁸13

S

¹⁹14

25

S

¹⁶0

S

¹⁶1

S

¹⁶2

S

¹⁶3

S

¹⁶4

S

¹⁶5

S

¹⁶6

S

¹⁶7

S

¹⁶8

S

¹⁶9

S

¹⁷10

S

¹⁸11

S

¹⁸12

S

¹⁹13

S

¹⁹14

26

S

¹⁷0

S

¹⁷1

S

¹⁷2

S

¹⁷3

S

¹⁷4

S

¹⁷5

S

¹⁷6

S

¹⁷7

S

¹⁷8

S

¹⁷9

S

¹⁷10

S

¹⁸11

S

¹⁹12

S

¹⁹13

S

²⁰14

27

S

¹⁸0

S

¹⁸1

S

¹⁸2

S

¹⁸3

S

¹⁸4

S

¹⁸5

S

¹⁸6

S

¹⁸7

S

¹⁸8

S

¹⁸9

S

¹⁸10

S

¹⁸11

S

¹⁹12

S

²⁰13

S

²⁰14

28

S

¹⁹0

S

¹⁹1

S

¹⁹2

S

¹⁹3

S

¹⁹4

S

¹⁹5

S

¹⁹6

S

¹⁹7

S

¹⁹8

S

¹⁹9

S

¹⁹10

S

¹⁹11

S

¹⁹12

S

²⁰13

S

²¹14

28 30

S

²⁰0

S

²⁰1

S

²⁰2

S

²⁰3

S

²⁰4

S

²⁰5

S

²⁰6

S

²⁰7

S

²⁰8

S

²⁰9

S

²⁰10

S

²⁰11

S

²⁰12

S

²⁰13

S

²¹14

S

²⁵0

S

1²⁵

S

2²⁵

S

3²⁵

S

4²⁵

S

5²⁵

S

²⁵6

S

²⁵7

S

²⁵8

S

²⁵9

S

²⁵10

S

²⁵11

S

²⁵12

S

²⁵13

S

²⁵14

S

²⁶0

S

²⁶1

S

2²⁶

S

²⁶3

S

²⁶4

S

²⁶5

S

²⁶6

S

²⁶7

S

²⁶8

S

²⁶9

S

²⁶10

S

²⁶11

S

²⁶12

S

²⁶13

S

²⁶14

S

²²0

S

²²1

S

²²2

S

²²3

S

²²4

S

²²5

S

²²6

S

²²7

S

²²8

S

²²9

S

²²10

S

²²11

S

²²12

S

²²13

S

²²14

S

²³0

S

²³1

S

²³2

S

²³3

S

²³4

S

²³5

S

²³6

S

²³7

S

²³8

S

²³9

S

²³10

S

²³11

S

²³12

S

²³13

S

²³14

S

²⁴0

S

1²⁴

S

2²⁴

S

3²⁴

S

4²⁴

S

5²⁴

S

²⁴6

S

²⁴7

S

²⁴8

S

²⁴9

S

²⁴10

S

²⁴11

S

²⁴12

S

²⁴13

S

²⁴14

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

31 32

図

3: A

空間状態遷移図

生成するセルラーオートマトン

A

が存在する

. A

の内部状態 数を

k

とすると

, A

の内部状態数は

O(k ² )

となる

.

さらに

A

を時間計算量

T (n)

ステップで動作する一斉射撃アルゴリズム を実行するセルラーオートマトンと仮定する

. A

^は時刻

t = t 0

に

C ₁

に将軍状態を生成するものとする

. t 0 , t 1 , t 2 , l

^を

∆t = t 2 − t 1 = 2l,

 

l ≥ 1,

 

t 2 ≥ t 1 ≥ t 0 ≥ 0 (2) t 1 + t 2 − 2t 0 ≤ 2T (n) − 2(n − 1) (3)

を満足する正整数とする

.

このとき

A

は時刻

t = t 0 + l +T (n)

時に一斉射撃する

. T (n)

が最適時間計算量である時

,

すなわち

,

T(n) = 2n − 2

の時

,

条件

(3)

は

t 1 + t 2 − 2t 0 ≤ 2(n − 1) (4)

となる

.

一斉射撃は

t = t 0 + l + 2 n − 2

ステップ時に起こる

.

時刻

t = t 1 , t 2

において

C ₁

に与えられた信号は

,

セル空間を

1/1

のスピードで右方向に伝わり

,

各セルは

2

つの信号が伝わ る

2 l

^{ステップの間}

, 2

ステップに

1

回の割合で状態遷移を繰り 返す

.

したがってこの間の動作速度は

1/2

になる

.

このような 動作を実現するために各セルはこの間

1

ステップ前の状態も 同時に保持しておく必要があり

,

そのため内部状態数は

O(k ² )

となる

.

時刻

t = t 1 + 1

より

t = t 2 + n

までのセル空間上の 計算状況において

,

一部のセルの状態変化に時間的な

”

ずれ

”

が 生じていることに注意する必要がある

.

図

2(a)

は

, A

^の動作 を示した時間空間図式で

,

灰色の領域では動作速度が

1/2

とな り

,

一斉射撃に至る時間が全体で

l

ステップ遅延される様子を

2

The 18th Annual Conference of the Japanese Society for Artificial Intelligence, 2004

示している

.

図

3

は

n = 14 , t 0 = 2 , t 1 = 6 , t 2 = 14

の場合に

おける

A

^{の計算状況である}

.

[

補題

2]

は次のように一般化できる

.

[

補題

3]A

を任意のセルラーオートマトンとする

. t 1 , t 2 , l

を次 の条件を満足する正整数とする

.

∆ t = t 2 − t 1 = 2 l, l ≥ 1 , t 2 ≥ t 1 ≥ 0 (5)

時刻

t = t 1 , t 2

においてセル

C _s , 1 ≤ s ≤ n

^{に特殊な状態を} セットすることにより

, A

^{の動作を漸近的に}

l

^{ステップ遅延さ} せ

,

その計算状況を生成するセルラーオートマトン

A

^が存在 する

. A

^{の内部状態数を}

k

^とすると

, A

^{の内部状態数は}

O( k ² )

である

.

 次に

A

^{を時間計算量}

T ( s, n )

ステップで動作する一般化一 斉射撃アルゴリズムを実行するセルラーオートマトンとする

. A

は時刻

t = t 0

に

C _s

に将軍状態をセットすると仮定する

.

また時刻

t = t 1 , t 2

時に先に説明した信号を

C _s

に与えるもの とする

.

但し

, t 0 , t 1 , t 2 , l

は次の条件を満足するものとする

.

∆t = t 2 − t 1 = 2l, t 2 ≥ t 1 ≥ t 0 ≥ t, l ≥ 1, (6) t 1 + t 2 − 2t 0 ≤ 2T (s, n) − 2 + max(s, n − s + 1) + 2. (7)

このとき

A

^は時刻

t = t 0 + l + T (s, n)

^{時に一斉射撃する}

.

時間計算量

T (s, n)

^{が最適時間である場合}

,

^すなわち

T (s, n) = n − 2 + max( s, n − s + 1)

となる時

,

上式

(7)

は

t 1 + t 2 − 2 t 0 ≤ 2( n − 1) (8)

となり

,

一斉射撃は時刻

t = t 0 + l + n− 2+max( s, n−s +1)

に生起する

.

図

2(b)

に

A

の動作を示し

,

図

4

に

n = 14, s = 6, t 0 = 2, t 1 = 6, t 2 = 14

の場合における状態変化の様子を示す

. [

補題

3]

は 次に示す

2

次元アレイの各行及び

,

各列方向での一斉射撃に利 用される

.

サイズ

m × n

の

2

次元セルアレイ

M

を考える

.

一般性 を失うことなく

,

以下では次のことを仮定する

. (1)m ≤ n, (2)1 ≤ r ≤ ^m ₂ , 1 ≤ s ≤ ⁿ ₂ .

ここで

, (r, s)

は

t = 0

時における

M

の将軍位置である

. M

は 自身のサイズ

m × n

の

2

次元アレイを

m

個の長さ

n

の

1

次 元アレイから構成されると考え

,

それぞれの行上で

1

次元最適 時間一般化一斉射撃アルゴリズムを実行する

.

各行上での一斉 射撃を同時に行うために

, [

補題

2]

に示した遅延技法を用いる

. t = 0

時にセル

C _r,s

は

s

列上を上方向並びに下方向にスピー ド

1/1

で伝わる信号を生成する

.

この信号は

s

^列上を

C _1,s

及 び

C _m,s

をめざして

s

^{列上を進み}

, C _1,s , C _m,s

に到達すると直 ちに反射し

,

同じ

s

^列上を

C _r,s

に向かって

1/1

で進む

.

先に

C _r,s

に到着した信号は

,

再度そこで反射する

.

後ほど

C _r,s

に 到着した信号は

,

その事実を

C _r,s

で知り

, C _r,s

で停止せず同 じスピードで進み続ける

.

両信号とも

C _1,s

あるいは

, C _m,s

で 停止する

.

同時に

C _r,s

上で出会った場合は

, C _r,s

で停止する

.

図

5

は

,1 ≤ r ≤ ^m ₂

の場合に

,

上記の信号が伝わる様子を示 した時間空間図式である

.

例えば

,

第

y(r ≤ y ≤ m)

上では

, t 0 = t 1 = y −t 2 = 2m − y− r − 4

時に

C ys

に信号が与えられ

, y

行上での一斉射撃がこれらの信号により全体として

, y − m

ステップ遅延される様子を示している

.

第

x (1 < x < r )

行で は

, 2

回の遅延動作が行われることが図

5

より明らかである

.

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

S

¹0

S

¹1

S

¹2

S

¹3

S

¹4

S

¹5

S

¹6

S

¹7

S

¹8

S

¹9

S

¹10

S

¹11

S

¹12

S

¹13

S

¹14

S

²0

S

²1

S

²2

S

²3

S

²4

S

²5

S

²6

S

²7

S

²8

S

²9

S

²10

S

²11

S

²12

S

²13

S

²14

S

³0

S

³1

S

³2

S

³3

S

³4

S

³5

S

³6

S

³7

S

³8

S

³9

S

³10

S

³11

S

³12

S

³13

S

³14

S

⁴0

S

⁴1

S

⁴2

S

⁴3

S

⁴4

S

⁴5

S

⁴6

S

⁴7

S

⁴8

S

⁴9

S

⁴10

S

⁴11

S

⁴12

S

⁴13

S

⁴14

S

⁵0

S

⁵1

S

⁵2

S

⁵3

S

⁵4

S

⁵5

S

⁴6

S

⁵1

S

⁵8

S

⁵9

S

⁵10

S

⁵11

S

⁵12

S

⁵13

S

⁵14

S

⁶₀

S

⁶₁

S

⁶₂

S

⁶₃

S

⁶₄

S

⁵₅

S

⁵₆

S

⁵₇

S

⁶₈

S

⁶₉

S

⁶₁₀

S

⁶₁₁

S

⁶₁₂

S

⁶₁₃

S

⁶₁₄

S

⁷0

S

⁷1

S

⁷2

S

⁷3

S

⁶4

S

⁶5

S

⁵6

S

⁶7

S

⁶8

S

⁷9

S

⁷10

S

⁷11

S

⁷12

S

⁷13

S

⁷14

S

⁸0

S

⁸1

S

⁸2

S

⁷3

S

⁷4

S

⁶5

S

⁶6

S

⁶7

S

⁷8

S

⁷9

S

⁸10

S

⁸11

S

⁸12

S

⁸13

S

⁸14

S

⁹0

S

⁹1

S

⁸2

S

⁸3

S

4

S

⁷5

S

⁶6

S

⁷7

S

⁷8

S

⁸9

S

⁸10

S

⁹11

S

⁹12

S

⁹13

S

⁹14

S

¹⁰0

S

⁹1

S

⁹2

S

⁸3

S

⁸4

S

⁷5

S

⁷6

S

⁷7

S

⁸8

S

⁸9

S

⁹10

S

⁹11

S

¹⁰12

S

¹⁰13

S

¹⁰14

S

¹⁰0

S

¹⁰1

S

⁹2

S

⁹3

S

⁸4

S

⁸5

S

⁷6

S

⁸7

S

⁸8

S

⁹9

S

⁹10

S

¹⁰11

S

¹⁰12

S

¹¹13

S

¹¹14

S

¹¹₀

S

¹⁰₁

S

¹⁰₂

S

⁹₃

S

⁹₄

S

⁸₅

S

⁸₆

S

⁸₇

S

⁹₈

S

⁹₉

S

¹⁰₁₀

S

¹⁰₁₁

S

¹¹₁₂

S

¹¹₁₃

S

¹²₁₄

S

¹¹0

S

¹¹1

S

¹⁰2

S

¹⁰3

S

⁹4

S

⁹5

S

⁹6

S

⁹7

S

⁹8

S

¹⁰9

S

¹⁰10

S

¹¹11

S

¹¹12

S

¹²13

S

¹²14

S

¹²0

S

¹¹1

S

¹¹2

S

¹⁰3

S

¹⁰4

S

¹⁰5

S

¹⁰6

S

¹⁰7

S

¹⁰8

S

¹⁰9

S

¹¹10

S

¹¹11

S

¹²12

S

¹²13

S

¹³14

S

¹²0

S

¹²1

S

¹¹2

S

¹¹3

S

¹¹4

S

¹¹5

S

¹¹6

S

¹¹7

S

¹¹8

S

¹¹9

S

¹¹10

S

¹²11

S

¹²12

S

¹³13

S

¹³14

S

¹³0

S

¹²1

S

¹²2

S

¹²3

S

¹²4

S

¹²5

S

¹²6

S

¹²7

S

¹²8

S

¹²9

S

¹²10

S

¹²11

S

¹³12

S

¹³13

S

¹⁴14

S

¹³0

S

¹³1

S

¹³2

S

¹³3

S

¹³4

S

¹³5

S

¹³6

S

¹³7

S

¹³8

S

¹³9

S

¹³10

S

¹³11

S

¹³12

S

¹⁴13

S

¹⁴14

S

¹⁴₀

S

¹⁴₁

S

¹⁴₂

S

¹⁴₃

S

¹⁴₄

S

¹⁴₅

S

¹⁴₆

S

¹⁴₇

S

¹⁴₈

S

¹⁴₉

S

¹⁴₁₀

S

¹⁴₁₁

S

¹⁴₁₂

S

¹⁴₁₃

S

¹⁵₁₄

S

¹⁵₀

S

¹⁵₁

S

¹⁵₂

S

¹⁵₃

S

¹⁵₄

S

¹⁵₅

S

¹⁵₆

S

¹⁵₇

S

¹⁵₈

S

¹⁵₉

S

¹⁵₁₀

S

¹⁵₁₁

S

¹⁵₁₂

S

¹⁵₁₃

S

¹⁵₁₄

C

0

C

1

C

2

C

3

C

4

C

5

C

6

C

7

C

8

C

9

C

10

C

11

C

12

C

13

C

14 t = 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

S

¹⁶0

S

¹⁶1

S

¹⁶2

S

¹⁶3

S

¹⁶4

S

¹⁶5

S

¹⁶6

S

¹⁶7

S

¹⁶8

S

¹⁶9

S

¹⁶10

S

¹⁶11

S

¹⁶12

S

¹⁶13

S

¹⁶14

26

S

¹⁷0

S

¹⁷1

S

¹⁷2

S

¹⁷3

S

¹⁷4

S

¹⁷5

S

¹⁷6

S

¹⁷7

S

¹⁷8

S

¹⁷9

S

¹⁷10

S

¹⁷11

S

¹⁷12

S

¹⁷13

S

¹⁷14

27

S

¹⁸0

S

¹⁸1

S

¹⁸2

S

¹⁸3

S

¹⁸4

S

¹⁸5

S

¹⁸6

S

¹⁸7

S

¹⁸8

S

¹⁸9

S

¹⁸10

S

¹⁸11

S

¹⁸12

S

¹⁸13

S

¹⁸14

28

S

¹⁹0

S

¹⁹1

S

¹⁹2

S

¹⁹3

S

¹⁹4

S

¹⁹5

S

¹⁹6

S

¹⁹7

S

¹⁹8

S

¹⁹9

S

¹⁹10

S

¹⁹11

S

¹⁹12

S

¹⁹13

S

¹⁹14

S

²⁰0

S

²⁰1

S

²⁰2

S

²⁰3

S

²⁰4

S

²⁰5

S

²⁰6

S

²⁰7

S

²⁰8

S

²⁰9

S

²⁰10

S

²⁰11

S

²⁰12

S

²⁰13

S

²⁰14

29 30

S

²¹0

S

²¹1

S

²¹2

S

²¹3

S

²¹4

S

²¹5

S

²¹6

S

²¹7

S

²¹8

S

²¹9

S

²¹10

S

²¹11

S

²¹12

S

²¹13

S

²¹14

S

²²0

S

1²²

S

2²²

S

3²²

S

4²²

S

5²²

S

²²6

S

²²7

S

²²8

S

²²9

S

²²10

S

²²11

S

²²12

S

²²13

S

²²14

S

²³0

S

²³1

S

²³2

S

²³3

S

²³4

S

²³5

S

²³6

S

²³7

S

²³8

S

²³9

S

²³10

S

²³11

S

²³12

S

²³13

S

²³14

S

²⁴0

S

²⁴1

S

²⁴2

S

²⁴3

S

²⁴4

S

²⁴5

S

²⁴6

S

²⁴7

S

²⁴8

S

²⁴9

S

²⁴10

S

²⁴11

S

²⁴12

S

²⁴13

S

²⁴14

S

²⁵₀

S

²⁵₁

S

²⁵₂

S

²⁵₃

S

²⁵₄

S

²⁵₅

S

²⁵₆

S

²⁵₇

S

²⁵₈

S

²⁵₉

S

²⁵₁₀

S

²⁵₁₁

S

²⁵₁₂

S

²⁵₁₃

S

²⁵₁₄

S

²⁶₀

S

₁²⁶

S

₂²⁶

S

₃²⁶

S

₄²⁶

S

₅²⁶

S

²⁶₆

S

²⁶₇

S

²⁶₈

S

²⁶₉

S

²⁶₁₀

S

²⁶₁₁

S

²⁶₁₂

S

²⁶₁₃

S

²⁶₁₄

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

S

⁰0

S

⁰1

S

⁰2

S

⁰3

S

⁰4

S

⁰5

S

⁰6

S

⁰7

S

⁰8

S

⁰9

S

⁰10

S

⁰11

S

⁰12

S

⁰13

S

⁰14

31 32

図

4: A

空間状態遷移図

[

補題

4]

^第

x

^行は時刻

t fx = m + 2 n − r − s − 1

時に一斉射 撃する

.

ここで

, x

は

1 ≤ x ≤ r

なる任意の正整数である

. (

略証

)

第

x

行は時刻

t = t 0 = r − x

時に一斉射撃が開始され る

. 2l 1 = 2(x − 1), 2l 2 = 2(m − 2r + 1)

ステップの間

,

スピー ド

1/2

で動作が進行する

.

従って

, l = l 1 + l 2 = m − 2r + x

が成り立つ

. [

補題

3]

より

t fx = t 0 + l + n − 2 + max( s, n − s + 1)

  

= m + n − r − 2 + max( s, n − s + 1)

  

= m + 2 n − r − s − 1.

また

, t 0 = r − x, t 1 = 3 r − x − 2 , t 2 = 2 m − r − x

^より

, t 1 + t 2 − 2 t 0 = 2( m − 1) ≤ 2( n − 1).

従って

,

条件

(8)

を満足 している

.

[

補題

5]

^第

y

^行は時刻

t fy = m + 2 n − r − s − 1

時に一斉射 撃する

.

ここで

, y

は

r ≤ y ≤ m

なる任意の正整数である

. (

略証

)

第

y

行は

,

時刻

t = t 0 = y − r

時に一斉射撃が開始さ れる

. 2l = 2(m − y)

ステップの間

,

スピード

1/2

で動作が進 行する

.

従って

, l = m − y. [

補題

5]

より

,

t fy = t 0 + l + n − 2 + max(s, n − s + 1)

  

=m + n − r − 2 + max(s, n − s + 1)

  

=m + 2n − r − s − 1.

さらに

t 0 = t 1 = y − r, t 2 = 2m − r − y

^より

, t 1 + t 2 − 2t 0 = 2m − 2y ≤ 2(n − 1).

^従って

,

条件

(8)

を満足している

.

 

[

補題

4,5]

より

, m < n

^の場合

,

すべての行上での一斉射 撃は同時に生起し

,

その時刻は

t R = m + 2 n − r − s − 1

で ある

.

一方

,

列方向での一斉射撃では

,

すべてのセルは同時に 射撃状態を取らず

,

同期は実現しない

.

射撃状態の出現は時刻

3

The 18th Annual Conference of the Japanese Society for Artificial Intelligence, 2004

m r

t = r-1

t = m-r

t = 3r-3

t = 2m-r-1 x

y t = 0

t = r-x

t = r+x-2

t = 3r-x-2

t = 2m-x-r t = 2r-2

t = y-r

t = 2m-y-r

t = 2m-2r 1/1

1/1

1/1

1/1 1/1

図

5:

制御レイヤの遅延効果の範囲を示す時間空間図式

t c = m + 2n − r − s − 1

までにすべてのセル上で終了する

.

し たがって

,

各セル上で

t c < t r

が成立し

,

第

2

回目の射撃をア レイ全体の一斉射撃とする

.

図

6

に

m ≤ n

^{の場合における行} 方向の一斉射撃の様子を示す

.

以上を次の定理にまとめる

. [

定理

6]

^サイズ

m × n

^の

2

次元セル空間において

,

将軍位置を

(r, s)

とするとき

, m + n + max(m, n) − min(r, m − r + 1) − min(s, n − s + 1) − 1

ステップの最適時間でセル空間全体を一 斉射撃状態に導くアルゴリズムが存在する

.

ここで

(r, s)

は

, 1 ≤ r ≤ m, 1 ≤ n ≤ s

の任意の正整数である

.

4. おわりに

Szwerinski [14]

とは異なる制御手法を用いた最適時間一般

化一斉射撃アルゴリズムを提案した

.

今後の課題として計算機 上での実装が残される

.

1/7 t = r+s-2

t = n+r-s-1

t = s-1

t = n-s

t = 3r+s-4

t = m+2n-r-s-1

t = n+3r-s-3 t = r-1

t = r-x

t = y-r

t = 2m-r+s-2

t = 2m+n-r-s-1

t = 2m-2r+s-1

t = 2m+n-s-2r

t = m-r

t = 3r-3

t = 2m-r-1

t = 0 t = 0t t = 0

t = 2m-2r

t = 0

t = 2m-r-y

t = 0

Control Layer Synchronization Layer

n

m n r

m s

s

t = r-1

t = m-r

t = 3r-3

t = 2m-r-1

n

m

n

m y n

m x

n

Synchronization Layer Synchronization Layer Synchronization Layer Synchronization Layer

m

1/1

1/3 1/1

1/3 r

t = r+s-x-1

t = n+r-s-x

t = m-r+s-1

t = m+n-r-s t = s-r+y-1

t = n+y-r-s

t=m+2n-r-s-1 t = 3r+s-x-3

t = n+3r-s-x-2

t=m+2n-r-s-1 t=m+2n-r-s-1 t=m+2n-r-s-1

x y

t = n+2r-s+x-2 t = r+x+s-3

t = 2m-r+s-x-1

t = 2m+n-r-s-x

t = 2m-r+s-2y-1

t = 2m+n-r-s-y t = 0

t = r-x

t = r+x-2

t = 3r-x-2

t = 2m-x-r t = 2r-2

t = y-r

t =2m-y-r

t = 2m-2r

rr

t = r+x-1

t = 3r-x-2

t = 2m-r-x

r

s s

r

s s

r

s n n

s n

s n

s

図

6: m < n

^における

2

次元セル空間の時間空間図式

参考文献

[1] R. Balzer: An 8-state minimal time solution to the firing squad syn- chronization problem. Information and Control, vol. 10(1967), pp. 22-42.

[2] W. T. Beyer: Recognition of topological invariants by iterative arrays.

Ph.D. Thesis, MIT, (1969), pp. 144.

[3] A. Grasselli: Synchronization of cellular arrays: The firing squad prob- lem in two dimensions. Information and Control, vol. 28(1975), pp. 113-124.

[4] K. Kobayashi: The firing squad synchronization problem for two-

dimensional arrays. Information and Control, vol. 34(1977), pp. 177-197.

[5]

前田,梅尾: 2次元セルラオートマトン上での一斉射撃アルゴリズム.情報処理学会アルゴリズム 研究会,第

81

回アルゴリズム研究会, 81-1, pp. 1-8, (2001).

[6]

前田,道坂,梅尾: 2次元一斉射撃アルゴリズムのための新しい設計手法.電子情報通信学会 コン ピューテーション研究会, COMP2001-97, pp.33-40, (2002).

[7] J. Mazoyer: A six-state minimal time solution to the firing squad syn- chronization problem. Theoretical Computer Science, vol. 50(1987), pp. 183- 238.

[8] M. Minsky: Computation: Finite and infinite machines. Prentice Hall, (1967), pp. 28-29.

[9] E. F. Moore: The firing squad synchronization problem. in Sequential Machines, Selected Papers (E. F. Moore ed.), Addison-Wesley, Reading MA., (1964), pp. 213-214.

[ 10] F. R. Moore and G. G. Langdon: A generalized firing squad problem.

Information and Control, vol. 12(1968), pp. 212-220.

[ 11] H. B. Nguyen and V. C. Hamacher: Pattern synchronization in two- dimensional cellular space. Information and Control, vol. 26(1974), pp. 12-23.

[ 12] A. Settle and J. Simon: Smaller solutions for the firing squad. Theo- retical Computer Science, vol. 276(2002), pp.83-109.

[13] I. Shinahr: Two- and three-dimensional firing squad synchronization problems. Information and Control, vol. 24(1974), pp. 163-180.

[14] H. Szwerinski: Time-optimum solution of the firing-squad- synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theoretical Computer Science, vol. 19(1982), pp. 305- 320.

[15]

寺岡,久岡,前田,梅尾:2次元セルラーオートマトン上での最適時間一般化一斉射撃アルゴリズ ムの設計,電子情報通信学会総合大会,D-1-10,pp.10[2004]

[16] H. Umeo, M. Maeda and N. Fujiwara: An efficient mapping scheme for embedding any one-dimensional firing squad synchronization algorithm onto two-dimensional arrays. Proc. of the 5th International Conference on Cel- lular Automata for Research and Industry, LNCS 2493, Springer-Verlag, pp.69- 81(2002).

[17] H. Umeo, M. Hisaoka, K. Michisaka, K. Nishioka and M. Maeda: Some generalized synchronization algorithms and their implementations for a large scale cellular automata. Proc. of the Third International Conference on Un- conventional Models of Computation, UMC 2002, LNCS 2509, Springer-Verlag, pp.276-286(2002).

[18] V. I. Varshavsky: Synchronization of a collection of automata with random pairwise interaction. Autom. and Remote Control, vol. 29(1969), pp.

224-228.

[19] V. I. Varshavsky, V. B. Marakhovsky and V. A. Peschansky: Synchro- nization of interacting automata. Mathematical Systems Theory, Vol. 4, No.

3(1970), pp. 212-230.

[20] A. Waksman: An optimum solution to the firing squad synchroniza- tion problem. Information and Control, vol. 9(1966), pp. 66-78.

4