Mathematical Analysis of Search Problems on Finite Graphs

在有限图上的搜索问题中，在初始位置未知的情况下，通过数学分析计算博弈的价值，找到最优策略。此外，通过全面思考图上的搜索问题，我们应用了合作博弈的核心，考虑通过合并重新分配搜索成本的节省。我们开始了一个新的分析搜索问题与非加性成本。另一方面，我们制定了一个两个人的零和游戏与多步之间的恐怖分子和运输船的侦察问题，并在分布式系统中的故障查找的应用。运输船配备一艘侦察艇来发现和排除水雷，必须确定何时发放侦察艇，这样成本就较小。我们考虑了两种情况，这取决于恐怖分子如何以及何时布设地雷。

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.