Mathematical Analysis of Search Problems on Finite Graphs

有限图搜索问题的数学分析

• 批准号: 23510177
• 负责人: KIKUTA Kensaku
• 金额: $ 3.33万
• 依托单位: University of Hyogo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23510177/
• 关键词: 探索理論; 最適戦略; ゼロ和ゲーム; システム工学; ネットワーク; 数理工学; モデル化; ゲーム理論

In a search problem on a finite graph, we calculated the value of the game and found the optimal strategies by mathematical analysis in the case where the initial position of the searcher has not been identified. In addition, by thinking in a comprehensive manner search problems on a graph, we applied the core of a cooperative game, considering the redistribution of savings of search costs through consolidation. We started a new analysis of a search problem with a non-additive cost. On the other hand, we formulated as a two-person zero-sum game with multi-steps a reconnaissance problem between the terrorist and the transport ship with an application to fault-finding in a distributed system. Transport ship is equipped with a reconnaissance boat to discover and remove the mines, and it must determine when to issue a reconnaissance boat so that the cost is smaller. We considered two cases, depending on how and when the terrorist sets the mine.

在有限图上的搜索问题中，我们在搜索者初始位置尚未确定的情况下计算博弈值，并通过数学分析找到最优策略。此外，通过在图上综合思考搜索问题，我们应用了合作博弈的核心，考虑通过整合节省的搜索成本的重新分配。我们开始对具有非累加成本的搜索问题进行新的分析。另一方面，我们将恐怖分子和运输船之间的侦察问题表述为多步骤的两人零和博弈，并应用于分布式系统中的故障查找。运输船配备侦察艇来发现和清除水雷，必须确定何时发出侦察艇，这样成本更小。我们考虑了两种情况，具体取决于恐怖分子埋设地雷的方式和时间。

项目成果

グラフ上の探索問題の合成について

关于图搜索问题的组合

• 发表时间: 2012
• 期刊: 京都大学数理解析研究所講究録
• 作者: R.Fokkink;L.Geupel and K.Kikuta;根本 俊男;矢野均;唐鎌考寛,開沼泰隆;菊田健作
• 通讯作者: 菊田健作

A Search Problem on a Finite Network with Traveling and Examination Costs

具有旅行和考试成本的有限网络上的搜索问题

• 发表时间: 2011
• 作者: X. Huang;J. Xu;S.Wang;C. Xu;Hitoshi Yano and Kota Matsui;K. Kikuta
• 通讯作者: K. Kikuta

分散システム故障回復への応用を考慮した効率的機雷探索

考虑应用于分布式系统故障恢复的高效矿山搜索

• 作者: 木庭淳;菊田健作
• 通讯作者: 菊田健作

協力ゲームのシャプレー値の変形

合作博弈的 Shapley 值的变化

• 作者: 2.Xu;C.;Huo,YL;Osaka;K.;菊田健作
• 通讯作者: 菊田健作

文科系のゲーム理論

文科博弈论

• 发表时间: 2012
• 作者: 2.Xu;C.;Huo,YL;Osaka;K.;菊田健作;菊田健作
• 通讯作者: 菊田健作