サーチライト・スケジューリング問題

• Item type: SIG Technical Reports(1)
• 公開日: 1988-11-25
• タイトル: サーチライト・スケジューリング問題
• タイトル / 言語: en
• タイトル: THE SEARCHLIGHT SCHEDULING PROBLEM
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学
• 著者所属: Univ. of Hawaii at Manoa
• 著者所属: Univ. of Wisconsin - Milwaukee
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical Engineering, Faculty of Engineering, Hiroshima Univ.
• 著者所属(英): en
• 著者所属(英): Dept. of Information and Computer Sciences, Univ. of Hawaii at Manoa
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical Engineering and Computer Secience, Univ. of Wisconsin - Milwaukee
• 著者名: 山下, 雅史; 杉原, 一夫; 鈴木, 一郎
• 著者名(英): Masafumi, Yamashita; Kazuo, Sugihara; Ichiro, Suzuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，二次元単純閉領域内を逃げ回る泥棒を幾つかのサーチライトで見つける問題について考察する．サーチライトは固定された位置にあり，一本の光線を発している．光線は領域内の境界を突き抜けることはできないが，光線の方向は連続的に変えることはできる．ある時間に泥棒が発見されるのはサーチライトの光線がその泥棒上にあるとき，また，その時に限る．泥棒は速度制限無しで連続的に移動できる点と見なす．目的は与えられたインスタンスにおいて，泥棒がとのように移動するかにがかわらず，泥棒を発見するための探索スケジュールが存在するがどうかを決定することである．与えられた領域の境界上に少なくとも1つのサーチライトがあるようなインスタンスに対する探索スケジュールを求める問題は境界上にサーチライトがないの場合に帰着させることができることを示す．また，探索スケジュールが存在するための十分条件も示される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the problem of searching for a mobile robber in a closed simple two-dimensional region by a number of searchlights. A searchlight is a stationary point which emits a single ray. The ray cannot penetrate the boundary of the region, but its direction can be changed continuously. A point is detected at a given time iff it is on the ray of a searchlight. A robber is a point which can move continuously with unbounded speed. First we show that the problem of obtaining a search schedule for an instance having at least one searchlight on the boundary of a given region can be reduced to that for instances having no searchlights on the boundary. The reduction is achieve by recursive application if a simple search starategy called One-Way Sweep Strategy. Additional sufficient conditions for existence of search schdule are also presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1988, 号 87(1988-AL-004), p. 1-8, 発行日 1988-11-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会