Mathematical Studies on Optimal Solutions for Search Problems on Graphs

图搜索问题最优解的数学研究

• 批准号: 13680525
• 负责人: KIKUTA Kensaku
• 金额: $ 2.05万
• 依托单位: Kobe University of Commerce
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680525/
• 关键词: Search Problem; Game Theory; Optimal Strategy; Two-Person Game; Analytical Method; Distributed System; 経営科学の手法

In this project, we studied mathematically four models related to search problems.(1)Search games with switching cost and examination, cost,(2)The quiet accumulation game on a linear graph,(3)Rendezvous search on a graph,(4)Search games related to probe complexity in quorum systems.For the model (1), we have got optimal strategies of the seekr when the underlying graph is cyclic, and this result will be published. For the model (2), we solved the cases when the number of nodes is small and gave bounds for the value of the game by considering special search strategies for both players. For the model (3), we have been studying optimal strategies for the both players when the underlying graph is star-shaped. For the model (4), we got optimal strategies for the both players when the underlying graphs are wheel-shaped, etc. and gave a talk at the annual meeting of the Operations Research Society of Japan.

在这个项目中，我们从数学上研究了与搜索问题相关的四个模型。（1）具有转换成本和检查成本的搜索博弈，（2）线性图上的安静积累博弈，（3）图上的Renaissance搜索，（4）quorum系统中与探测复杂度相关的搜索博弈.对于模型（1），我们得到了当底层图是循环图时搜索者的最优策略，这个结果将被发表.对于模型（2），我们解决了节点数较少的情况，并通过考虑双方的特殊搜索策略给出了博弈值的界。对于模型（3），我们一直在研究当基础图是星形时双方的最优策略。对于模型（4），当基础图为轮形等时，我们得到了双方的最佳策略，并在日本运营研究学会年会上发表了演讲。

项目成果

W.Ruckle, K.Kikuta: "Special Classes of Quiet Accumulation Games"Journal of the operations Research Society of Japan. Vol.46,No.4. 487-502 (2003)

W.Ruckle、K.Kikuta：“安静积累游戏的特殊类别”日本运筹学会杂志。

K.Kikuta: "Totally Reasonable Outcomes in a Cooperative TU Game"商大論集. 55・5. 421-436 (2004)

K. Kikuta：“合作 TU 博弈中的完全合理结果”商业大学评论 55・5（2004 年）。

K.Kikuta: "A Search Game on a Cyclic Graph"数理解析研究所講究録. 1207. 114-127 (2001)

K. Kikuta：“循环图上的搜索游戏”数学科学研究所 Kokyuroku。1207. 114-127 (2001)

H.Kawakatsu, K.Kikuta et al.: "Bayes Solution to Dynamic Perishable Inventory Problem with Two Types of States"Scientiae Mathematicae Japonicae. 54巻3号. 583-594 (2001)

H.Kawakatsu、K.Kikuta 等人：“具有两种状态的动态易腐烂库存问题的贝叶斯解决方案”Scientiae Mathematicae Japonicae，第 54 卷，第 3. 583-594 期（2001 年）

V.Baston, K.Kikuta: "An Inviltration Game with Two Cables"RIMS Kokyuroku. 1252. 34-40 (2002)

V.Baston、K.Kikuta：“两根电缆的入侵游戏”RIMS Kokyuroku。