Mathematical Studies on Optimal Decisions for Search Problems on Finite Graphs

有限图搜索问题最优决策的数学研究

• 批准号: 17510131
• 负责人: KIKUTA Kensaku
• 金额: $ 2.39万
• 依托单位: University of Hyogo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17510131/
• 关键词: Search Problem; Game Theory; Optimal Strategy; Two-Person Game; Analytical Method; Distributed System; Network; システム工学; ランデブー探索; 最小点被覆集合; 自己安定近似アルゴリズム

In this project, we studied mathematically four models related to and around search problems.(1) Search problems with switching cost and examination cost,(2) The quiet accumulation game on a finite graph,(3) Rendezvous search on a graph,(4) distributed system.For the model (1), we have studied optimal strategies of the seeker when the underlying graph is complete, and the examination costs and switching costs are high or low. We gave a talk at the annual meeting of the Operations Research Society of Japan. For the model (2), a paper has been published in which the underlying graph is linear and we gave bounds for the game value, and we studied in detail when the number of nodes is small. For the model (3), we studied rendezvous search on a star graph, and a paper has been published. For (4), we gave a talk at an international meeting.

在这个项目中，我们从数学上研究了与搜索问题相关的四个模型。(1)具有切换代价和检查代价的搜索问题，(2)有限图上的安静积累博弈，(3)图上的交会搜索，(4)分布式系统。对于模型(1)，我们研究了底层图完备、检查成本和切换成本高或低时寻道者的最优策略。我们在日本运筹学学会的年会上作了报告。对于模型(2)，已经发表了一篇论文，其中底层图是线性的，我们给出了博弈值的边界，我们详细研究了节点数较少时的情况。对于模型(3)，我们研究了星图上的交会搜索，并发表了一篇论文。为了(4)，我们在一个国际会议上作了报告。

项目成果

Brief announcement : An efficient and self-stabilizing link formation algorithm

简短公告：一种高效且自稳定的链接形成算法

• 发表时间: 2006
• 期刊: A.K. Datta and M. Gradinariu (Eds.) : SSS 2006 LNCS 4280
• 作者: Jun Kiniwa;Kensaku Kikuta
• 通讯作者: Kensaku Kikuta

ambushゲームとその周辺

伏击游戏和环境

• 发表时间: 2006
• 作者: Toichi;SAWADA;Takafumi;KAWAKAMI;Mitsuru;YAMAGUTI;Toshiya;HIROSE;木庭 淳;菊田 健作
• 通讯作者: 菊田 健作

Rendezvous search with examination cost on a finite graph

有限图上具有检查成本的会合搜索

• 发表时间: 2005
• 期刊: 京都大学数理解析研究所講究録 (掲載予定)
• 作者: W.Ruckle;K.Kikuta
• 通讯作者: K.Kikuta

The Quiet Accumulation Game of a Linear Graph: A Special Case

线性图的安静积累博弈：一个特例

• 发表时间: 2007
• 期刊: I Game Theory and Applications 12
• 作者: 山田健太郎;Abdullah Zawawi;澤田東一;K.Kikuta and W.Ruckle
• 通讯作者: K.Kikuta and W.Ruckle

直線上あるいは空間での探索ゲーム

直线或太空探索游戏

• 发表时间: 2007
• 期刊: 数理解析研究所講究録 1548
• 作者: 澤田東一;広瀬敏也;春日伸予;銭谷真拓;菊田 健作
• 通讯作者: 菊田 健作