数理解析研究所講究録 1325 巻 2003 年 8-14

8

守備特訓に喘ぐ外野手のための捕球経路問題-Busy Outfielder Problem
佐久間 俊慎 *1

小野 廣隆 *

はじめに

君は守備特訓を命ぜられた外野手である. そこで次々と打ち出されるボールをできるだけ多く捕球するための移動経路を求めたい.
この問題を多忙な外野手問題 (Busy Outfielder
Problem-BOP) と呼ぶ. 実世界ではおおよそ次の二つの状況において BOP が現れる. 第一に, 複数の移動するシステム要素にアクセスする必要がある場合であり, 第二に, 複数の移動する障害物を排除してシステムを保全する必要がある場合である. 簡単な具体例として, 航空機の空中給油ス
ケジュール, 複数のベルトコンベアに乗って流れる製品の収集スケジュール, ミサイルを迎撃する
戦闘機の飛行スケジュールなどを求める問題がある. しかし, 有名な格言「二兎追う者、 一兎も得ず」が示すように, BOP の応用は物理空間上のス
ケジュールに留まらない.

BOP はその応用上, 3 次元空間を対象としたオ
ンラインアルゴリズムの検討がより重要であると思われるが, 本論文では BOP を 2 次元空間上のオフライン問題として検討する. すなわち, ボールと選手を 2 次元空間上の点, ボールの軌跡を等速直線運動によってモデル化した上で, ボールの軌跡が与えられたときに, できる限り多くのボールを捕球するための選手の移動スケジュールを出力するアルゴリズムを検討する.

牧野 和久 \d ag er

朝廣 雄一 \dag er

山下 雅史 *
堀山 貴史\S

ボールと選手の速度の関係について一切の仮定を置かないが, 問題の定義から (野球場が十分に広いという仮定の下で) 一般性を失うことなしに
ボールは選手より遅くないと仮定できる. 一方,
選手はボールよりも速いという仮定を入れるならば, 常にすべてのボールを捕球できるので, 捕球できるボールの個数ではなく, すべてのボールを捕球するために必要な時間が主な検討対象になる.
この問題は Moving Target TSP と呼ばれている.
停止したボーノレに対する Moving Target TSP はよく知られた NP-困難問題である巡回セールスマン問題 (Traveling Salesman Problem, TSP) であるから, Moving Target TSP も一般には NP-困難である. しかし, 野手とボールが同じ直線上を移.
$O(n^{2})$時間で最適スケジュール
動する場合にはが計算でき [5], すべてのボールの速度が一定の場合には PTAS が存在する [4] ことが知られている. ここで, $n$ はボーノレ数である.

2

多忙な外野手問題

xr 平面上を等速直線運動する$n$個の点 (ボーノレ) $B=\{b_{1}, b_{2}, \cdots, b_{n}\}$ を考える. ボーノレ のと速度ベ
運動は時刻 0 における位置によって与えられている. 時刻
クトル
でにおけるボーノレの位置を$b_{:}$$b_{:}(0)\in \mathrm{R}^{2}$$v:\in \mathrm{R}^{2}$$t\in \mathrm{R}$表わす. ここで,$k$$b_{\dot{*}}(t)\in \mathrm{R}^{2}$$b_{:}$$\mathrm{R}$は実数の集合である.

人の選手 (Player) $P=\{p_{1},p_{2}, \cdots,p_{k}\}$ のたは各選手 . に対する連続なで速度の絶対値が常に定曲線乃 :[to, $tf$ ]をを越えないようなものである .1
数
スケジュール開始 (終了) 時間と呼ぶ. 各選手がめのスケジュール

$\mathrm{S}$$p_{1}$$arrow R^{2}$$v_{0}$$t\mathrm{o}(\iota_{f})$同じ開始 (終 7) 時間を持つことは問題への制約
1 各選手に異なる最大速度を持たせる方がより自然な定式化であろう. しかし, 3 節の結果が示すように, 本論文の定式化の下でも多くの問題は NP-困難である.

9とはならない. スケジュール $S$ によって捕球さかを判定し, もしも存在するならばそのスケれるボーノレの集合は $Cs=\{b_{i}$ : $(\exists pj\in F,$ $t\in$

ジュールを求める問題$[t_{0}, tf])b_{i}(t)=pj(t)\}$である. 多忙な外野手問題(Busy Outfielder Problem-BOP) は $|Cs|$ を化するようなスケジュール を計算する問題である. なお, 以下では一般性を失うこと無く $t_{0}=0$を仮定する .2
次節ですぐに説明するように, BOP は一般には-困難である. そこで, 以下の各節では, 選手の移動範囲を制約した上で BOP の時間計算量を議論する.
$S$(ii) 選手数 が与えられたときに, 捕球可能な最大ボール数およびそれを実現するスケジュ–
ルを求める問題$k$(iii) すべてのボールを捕球するために必要な最小選手数 およびそれを実現するスケジュ$k$

ルを求める問題$\mathrm{N}\mathrm{P}$3

選手が直線上を移動する場合

各選手 : が移動できる範囲を原点を通るある直線 (動作軸と呼ぶ) 上に限定する. スケジュ$p$

ル開始時点$t_{0}$

では, すべての選手

: が原点

$p$

$O$

に

集合していると仮定しても一般性を失わない. 選. 力 軸となす角 (動作角)
手乃の動作軸ををとする.
はボーノレをこの動作軸上でしか捕球できない. 図 1 は選手数 $k=2$ ,ボール数 $n=3$ の場合を示している.
$\mathrm{r}$$l_{1}.’\ell_{1}$$\theta_{1}.(0\leq\theta_{\dot{*}}<\pi)$$x$$p_{\dot{*}}$

問題 (ii) およひ (iii) は明らかに問題 (i) よりも容易ではない. 両者の間に実際に時間計算量の差があることを示すことも本論文の目的の一つである. 紙面の制約から証明は省くが,
完全問題
あるいは
である
からの還元によって以下の定理が証明できる.
$\mathrm{N}\mathrm{P}$$\mathrm{M}\mathrm{A}\mathrm{X}2\mathrm{S}\mathrm{A}\mathrm{T}$$3\mathrm{S}\mathrm{A}\mathrm{T}$定理 11. 問題 (i) は $k\geq 3$ の場合 NP-困難である. したがって, 問題 (iii) も NP-困難である.

($3\mathrm{S}\mathrm{A}\mathrm{T}$からの還元)

2. 問題 (ii) は $k\geq 2$ の場合 NP-困難である.
からの還元)($\mathrm{M}\mathrm{A}\mathrm{X}2\mathrm{S}\mathrm{A}\mathrm{T}$31

選手数 $k=1$ の場合

選手 の動作角 を任意に固定する. 動作軸があるボーノレ の軌道と一致する場合 [こは, は$\theta$$p$$b_{i}$$p$$b_{j}$

を必ず捕球できるかあるいは絶対に捕球できない
かどちらかであり, またそのどちらであるかを簡単に決定できる. そこで, 検討からこのようなボー
ルを外すことができるので, 動作軸はどのボール
とも一点で交わることを以下では仮定する.
選手 が捕球できるボール間の関係を表現する$p$

図 1: 選手の移動範囲が直線上に限られる場合

BOP を含む以下の三つのスケジューリング問
題を本節では検討する. 各選手乃の動作角度
は (入力の一部として与えられるものではなく)選手力墳由に決定できるものであり, その決定も$\theta_{i}$スケジューリングの一部である.

有向非サイクルグラフ (DAG) $G(\theta)=(V$, A(の)を以下で定義する: 頂点集合は $V=\{0,1, \ldots, n\}$である. 有向枝 $(i,j)\in A(\theta)$ であるための必要十分条件は, 1) $i=0$ かつボール を捕球できる$b_{j}$

力\searrow あるいは 2) ボーノレをこの順序で捕球できることである. 有向グラフの例を図 2に示す. 図から, たとえば, すべてのボールは直, はこの順序で捕球でき接捕球でき, ボー), はこの順序で捕球できないこるが, ボー)とが分かる. 動作軸とボールは一点でしか交わらは実際にないから, このように定義された$k$2

この事実は明らかではないが容易に証明できる.

と$b_{j}$$G(\theta)$$\text{レ}b_{2}$$\mathrm{s}b_{1}$(i) 選手数 が与えられたときに, すべてのボールを捕球するスケジュールが存在するかどう$b_{i}$$b_{4}$$b_{2}$$G(\theta)$

DAG である.

10である. 集合$d\leq v(t$を $\{(t, d):-v(t-t_{i})+d_{i}\leq$$D_{i}\subseteq \mathrm{R}^{2}$-t$d_{i}$} と定義する. 図 3 に $n=4$ のは点場合の例を図示する. たとえば,を捕球にラベル付けられており, 選手がボーノ
はを頂点とするした状況に対応する. 領域
二つの半直線によって切り取られた空間の原点を含まない部分である. bj\in Dj(あるいは同じこ$(t_{1}, d_{1})$$b_{1}$$\text{レ}b_{1}$$D_{1}$$b_{1}$$O$とだが DjD

図 2: 有向グラフ G(のの例

任△襪海箸 ボーノレを$b_{1}\cdot,$$b_{\mathrm{j}}$の順序で捕球できるための必要十分条件である.

動作角度 を持つ選手が捕球できる最命題 1に含まれる最長路の長さに大のボール数は$\theta$$f\mathit{8}f$$G(\theta)$等しい.

とすると, DAG の最長路問
題は $O(n+m)$ で解決できる. したがって, を変化させたときに現れるすべての DAG G(ののそれぞれに対して最長路問題を解くことで, 問題(i) と (ii) を解くことができる. 異なる DAG G(のの個数を評価する.
DAG に現れる可能性のある枝の種類の総数は$O(n^{2})$ であり, 一方, どの枝 $(i,j)$ についても, その枝が存在するような の極大区間の個数は $O(1)$で抑えられる. したがって, 以下の命題力城立する.

DAG の枝数を$m$$\theta$

図 3: 捕球時間と捕球位置の関係

ここで, 変換. $=vt_{i}-d_{i},$ $\beta:=vt|$. $+d$:$\alpha_{1}$$\theta$

命題 2[8] 動作角
なる DAG$G(\theta)$

を考える.
つ

を変化させたときに現れる異の総数は $O(n^{2})$ である.

$(\alpha_{j},\beta j)\leq(\alpha_{j}, \beta j)$$\beta j\leq\beta j$$\theta$

命題 1 と 2 を組み合わせれば, 問題 (i) と (ii) を時間で解決できる. 3.1 節の以下の部分では, 動作角 が与えられた場合に, DAG の最長路問題を経由せずに問題 (i) と (ii) を $O(n\log n)$ 時$O(n^{4})$$\{(\alpha_{i}, \beta:)

する.

を

.

$\alpha_{1}$$\leq\alpha j$かであることと定義することで, 集合
上 1 こ (半) 順序関係 を導入:

1\leq i\leq n\}$$\leq$$(\alpha|., \beta_{j})\leq(\alpha_{j}, \beta_{j})$かつ$(\alpha:, \beta_{i})\neq(\alpha_{j}, \beta_{j})$と書くものとする.
, \beta
このとき, 以下の命題が成立する.

のときに ($(\alpha j, \beta j)$$\alpha_{i}$$\theta$間で解決するアルゴリズムを与える. したがって,
命題 2 と組み合わせることで, 問題 (i) と (ii) を$O(n^{3}\log n)$ 時間で解決できる.
動作角 を任意に固定する. 容易に分かるように, $\theta=\pi/2$ を仮定しても一般性を失わない. ボー
ノレが動作軸と時刻 t こ座標 $b_{i}(t_{1}.)=(0, dj)$ で交差するとする. 選手 が時刻 に座標 (0, d
まが時刻
ボーノレ . を捕球したとする.

命題 31. ボール$b_{i}$

を捕球できるための必要十分条件は $(0, 0)\leq(\alpha j$ ,\beta

2. ボーノレ

任△.

をこの順序で捕球できるためのである.
必要十分条件は$b_{1}.,$$bj$$(\alpha j, \beta:)\leq(\alpha j, \beta j)$$\theta$$t_{i}$$b_{i}$$p$$b_{1}$$t_{i}$$p$$t(\geq t_{\dot{*}})$

でに移動し得る動作軸上の点 $(0, d)$ が満すべき必要十分条件は, が選手の最大速度であることに注意すると,$v$

したがって, 問題 (i),(ii) はこのようにして作られた半順序集合の最長鎖の長さを求めることに帰着される. 一方, 半順序集合について以下の命題が知られている.
命題 4[7] 半順序集合の最長鎖の長さは最小反鎖被覆数に等しい.
ボー

di-v(t-ti)\leq d\leq di+v(t-t$\mathrm{K}\text{レ}$

の集合

$S$

を考える. ボーノレ $b_{:}inS$ が $S$ でパレート最適であるとは,$(\alpha j, \beta j)>(\alpha:, \beta_{i})$を

11
みたすようなボーノレ $b_{j}\in S$ が存在しないときでえられているとする. このとき問題 (i) の時間計

ある. また, 集合 $S’\subseteq S$ が $S$ のパレート最適集

算量は $O(n^{2})$ である,

合であるとは,$S’$

適であり, かつのすべてのボーノレがパレート最をみたすボー$(\alpha_{i)}\beta_{i})=(\alpha_{j}, \beta j)$

が存在しないことである. 最小反鎖被覆
は, ボールの全集合 $B$ から始めて, 最大のパレール$b_{\dot{*}},$$b_{j}$

ト最適集合をつぎつぎに取り除いて行くことにより求めることができることが知られている.
図 4 に変換された後の各を例示している. こ$b_{j}$

がの例では, 最大パレート最適集合の最小反鎖被覆になっており, したがって, 最長のそれぞれについて, 動作角を変化させた場合に現れる異なる DAG は $O(n^{2})$ 通り
あるから, 以下の系が成立する.
$G(\theta_{1}),$$G(\theta_{1})$系 1 選手数 $k=2$ の場合, 問題 (i) の時間計算量
は $O(n^{6})$ である.

$B$

$S_{1},$ $S_{2},$ $S_{3}$3.3

すべての選手が同一の動作軸上を移動する
場合

鎖の長さは 3 である.

定理 1 から, 3 人以上の選手を扱う場合には問題$\beta$.

$\ldots\ldots..d\circ\circ:|\mathrm{b}_{\tilde{3}}^{\sim}\cdot\backslash$$\ldots\ldots..’|\backslash$.

.

$\dot{|||}\dot{\mathrm{b}}_{\tilde{3}^{\backslash }}^{\sim}\backslash \backslash$$\mathrm{i}|\mathrm{I}$.‘-..–‘.i;‘.
、.
$1$$\ldots..---$$\backslash .\backslash ^{1}\sim \mathrm{t}^{\mathrm{I}}$$|\grave{\mathrm{b}}_{7^{\backslash }}^{\backslash }\backslash |\backslash$

:

.

.

$\cdot$$|\backslash -\cdot\cdot--\tau_{\mathrm{I}}\backslash \backslash \backslash \cdot$$\sim.\cdot.\mathrm{I}\prime \mathrm{l}$$|$$\backslash \backslash \backslash$$.*\cdot.\backslash ..\mathrm{I}$$.\cdot.\cdot.\cdot.\cdot.\cdot\acute{\iota}_{\mathrm{p}\cdots\{}.\prime^{---}\backslash \cdots$

1

’

:

$\backslash$$\mathrm{b}$.

$\mathrm{b}_{5_{1}^{\grave{\backslash }}}$$|,|.5_{1}^{\backslash }|\backslash$$1.:_{\vee-}^{\mathrm{r}}..$’$\mathrm{S}_{1}$$.\cdot.\cdot.\cdot.\cdot.\cdot\acute{|}\mathrm{r}_{\backslash }..\cdot.\cdot..\cdot.\mathrm{b}..\mathrm{i}^{\mathrm{e}_{\backslash }^{\backslash }\cdot:_{\vee-\vee}\prime}\prime^{---\sim}\backslash \backslash \cdot\cdot.\backslash \cdot\backslash \cdot\backslash \cdot..\cdot.-\cdot.\cdot \mathrm{S}_{1}$$|$$\backslash \backslash \backslash$$|||\mathrm{b}_{\mathrm{J}}^{1}$$\lfloor$......

:$\backslash ^{\mathrm{I}}.\backslash ..\mathrm{I}\backslash \backslash ^{\mathrm{I}}\mathrm{l}$,$\mathrm{b}_{4^{\backslash _{1}}}^{\backslash \mathrm{l}}$のいずれもが$\mathrm{N}\mathrm{P}$-困難であった. そこで本節では, すべての選手が同一の動作軸上を移動する場合に各問題の時間計算量を考察することにする. まず, 最小反鎖被覆数のアイデアを用いることにより, 定理 2 の系として以下が得られる.

$:^{-}$$\ldots..--\cdots\backslash \sim\backslash \backslash -\cdot$$(\mathrm{i})-(\mathrm{i}\mathrm{i}\mathrm{i})$$|$$||$

$|$

$|$

$|$

.
.
:. : ..

$|!.\backslash ^{1}\backslash ||$$\ldots\ldots..\backslash ..\cdot.\cdot.\cdot..\cdot \mathrm{b}_{4_{\dot{\mathrm{t}}}^{\backslash }}^{\backslash }\backslash \backslash \backslash \iota.\cdot\iota\sim\cdot\cdot’-\cdot.\mathrm{s}_{2}..\cdot.$$|$$||\iota.\cdot\sim.-\cdot..\cdot\cdot\prime \mathrm{I}’($$|\mathrm{I}$

$||$

1

系 2 動作角 が与えられたとき, (\rfloor 約された)問題 (iii) の時間計算量は $O(n\log n)$ である. したがって, (同じ条件の下で) 問題 (i) の時間計算量も $O(n\log n)$ である.

$|\mathrm{I}$$\theta$$\mathrm{I}\mathrm{I}\mathrm{s}_{2}$$\mathrm{I}\mathrm{I}$$|$$||$$|$$\cdot$$\mathrm{I}\mathrm{I}$$|$$.\cdot...||.\cdot$$.\cdot.\cdot\iota’..\cdot.\mathrm{B}_{\tilde{2}}..\backslash \backslash \cdot\backslash \cdot \mathrm{b}_{\dot{\beta}}..\cdot..\cdot$

.

,

.

$.\cdot.\cdot\iota’....\cdot..\mathrm{B}\backslash \cdot\backslash \sim_{-\prime}\tilde{.}2^{\backslash }....\mathrm{b}$$\mathit{1}\mathrm{s}_{1}.\mathrm{l}|$..

$^{\mathrm{N}}3||$$|$$.\cdot$$|$$|$$\cdot$$\sim_{-\prime \mathrm{s}_{3}}.\cdot’..\cdot$$|$$\cdot$
$|$

.

$|..$
$|$

$|$

$\alpha$

図 4: 変換後の半順序集合とその反鎖分割

命題 2 と組み合わせると, 動作角が与えられていない場合には, (制約された) 問題 (i),(iii) の時

AVL 木のような平衡木を用いれば, パレート最適集合は 1 点あたり $O(\log n)$ , 合計 $O(n\log n)$ で間計算量はともに $O(n^{3}\log n)$ である. 以上のア
イデアは (制約された) 問題 (ii) に対しては働かない. そこで, この問題を最小コストフロー問題

計算できる. 以上をまとめる.

に帰着する.
動作角が与えられたとき, ネットワーク$\theta$が与えられたとき, 問題 (i),(ii)の時間計算量はともに $O(n\log n)$ である.

定理 2 動作角

32$\theta$$N(\theta)=(W, E)$

定理 1 で問題 (ii) は選手数が 2 以上ならば NP-

困難であることを述べた. したがって, 二人の選手 $P1,P2$ のための動作角を固定した場合にも問題は依然として-困難である. そこで対象を問題 (i) に絞る. 動作角をを固定すると,$\theta_{1},$$\theta_{2}$$\mathrm{N}\mathrm{P}$$\theta_{1},$3.1 節で導入した DAG

ここで,$2\mathrm{S}\mathrm{A}\mathrm{T}$を経由して,に帰着するこ$N(\theta)$

定理 3[

選手数 $k=2$ とし, 動作角$\theta_{1},$$\theta_{2}$が与: demand(u):

$\{$

である.

である.

$k$

0

,
,

,

$E_{2}$に対する次の$\min\sum c_{\mathrm{e}}x_{\epsilon}$$-k$$\mathrm{H}_{\ell}\mathrm{R}$: $1\leq$

1 \leq i\leq n\}$1\leq i\leq n\}$に属する枝を内部枝とよぶ.
最小コストフロー問題を考える.

日的関数 :か: $(i,j)\in A(\theta),$ $1\leq$$=\{(i^{-}, i^{+}) :$=\{(s, i^{-}), (i^{+},t) :とができる.
$\mathit{9}f$E2$i^{+}$$E=E_{1}\cup E_{2}\cup E_{3}$$E_{1}=\{(i^{+},j^{-})$$i,j\leq n\}$ ,$E_{3}$$W=\{i^{-},$$\theta_{2}$$G(\theta_{1}),$ $G(\theta_{1})$問題 (i) はサイズが $O(n^{2})$ の$G(\theta)=(V, A(\theta))$$\mathrm{D}\mathrm{A}\mathrm{G}$ら以下のように構成する.
$i\leq n\}\cup\{s,t\},$

遍手数 $k=2$ の場合

を

$u=s$
$u=t$

その他

12
枝

意に固定し, この条件の下で必要な最小速度 w(のを計算することから始める. 3.1 節で述べた理由から, すべてのボールは動作軸と一点で交わると仮定しても一般性を失わない. 一方, どの二つのボールも動作軸と同じ時刻に交わらないような動作角 が常に存在するから, はこの条件を滴足すると仮定しても一般性を失わない.
任意の $0\leq i,$ $j\leq n$ に対して, 二つのボールをこの順序で捕球するために必要な最小速とする. ただし, 捕球できない場合に度をは $fjj(\theta)=\infty$ と定義する. あきらかに,

1$0\leq x_{e}<$-1,cost(e) $-\{$
0,

$e$

が内部枝

$..$

その他

$\theta$$\theta$$b_{\dot{*}},$$bj$$f_{ij}(\theta)$

図 5: 図 2 に対応するフローネットワーク $N$ (の$f_{\dot{\iota}j}(\theta)<\infty\Leftrightarrow f_{ji}(\theta)=\infty$

図 5 は図 2 に対応するネットワークである. ソーのフローが流れ出だし, シンクのフローが集まる. 各枝の容量はに同じ大きさ1 であるから, フローの整数性から から に

ス $s$ から大きさ$k$$B)/CT^{2}+DT+E$ と表現される. ここで, $T=$$\tan$ (のである. $w_{jj}( \theta)=\min\{f_{jj}(\theta), f_{ji}(\theta)\}$ と定.,はボーノをともに捕球す
義すると,本の有向道ができ, 各道が各選手の移動経路に対応する. cost は内部枝をフローが流れたときのみ減少するので, cost の総和の絶対値は選手が捕球するボールの総数に対応する. このネットワーク
に対する最小コストフロー問題は容量スケーリン
グ法により $O(n^{3})$ 時間で解くことができる $[2, 3]$.

定理 4 選手数 $k\geq 2$ とする. 動作角 が与えられたとき, (fflJ 約された) 問題 (ii) の時間計算量は$\theta$$O(n^{3})$を用いて $f_{1j}.(\theta)=\sqrt{1+T^{2}}(AT+$$A,$ $B,$ $C,$ $D,$ $E$

$k$

$t$

は簡単に計算でき, 有限の場合には定数

$t$

$k$

$s$

$f_{ij}(\theta)$である.

$w_{ij}(\theta)$$\text{レ}b_{*}$$b_{j}$

るために必要な最小速度である. このとき,$v_{m1n}.= \min\{\max w_{1j}.(\theta)\}$$\theta$である. すなわち ,$i,j$は, $O(n^{2})$ 本の曲線 wij(のの上側エンベロープの最小値である.
の表現から, 任意の二つの曲線は高々 6 点で交わり, したがって, 二つの曲線$v_{\min}$$fjj(\theta)$$f_{1j}.(\theta)$

は高々24 点で交わることが証明できる.
は $O(n^{2})$ 個 $.\#$ 在するので, 上側異なる
個の $wjj(\theta)$ 達のエンベロープは高々$w_{ij}(\theta)$$w_{1j}.(\theta)$

3 節で得た結果を表 1 にまとめた. 動作軸欄が共通の行は, すべての選手が一つの動作軸を共有する場合の結果であり, 3.3 節で検討した. 固有の行は各選手が異なる動作軸を取ることが可能な場合である. 表 1 の結果は動作角が与えられた場合のものである. したがって, 動作角が与えられていない場合には, 動作角の候補が動作軸 1 本につき $O(n^{2})$ 個あるのでそのことを考慮しなければならない. なお, 問題 (i) は選手数 $k=1$ の場合,
動作角が与えられていなくとも $O(n^{2}\log n)$ 時間
で解決できる [8].

4$O(\lambda_{24}(n^{2}))$断片から構成されている. ここで,$O(n^{2}2^{O(A(n^{2})^{11})}),$ $A$ はアッカーマン関数の逆関である [1]. 上側エン
数であり.
$\lambda_{24}(n^{2})=$$\lambda_{24}(n^{2}\rangle\simeq O(n^{2})$ベローブの各関数の極大連結部分を左から右にソートした順に求めるのに $O(\lambda_{24}(n^{2})\log n)$ が必
要なので,の時間計算量は $O(\lambda_{24}(n^{2})\log n)$$v_{\min}$$\simeq O(n^{2}\log n)$定理 5 全球捕球のために必要な最小速度 vmin は$O(\lambda_{24}(n^{2})\log n)\simeq O(n^{2}\log n)$ 時間で計算できる.

全球捕球のための最小速度
本節では, 一人の選手がすべてのボールを捕球するために必要な最小速度 v。in を求めるアルゴ
リズムを検討する. き続き, 選手が移動可能な領域を原点を通る直線上に制限する. 動作角 を任$\xi|$$\theta$となる [6].

13
表 1 移動範囲が直線上に限られる場合の結果

5

すぺてのボールが同じ速度ベクトルを持つ場合
3 および 4 節では選手の移動範囲を直線上に制約した. 本節では, この制約を取り除き, 選手は平面内の任意の地点に移動できるものとする. ほと-困難であるから, 本節では, すべてのボールが同じ速度ベクトルを持つという仮定を導入する. 一般性を失うことなく, すべての
ボーノ
は架軸と並行に下に向かって速度 (ベク$=(0,-cv)$ で落ちてくると仮定する. こトル)vj
こで, $c\geq 1$ は定数, は選手の最大速度である(図 6).
んどの問題が$\mathrm{N}\mathrm{P}$$\triangleright bj$$v$

捕球できることを示す.

容易に分かるように, 3.1 節と同様に, $G$ の最長路の長さが選手数 $k=1$ の場合に捕球できるボール数の最大値であり, 最小反鎖被覆数を求める問
題に帰着することで $O(n\log n)$ で求めることができる. この場合には, 対象となる DAG はだけであるから, 問題 (i),(ii) を ( Iog ) 時間で解決
$G$

$O$

$n$

$n$

できたことになる.

複数の選手を取り扱う場合にも 3 節で述べたア
イデアを応用できる. 紙面の制約から, 証明を省

き, 各問題に対する結果だけを表 2 にまとめておく. 選手の初期位置が共通でなければならないか,
それとも異なっていても良いかによって計算量が-困難であった問題が表 2
変化する. 表 1 では
では多項式時間を持つことに注意せよ. これは, 3
節では, 動作角が与えられた後においても, 各選
手 p- ごとに異なる DAG G(\mbox{\boldmath $\theta$} 鯊仂櫃箸靴涜弍
する問題を検討する必要があったのに対して, 本$\mathrm{N}\mathrm{P}$節では, 初期位置の相違はあるものの, すべての$pi$が本質的には同じ DAG $G$ を持つものとして問題を検討すれば十分であることに起因している.

6
図 6: すべてのボールが等速度で下に向かって落

ちてくる場合すべてのボールの速度ベクトルが等しい場合には, 時間の経過にともなうボール同士の位置関係には変化がない. したがって, あるボールを捕球する時刻や位置は考慮する必要がな , 捕球するか否かだけが重要となる. この事実から, 3.1 節
で述べたような DAG $G=(V, A)$ を構成することができる. すなわち, $V=\{0,1, \ldots, n\}$ であり,$(i, j)\in A$ はボールがこの順序で捕球できることを示す. ただし, $(0, i)\in A$ はボーノレ が$\langle$$b_{1}.,$$bj$$b_{i}$

おわりに

本論文では, 多忙な外野手問題 (Busy Outfielder Problem-BOP) を定式化し, 様々な部分
問題の時間計算量をあきらかにした. 選手に移動範囲が直線上に限られる場合を特に綿密に考察し, BOP を含む三つの問題のすべてについて, 多
項式時間アルゴリズムと NP-困難性の証明のいずれかを与えた.

以上の考察から得られた一般的な結論は, 選手の移動範囲に与えた強い制約に関わらず, 3 名以
上の選手を対象とする場合は考察したすべての問-困難となるということであった. 一方,
題がBOP の応用においては, 選手の移動範囲の制約がそぐわないものが多くあると考えられる. そこで, 移動制約を伴わない BOP をすべてのボール$\mathrm{N}\mathrm{P}$14
表 2: すべてのボールが同じ速度ベクトルを持つ場合が同じ速度ベクトルを持つという制約のもとで検討した.
残された大きな問題としては, 選手の初期位置決定問題がある.

参考文献[1] P. K. Agarwal, M. Sharir and P. Shor Sharp
Upper and Lower Bounds for the Lengthof General Davenport-Schinzel Sequences,
Journal of Combinatorial Theory, Series$\mathrm{V}\mathrm{o}\mathrm{l}.52(1989),$$\mathrm{p}\mathrm{p}.228-274$$\mathrm{A}$,.

[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows :Theory, Algorithms
and Applications, (Prentice-Hall; 1993).
[3] W. J. Cook, W. H. Cunningham, W. R.
Pulleyblank and A. Schrijver, Combinatorial
Optimization, (John Wiley&Sons, 1998).

[4] M. Hammar and B. J. Nilsson, Approimation results for kinetic variants of $TSP$,LNCS 1644, pp.392-401, 1999.

[5] C. S. Helvig, G. Robins, and A. Zelikovsky,
Moving Iarqet $TSP$ and Related Problems,
LNCS 1461, pp.453-464, 1998.
[6] 今井浩, 今井桂子, 計算幾何学, (共立出版,
1994).
[7] L. Loviz and M. D. Plummer, Matching
Theory, Annals of Discrete Matghematics,

29, (North-Holland, 1986).
[8] 佐久間, 朝廣, 宮野, 山下, 「直線上を移動するロボットによるボール回収アルゴリズム」 ,火の国情報シンボジウム, p.71-76,2001.
次[9] 佐久間, 山下, 朝廣, 亀田, 牧野, 宮野,
元上を移動する複数台ロボットによるボール$\mathrm{r}_{1}$回収問題」 , 2001 年度冬の予稿, pp. 2.1-2.4.

$\mathrm{L}$A シンポジウム