経営科学(日本オベレーショ γ ズ・リサーチ学会邦文機関誌)

ある

第 18 巻分探索モデ lレ T

村1.

第 3 ・ 4 号(1 974年 7 月)

上

知*

序論
一つの探索日擦が与えられた区間上にあり，民間 1: の 1 点を選べば日諜がその右にあるか在にあるかが判別できるような課索行動を考える.ただし判51iHこ要する費用は，もし日擦がその点の左にあるときには 1 単佼，右にあるときには k( 注 1) 単位とする.すなわち，最初の探索点な任意に選べば，その点での探索の結果，円擦がその点より左側の区聞に存在ナるか，あるいはお側の係閣に存在するかがわかり，目標の存在訳詞が縮小される.左様，1]の民間に存在する場合にはこの探索に 1 なる費用を婆し，右側の区間に存在する場合には k なる費用が必要である.このようにして縮めたi玄関を新たな区間とみなして同様の探索を続けると，目標の存在区間を限りなく縮めることができるが，実際問題としては、その必繋はなく，適当な長さ d にまで縮めれば十分である.ここで， .;;1 =1 としても一般性会失わない.
以上のような探索モデルに対して少なくとも次のニつの問題が考えられる.

(1) 長さ n の与えられた存在区間を長さ 1 にまで縮めるに要する期待費用を最小にナるような判別点の系列(期待費用最小政策と呼ぽりと，この系列を用いた場合に要する最小期待費用
f(めな求めること.

(n) 長さ持の与えられた存夜区間をまえさ 1 にまで縮めるに委する費用の最大を最小にするような半1)別点の系列(ミニマックス政策と呼ぼう)と，この系列を用いた場合に要する最大の費用
h(n) を求めること.

問題(I)は Cameron ら[ 1J によって提案された.絞らは，探索沼擦の事前確率は一様であると仮定して定式化し ， f(n) の j駅近式を求め，さらに k=6 のときの数鎖解を示している.また著者 [2 ]は，彼らと同じ夜窓のもとにその離数問題 (11 ， k および判翌1] 点の位置 r が整数しかとらない場合)の厳療な解を得た.しかし，問組(日)の場合を取り扱った文献は見あたらない.本研究ではこの問題を取り扱い，持および z が実数であるような一般の場合について厳密な解を得た，また ， n , X および h が整数の場合には期待費用最小政策はミニマックス政策でもあるとし、う興味ある性賞を得た.

t 1972 年 10 月 16 El受理.

*防衛大学校応用物獲教室.
125© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

126

村上先!

2. 定式化と解の導出
存在区間の長さ n を単位の長さにまで縮めるのにミニマックス政策を用いた場合に要する最大の費用を h(n) としよう.最初の探索点 z を任意に選び，もし探索目標がその点よりも左にある場合には，点 z での探索コストは 1 で，それ以後ミエマックス政策を用いた場合に要する最大の費用は h(りとなる.また右にある場合には点 z での探索コストは h で，それ以後ミニマックス政策を用かて要する最大の費用は h(n-x)となる.したがってベルマンの DP の原理により，ただちに次式が成立する.

o(2.
1) h(n)= ~lminmax(l 十 h(x) ，O:;;.
:;;n1~ n>0n>lk 十 h(n-x)}

ただし h は 1 以上の整数 ， X , n は非負の実数とする.ここで(2.
2) Hn(x)=max(l+h(x) , k 十 h(n-x)} .
とおき，与えられた n に対して H，， (x) を最小とする z の集合を S" とおくと， n>l のとき (2. 1)
は次のごとく書きかえられる.

(2.
3) h(n)= minHn(x)= H,, (x;x f. S")<Hn(x;x$Sn)
.
0".
:;;"

次に整数 m ，に対して次式によって定義される関数 g(m) ， N(i) を導入しよう.

11 二三 i ミ 2-k(2.
4) N(i)= {lN(i -l) 十 N(i-k)(2.5) g(m)= g(m‑1)+ ψ (m)

二三 2
間三 2

ただし g( 1)=l+k で，関数 ip(m) は m=N(j) を満たす整数 j が存在する場合には 1 ，しからざるときは O とする.このとき g(m) ， N(i) に関して次の補助定理が成立する[ 2].

表 1I g(m)k=6 のときの g(m) ， N(m) の{直IJ..例g(m)N(m)

噌i15952

句1

勾d
4EE--A-1-41
14

14

i1
句・

噌EA

且 U4
ムヮ“只υ0000

噌i1A14

交UQdAυ

宮内 05

唱目目晶

民UFhυEυ噌E4 噌Eム司自由晶

iuquA2EU

巧4

巧400

噌i14

ウtnd

氏U

つ白ワ

υ

'44E4
噌iqdO083pb6nv

斗ムヴd

QAVA 宮戸 D

141A

噌EAaAZ 凋当日

つλMaul7A

ゐ'Ai
噌 n4ndaqRυpbn61&A-

ヮ“

噌Eム噌

E4
噌'a- 唱'回会噌

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

9361243623592

1 品

民UCυaunt

見υQdAU14

唱'ain41vqO4

唱

句目目ふ噌EA1122222222223

34FUFUndQd

噌'AAUBA噌目目ゐ吋

3456789012345

9m

127ある二分探索モデル

N( 隅)

g(m)
18171615141312111098

1000

100

7 ト・

10

65qunFM「ll「 Ls守ao 2 4 6 8 1012141618202224262830m
図1 2 4 6 81012141
618202224262
830m

k=6 のときの (1(m) の値

図 2

k=6 のときの N(m) の値

補助定理1.与えられた任意の整数 m に対して ， N(i) 三:;;m 三三 N(i+1)-1 を満足するただ一つの整数 i が決まり，次式が成立する.

(2.
6) u(m)=i+k.
11=二 6 のときの g( 11I)， N(m) の値を図 1 ，図 2 および表 1 に示す.
(2.1)

または (2.3) の解は次の定理によって与えられる.

定理1. Iz (n) ， らは次式によって与えられる(2.7) h(n)=, g(元 )-1 ，(2.
8) 5" ニ {.x; n‑N(i+1‑k)~.x三 N(i)}ただし元は n より小さい最大の整数で， i は(2.
9) N(i) 三二元三三 N(i +1)-1を満たす整数とする.

証明.初期条件 h(n)=O (1 ;:::n ミ 0) のもとで h(n) が一意に定まることは (2. 1) より明らかであるから，(2.7) , (2.8) が (2.3) を満たすことを示せばよい. (2.4) より明らかに N(i) は増加関数であるから，半開区間 A戸 (N(i) ， N(i+1)) の合併集合 UA; は 1 より大なるすべての実数を含む.したがって，ある任意の整数 i ミ 1 を与え\，、かなる nE A; に対しても(2. 7) , (2.8)が (2.3) を満たすことを示せば，すべての 1 より大なる実数 n に対して定理を証明したことになる.

(n , .x)平面を考え，次のような集合を導入しよう.
R;= {(n ,.x); nE A;, O~ .x 三三 n}

C;= {(n , x);nEA; , xESn}© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

128

村上知U , = {(n , X)
; nfA" N(i)<X~ n)Li= {(n , x)
; nfA" 0三三 x<n-N(i 十 1-k)}
ここでR， =C， UU， UL ， ・以上の各領域の関係は図 3 に示される.
r(2.7) を (2. 2) に代入して各領域内での Hn(x) のX=n 取りうる値を求めると次のようになる(詳細は付録参九;斜線 (;-!1分照) •(n , X)fC，のとき H"(x) = i 十 k-1 ，(n , X)fUi のとき H，， (x) ニ t 十 k ，(n , X)fLi のとき Hn(.T) 孟 t 十 k.
以上をまとめると，(n , X)fCi のとき H"(x) =i+k-1 ,(n , x) 辛 C，のとき Hn(X) ミ i+ k.
N(;)
Iヨ 3N( 什 Dn換言すれば任意の nf んに対して

符1 域 Ri の分割

X$S" のとき

XfSn のとき H"(.r) = i 十 k-1 ，H"(x) ミ t 十 k.

すなわち X f S" のときのみ H，， (x) は最小値 i+ k-1 を持つ.また補助定理とnfAi に対して ，(2.9)

より任意のg(元)ニ i+k であるから，ただちにh(n) 一 min

H ,, (x) = g(元 )-1 一 (i +k-1) = 0

O::;:x~nQ.E.D.
系1.関数 h(n) は .1， なる民間で一定値 z 十 k-1 をとる.

k理 1 よりミニマックス政策を得るのは容易である.すなわち，与えられた任意の n に対してSn の任意の要素を判別点として選び，判別の結果縮まった区間の長さを改めて n とみなして Snの任意の要素を第 2 の判別点として選び，以下同様にして単位の区間になるまで続ければよい.
このようにして得られた判別点の系列はミニマックス政策である

よってらをミニマックス政策と呼ぼう.
前節で、述べた問題( l)を DP の原理を用いて定式化すると、ただちに次式が得られる.

(2.
10) f(n)= min[x{l+f(x))/n+(n‑x){k+f(n‑x))/n].

n>1.

O~三 x:=:;n

ここで 11 ， X, k は本論文の記号と同じ意味を持つ.さて En(x) = X(1+f(x)}/n+(n‑x)(k+f(n‑x)}/nとおき，与えられた n に対して E，，(.r) を最小にする r の集合を(x*(n))とおくと，(2.10) は次のごとく書きかえられる.

(2.
11) f(n)=minEn(x)=En(x;xf(x*(n)})<En(x;xE
ﾋ(x*(n))).
O<x<n河x，k が整数のとき(2.12){x 水 (n)} =(x*(n))

は次のごとく書ける.

{x;max(N (i -1) , n‑N(i+1‑k)) ~ x ζ min(N(i) ， n‑N(i‑k))}

これは著者の前論文[ 2]で求められたもので，本論文のらに対応している.よっていペ n)) を© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

129ある二分探索モデル

期待費用最小政策と呼ぶと，ミニマックス政策らとの聞には次の定理が成立する.

定理 2. n , x および h が整数の場合，期待費用最小政策 (x*(n)) はミユマックス政策らでもある.
証明.

(x*(n)) ニ (x;max(N(i-1) ,n-N {i +1-k)) ζ x S min(N(仏n-N(i -k))} .

Su= {x; n ー N(i 十 1-k) 三二工三三 N(i))
ここで、，min(N(仏n-N(i -k)) ζ N(i)，n-N(i +1-k) 三 max(N(i ー 1) ，以上よりただちにn‑N(i+1‑k)).

Q.E.D.

(x*(n)) cS"

この定理は n ， X , k がすべて正の実数という一般的な場合にも成立すると思われるが，今後の研究課題である.

各領域内での Hn(x) の取りうる値

付録 A.

ll,, (x) の{甫を求める使宜上，領域 Cj を次の三つの領域に分割しよう.
C ,o = {(n ， 刈n E Ai ,Ki'lI}

XECi
1 = {(n , x); nfA" n‑N(i‑k)<x 三 N(i))

Ci2= ((n , x); nfAi ,n-N(i+1-k) ζ x<N(i‑1))

7、こだし，

K""= [max(N (i -1) , n-N (i +1-k)) , min(N(i) , n‑N(i‑k))].
ここで，R ， ニ Ci

UU, ULj=)‑ｭ(

次に各領域内での lln (.r)

CjQ

U(';
¥UCi2UUiUL ， ・の取りうる舶を求めよう.

(n , x) f Ui のとき

H ,, (x) の値を求めるために (2.7) 式を (2.2) 式に代入すると，n(x)=max(g(x) , g(n‑x)+k‑1)(A.1) Hとなる.

よって g(x) ，g(n‑x) の値を求めればよい.元の定義より(A.2) n-1 三二元 <n
よって η -x=(n ー 1) ー (x ー 1) 三諒一 (x-1) 三品 +l-x

また y が整数のときは d ニグ -1 であるから
元 -x+1= 元 -x ，(A.3)
次に

したがって

n-x 三三品 -x(2.9) 式と Ui の定義より(A.4) N(i)sx 三三員三三 N(i 十 1)-1(2.4) , (A.3) , (A.4) 式を用いるとただちに(A.5) n‑xS 元 -x 云 N(i+1)-N(i) ー 1 =N(l 十 1-k) ー 1© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

130村ヒ知を得る.よって (A. 4) , (A.5) 式と補助定理より ， g(.z )=i+k, g(五二泊三二 i を得る.これらの値を (A.1) 式に代入するとただちに(A.6) H.
.
(x)= i+kを得る.

(ii) (n , X)ELi のとき
Li の定義より n-x>N{i +1-k).

したがって n-x~ N(i+ 1-k)となり，補助定理を用いると，

y(n-x) ミ i+1 を得る.これより(A.7) H.
.
(x)~ i+k(iii) (持， X)ECiQ
C;o の定義より

max{N(i -1) , n‑N(i+1‑k)} ~ X 三二 min{N(i) , n‑N(i‑k)}
よって(A.8) N(i‑1)~ X ζ N(i)(A.9) N(i‑k)~ n‑x~ N(i+1‑k)を得る.これより g(x)= i+ k-1 または i+ k-2 ， g(五二記)=i または i-1 となり ， H.(x) の値が決まらないので二つの場合にわけて求めよう.

(a) x=N(i-1) のとき(2.9) 式より

(A.10) N{i)<n~ N(i+1)
したがって n-.f>N(i)‑N(i ー l)=N(i-k).

これと(A.9) 式より N(i -k)<n-x~N(什 1-k).

ゆえにこのとき y(.z)=i+ k-2 ， g(九二面)=i となり ， Hn(x)= i+ k-1 を得る.
(b) N(i -1)<x ζ N(i) のとき

g(.
x)=i+ k-1 , g(n-x) 三二人
結局 (a) ，

よって Hn(x)=i+k‑1.

(b) よりどちらの場合も(A.11) Hム (x) =i 十 k- l.

(iv) (珂， X)ECil のとき
n‑N(i‑k)<x~N(i) と(A. 10) 式よりN(i -1)<x~N(i)，n-.(<N(i -k).

したがって g(x)=i+k-1 ， g(n-x) 云 i- l.

ゆえに(A.12) H.んr) =i+k‑l.
(v) (n， x)E C; z のとき
n-N( i+ 1-k) ζ x<N(i -1)と(A.10) 式より，x<N(i-1) , N(i-k)<n-x ζ N(i +1-k) となり ， g(x) 三三 i+k-2 ， g(n-x)=i を得る.ゆえに(A.13) Hn(x)=i+k‑l.
以上をまとめると(n , X)ECi のとき

Hn(x)=i+k-1 ,© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

ある二分探索モデノレ(n , X)
EUi のときH ,, (x) = i+k ,(n , X)
EL. のとき

Hn(X)~ i 十 k.

131となる.

参考文献[1] Cameron , S.H. andS.G. Narayanamllrlhy ,“ A Searc
hProblem ， "ορ ns. Res. , 12 , 4 (1964) , 623‑629.
[2J Mllrakami , S. ,“ A DichotomollsSearch ，'ソ .0仰 s. Res.Soc.Japan , 14 , 3 &¥t(1971) ， 127-112 目© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.