2017 旭硝子財団 助成研究発表会 要旨集

143/223

が指定される場合もある）．離散的な選択肢をもつスケジューリングは古典的な問題であるし，図形全体をカバーする被覆問題も様々な設定で扱われているが，時間的・空間的に「満遍なく」訪れるという，言わば両者の融合した要求に対しては，このように単純な問題であっても従来あまり解析が進んでいなかったのである．単なる線分を警邏するなど極めて基本的な場合にさえ，最適解は非自明な複雑さを呈することが既にわかっていた． 図2 複数人が協力して，すべての点を，時間間隔を空け過ぎずに訪問することを目標とする「警邏問題」． そこで本研究では計算問題としての容易さ・困難さを分類することを目指した．すなわち標準的な貪慾法，動的計画法，近似手法を用いるための部分構造最適性を持つのは如何なる場合か，また逆に，知られているNP完全問題や更に強い意味で近似不可能な問題と同等の困難度を持つのは如何なる場合かを調べた． この問題についてもやはり，扱う入力や解が実数データであることによる難しさを排除する必要があった．すなわち，各人がいつどこで動きを変えるか一般には簡潔に表せない実数無限の可能性がある問題設定を，一定の条件下においてうまく離散的な状況に言い換えることで，スケジューリングや被覆問題で知られる古典的な手法を適用できた．中でも第二年度の研究［11］では，グラフ（辺点図）の各頂点を複数の巡査が複雑に協力して警備するという，先行研究では扱えなかった場合の複雑さを分析した．また警邏の空間的移動に関する側面を除き，保守の対象を離散的にした問題［10］も分析した．これを含め現在までの状況や未解決の課題について数回発表し［7，12，13］，周辺分野の研究者から一定の注目を得られたので，今後も共同研究の形で発展させたい． 2.3 その他 以上は当初から主に予定した題材だが，研究を進める中で新たに取組んだ問題について次の結果も得た． ・グラフの頂点上のモノの配置を並べ替える問題について，多項式時間で解ける状況と困難性を呈する状況の境界を示す結果［6，9］． ・紙に書かれた幾つかの点を，紙を折ることで望む通りに重ねる効率的な方法に関する結果［5］． 3. 今後の展開（計画等があれば） 本研究で取組んだ幾つかの問題は，以上のように「遮光」「警邏」などの譬え話で述べると異なる内容に聞えるが，いずれも多くのモノ（壁の断片や，複数の巡査）が共同で何かを被覆する目標に対し，それぞれが単独での貢献を増やすことと，全体での協力による効果を高めようとすることとが，ジレンマをなす状況の正確な解析を目指している．この共通点をうまく切り出し，同様の状況の解析に広く使える一般的原理を抽出できれば，他にも多くの図形被覆問題の解析に役立つであろう． 4. 参考文献 ［1］A. Dumitrescu and M. Jiang. The opaque square. In Proc. 30th SoCG, 529-538, 2014. ［2］A. Dumitrescu and C.D. Tóth. Computational Geometry Column 59. ACM SIGACT News, 45(2), 2014. ［3］T. Izumi. Improving the lower bound on opaque sets for equilateral triangle. Disc. Appl. Math., 213, 130-138, 2016. ●本助成研究にかかわる論文発表 ［4］A. Kawamura, S. Moriyama, Y. Otachi and J. Pach. A lower bound on opaque sets. In Proc. 32nd SoCG, LIPIcs 51, Article 46, Boston, USA, June 2016. ［5］Y. Asao, E. Demaine, M. Demaine, H. Hosaka, A. Kawamura, T. Tachi and K. Takahashi. Folding and punching paper. Journal of Information Processing, to appear. ［6］K. Yamanaka, E.D. Demaine, T. Horiyama, A. Kawamura, S. Nakano, Y. Okamoto, T. Saitoh, A. Suzuki, R. Uehara and T. Uno. Sequentially swapping colored tokens on graphs. In Proc. 11th WALCOM, LNCS 10167, 435–447, Hsinchu, Taiwan, March 2017. ［7］河村．最適の警邏に関する諸問題．研究集会「最適化技法の最先端と今後の展開」．京都府京都市，平28・8．数解研講究録（平29）． ●本助成研究にかかわる口頭発表 ［8］河村．塀の警邏．スケジューリングシンポジウム．東京都渋谷区，平27・9． ［9］山中，ドメイン，堀山，河村，中野，岡本，斎藤，鈴木，上原，宇野．シーケンシャルな交換による色付きトークン整列問題の計算複雑さ．信学COMP研．石川県金沢市，平28・6． ［10］E. Ando, A. Kawamura, M. Kiyomi, E. Miyano and H. Ono. Logging with maximum length constraint. Presented at 19th WAAC, Hakodate, Japan, Aug. 2016. ［11］河村，能城．複数の巡査による指定地点の警邏について．電子情報通信学会コンピュテーション研究会．徳島県徳島市，平28・9． ［12］A. Kawamura. Open problems on optimal patrolling. KAIST Computer Science Colloquium. Daejeon, Korea, Oct. 2016. ［13］A. Kawamura. Open problems on optimal patrolling. Presented at 8th GRASTA, April 2017. 5. 連絡先 kawamura@graco.c.u-tokyo.ac.jp http://www.graco.c.u-tokyo.ac.jp/~kawamura/ −133−