https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%A9%E3%83%B3%E3%83%87%E3%83%96%E3%83%BC%E6%8E%A2%E7%B4%A2
ランデブー探索 - 版の履歴
2026-05-28T00:55:52Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%87%E3%83%96%E3%83%BC%E6%8E%A2%E7%B4%A2&diff=9758&oldid=prev
2008年4月2日 (水) 06:56にSakasegawaによる
2008-04-02T06:56:19Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年4月2日 (水) 06:56時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【 らんでぶーたんさく (rendezvous search) 】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【 らんでぶーたんさく (rendezvous search) 】'''</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>友好的な2人以上の[[探索者]]が早く遭遇するための方策を</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>友好的な2人以上の[[探索者]]が早く遭遇するための方策を</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >7行目:</td>
<td colspan="2" class="diff-lineno">8行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>探索者が得る情報，探索者の数，探</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>探索者が得る情報，探索者の数，探</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>索者の初期位置についての設定，探索基準等によって種々の[[モデル]]が考えられる．</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>索者の初期位置についての設定，探索基準等によって種々の[[モデル]]が考えられる．</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 夫と妻がデパートではぐれてしまったときのためにあらかじめ打ち合わせておくことにした．呼び出しサービスもなく，また２人のうち少なくとも一方が携帯電話を持っていないとしたとき２人ができるだけ早く遭遇するためにはどうしたらよいか．また，ハイカーがはぐれたときの用心のために移動方法を記したハンドブックを作成したい．再会するまでに要する時間が平均的に小さくなるような方法を求めよ．[[ランデブー探索]](rendezvous search) とは友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．古くから文献で指摘されてきたが，ランデブー探索の数理的研究が盛んになったのは１９９０年前後以降である．探索者の行動領域が離散であるか連続であるか，またそれが有界であるかどうか，探索者がとり得る行動（戦略），探索者が得る情報，探索者の数，探索者の初期位置についての設定，その他によって種々のモデルが検討され研究が続けられている．ランデブー探索では探索者をplayer</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">と呼ぶことが多いが，一般にはランデブー探索はゲームではないことに注意すべきである．探索者が事前にお互いの役割について相談していない状況（上記ハイカーの例）を，すべての探索者が同じ戦略を用いるとしてモデル化し，この場合を(player-)symmetric という．一方探索者ごとに異なる戦略を用いることができるモデル（上記夫妻の例）をasymmetric という．他の条件が同じである場合，symmetric モデルの方がasymmetric モデルより数理的解析が困難である．探索者が2 人であるようなasymmetric モデルにおいて，探索者の一方は初期位置に留まって動かないような戦略に限定すると，他方による静止目標物の探索問題となる．探索者同士が探索領域についてどの程度の知識を共有しているか，（例えば，時計回り，方位等）もランデブー探索の重要な要素である．最小の期待再会時間をランデブー値（rendezvous value）と呼ぶ．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">'''[直線上のランデブー探索：asymmetric モデル]''' 2 人の探索者（探索者I，II）が数直線上に位置している．2 人は時刻<math>0\,</math> においてお互いの初期位置間の距離<math>d\,</math> の確率分布<math>F\,</math> を知っているが，自分が数直線上のどこにいるのかわからない．相手が自分のどちら側にいるのか，またどちら向きに進んでいるのかを知らない．それぞれが自分の最初の向きを前進だと考える．最初に進む向きの組み合わせは4 通りあり，それぞれが確率<math>1/4\,</math> で起こる，とする． 2人は速さ<math>1\,</math> で進むことができて，できるだけ早く遭遇することを望んでいる．2 人が同時刻に同じ点にいるとき出会うことができると仮定する．期待再会時間を最小にするには2 人は直線上をどのように動けばよいか．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> この問題において，それぞれの戦略は次の集合から選ばれる，とする．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">L= \{ f:[0,\infty) \rightarrow (-\infty, \infty): ~ f(0)=0,~ |f(s) - f(t)| \leq |s - t| \} .\,</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>f \in L \,</math>に対し，<math> f(t)\,</math>は時刻<math>t\,</math> において，初期位置に対する探索者の相対的な位置を表す関数である，ただし探索者の最初の向きを正とする．例えば，初期位置が<math>w\,</math> で最初の向きが左であって<math>f(t)=5\,</math> であったとする．探索者<math>t\,</math>の時刻での位置は<math>x-5\,</math> である．一方，最初の向きが右であって<math>f(t)=-5\,</math> であっても時刻<math>t\,</math> での位置はやはり<math>x-5\,</math> となる．一般に，初期位置が点<math>x\,</math> であり戦略<math>f\,</math> を選んだならば，時刻<math>t\,</math> での位置は確率<math>1/2\,</math> ずつで，<math>x \pm f(t)\,</math> となる． <math>L\,</math>の部分集合で，傾きが<math>\pm1\,</math>（離散点を除いて）となる<math>f\,</math> の全体は<math>L\,</math> 内でdense である．2 人の戦略をそれぞれ<math>f,g\,</math> とする．探索者I，II の初期位置をそれぞれ点<math>0\,</math> および<math>d\,</math> とする．2 人の最初の向きが，探索者I は右，探索者II は左である，つまり <math> {I \atop \rightarrow} {II \atop \leftarrow} \,</math>とすれば， <math>f(t)+g(t)=d\,</math>となる最小の時刻<math>t\,</math> で2 人は出会うことになる．同様に考えて，探索者I，II の初期位置がそれぞれ点<math>0\,</math> および<math>\pm d\,</math> のときの2 人の期待再会時間は</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">T(f,g)= \int_{0}^{\infty} \frac{1}{4} \left[ \min \left\{ t: f(t)=d+g(t) \right\} + \min \left\{ t: f(t)=d- g(t) \right\} </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> + \min \left\{ t:f(t)= - d+g(t) \right\} + \min \left\{t:f(t)=-d -g(t) \right\} \right] d F(d)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\,</math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">となる．目的はasymmetric ランデブー値<math>R(F)\equiv \inf_{f,g\in L}T(f,g)\,</math> を求めること，またそれを与える戦略を見つけることである．確率分布<math>F\,</math> が有界で平均が<math>\lambda\,</math>，最大値が<math>D\,</math>，つまり<math>F(D)=1\,</math>であるとする．次のような戦略の組<math>(f^{*},g^{*})\,</math> を考える．<math>f^{*}\,</math> は初期位置から<math>D\,</math> だけ進み，その後折り返して<math>2D\,</math>だけ進む. <math>g^{*}\,</math>は <math>D/2\,</math>だけ進み，折り返して初期位置に戻る．次に任意の方向へ確率<math>1/2\,</math> で<math>D\,</math>だけ進み折り返して初期位置に戻る，というものである．すると<math>T(f^{*},g^{*})=(9D+4\lambda)/8\,</math>となりランデブー値<math>R(F)\,</math> の上界が得られる．特に，初期位置間の距離<math>d\,</math> が既知の場合は<math>d = D = \lambda\,</math> となり，ランデブー値は<math>13d/8\,</math> となる．このとき唯一の最適な戦略は上記<math>(f^{*},g^{*})\,</math> であることが知られている．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">'''[直線上のランデブー探索：symmetric モデル]''' この場合は初期位置間の距離が既知であるような基本的なモデルであってもランデブー値の上界が得られているにすぎない．初期位置間の距離の分布<math>F\,</math> が有界であり最大値が<math>D\,</math> 平均が<math>\lambda\,</math> であるとする．2 人の探索者それぞれが速さ<math>1\,</math> で動き， <math>D/2\,</math> の整数倍の時刻のみに方向を変えるような戦略を次のように表現する．<math>\eta_1 F \eta_2 B \eta_3 F \eta_4 B \ldots\,</math>. これの意味は，まず <math>\eta_1 D/2\,</math>の間前進，<math>\eta_2 D/2\,</math> 後進，...．このような表現の戦略あるいはそれの組み合わせでしかもできるだけ期待再会時間を小さくするような特定の戦略を考えることが研究の現状である．例えば，<math>d = D = \lambda=2\,</math>とする． 2人が<math>1F2B\,</math>，つまり，まず確率<math>1/2\,</math> で進む向きを決め，その向きに<math>1 \times D/2 =1\,</math> だけ進み<math>2\,</math> だけ戻る．再び確率<math>1/2\,</math> で向きを決め，同じ行動を繰り返す．この戦略での期待再会時間は<math>5\,</math> になる．より複雑な戦略を考えることにより， <math>F\,</math>の最大値が<math>D\,</math>，平均が<math>\lambda\,</math> のとき現在得られている最小の上界は，<math>1.701D+0.5\lambda\,</math>である．特に，初期位置間の距離<math>d\,</math> が既知の場合は<math>d = D = \lambda\,</math> となり，ランデブー値の上界<math>2.201d\,</math> が得られる．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">'''[ランデブー探索に同値な探索問題] ''' [直線上のランデブー探索：asymmetric モデル] において，<math>F\,</math> が有限の平均をもつと仮定する． 2人の戦略<math>f,g\,</math> に対し，<math>x,y\,</math>を</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">x(t)=f(t)+g(t), ~~ y(t)=-f(t)+g(t), ~~ |x^{'}(t)| + |y^{'}(t)| \le 2</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\,</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">と定義する．例えば2 人の最初の向きが<math> {I \atop \rightarrow} {II \atop \leftarrow} </math> の場合，時刻<math>s\,</math> までに2 人が出会えるのは<math>d \le \max_{0 \le t \le s} \left[ f(t)+g(t) \right] \,</math> となる場合で，その確率は，<math>F( \max_{0 \le t \le s} \left[f(t)+g(t) \right])\,</math>, つまり<math>F(\max_{0 \le t \le s}x(t))\,</math>である．他の3 つの場合も同様に考えて，結局2 人が時刻<math>s\,</math> までに出会う確率は</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">P_{f,g}(s)= \frac{1}{4} \left\{ F(\max_{0 \leq t \leq s} x(t))+F( \max_{0 \leq t \leq s} -x(t))+ F(\max_{0 \leq t \leq s} y(t))+F(\max_{0 \leq t \leq s} -y(t)) \right\}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\,</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">となる．一方，直線上のランデブー探索が次に述べる探索問題において戦略を上述の<math>x,y\,</math> としたものに同値であることが知られている．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 1 つの静止目標物が2 本の数直線<math>l_I, l_{II}\,</math>, のうちのいずれかに存在する．存在確率は<math>F\,</math> で与えられる．探索者I,II の初期位置はそれぞれ数直線,<math>l_I, l_{II}\,</math> の原点である．2 人の探索者は，合計の速さが<math>2\,</math> であるようにして数直線上を移動しながら目標物を探索する．2 人のうちの1 人が目標物を発見するまでの期待時間が最小になるような行動を求めよ．このとき，2 人のうちのどちらかが時刻<math>s\,</math> までに目標を発見する確率が<math>P_{f,g}(s)</math> で与えられる．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">'''[3 人以上のランデブー探索]''' (i) 長さが<math>n\,</math> である円周上に等距離<math>1\,</math> だけ離れて<math>n\,</math> 人の探索者がいる．円周上には位置を特定できる目印はなく，また<math>n\,</math> 人のすべてにとって，どちらが時計回りかの共通の認識がない．<math>n\,</math> 人が円周上で一同に会すには探索者はどのように動けばよいか．この問題のランデブー値は漸近的に<math>n/2\,</math> であることが知られている．(ii) <math>n\,</math>人が数直線上の連続する整数点上に位置している．それぞれが確率<math>1/2\,</math> で自分の向きを決める．すべてが一同に会すことができることを確実にするのに必要な時間を最小にするにはどのように動けばよいか．この最小時間を<math>\min\max\,</math> ランデブー値という．これは漸近的に<math>n/2\,</math> に近づくこと，さらに<math>n=3\,</math> の場合は <math>\min\max\,</math>ランデブー値が<math>3.5\,</math> であることが知られている．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> ここで紹介したモデル以外にも，例えば探索領域が2 次元以上の場合のランデブー探索，ネットワーク（あるいはグラフ）上でのランデブー探索等について論文が散見されるが，多くの問題が残されており今後の研究が待たれる状況である．ここで紹介した分析を記述した原論文についての情報も含めて，詳しくは参考文献[1] を参照されたい．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[1] S. Alpern and S. Gal, ''The Theory of Search Games and Rendezvous'', Kluwer’s International Series, 2003.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[category:探索理論|らんでぶーたんさく]]</ins></div></td></tr>
</table>
Sakasegawa
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%87%E3%83%96%E3%83%BC%E6%8E%A2%E7%B4%A2&diff=9443&oldid=prev
2007年9月20日 (木) 06:28にSaruによる
2007-09-20T06:28:42Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年9月20日 (木) 06:28時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''【 らんでぶーたんさく(rendezvous search) 】'''</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''【 らんでぶーたんさく (rendezvous search) 】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．探索者の行動領域が離散であるか連続であるか，またそれが有界であるかどうか，探索者がとり得る行動，探索者が得る情報，探索者の数，探索者の初期位置についての設定，探索基準等によって種々のモデルが考えられる．</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">友好的な2人以上の[[探索者]]が早く遭遇するための方策を</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">考える探索問題である．</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">探索者の行動領域が離散であるか連続であるか，</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">またそれが有界であるかどうか，探索者がとり得る行動，</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">探索者が得る情報，探索者の数，探</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">索者の初期位置についての設定，探索基準等によって種々の[[モデル]]が考えられる．</ins></div></td></tr>
</table>
Saru
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%87%E3%83%96%E3%83%BC%E6%8E%A2%E7%B4%A2&diff=8772&oldid=prev
Tetsuyatominaga: 新しいページ: ''''【 らんでぶーたんさく(rendezvous search) 】''' 友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．探索...'
2007-08-14T17:16:39Z
<p>新しいページ: ''''【 らんでぶーたんさく(rendezvous search) 】''' 友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．探索...'</p>
<p><b>新規ページ</b></p><div>'''【 らんでぶーたんさく(rendezvous search) 】'''<br />
<br />
友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．探索者の行動領域が離散であるか連続であるか，またそれが有界であるかどうか，探索者がとり得る行動，探索者が得る情報，探索者の数，探索者の初期位置についての設定，探索基準等によって種々のモデルが考えられる．</div>
Tetsuyatominaga