Mathematical Studies on Optimal Solutions for Search Problems on Graphs

在这个项目中，我们从数学上研究了四个与搜索问题相关的模型。(1)具有切换代价和检查代价的搜索博弈；(2)线性图上的安静积累博弈；(3)图上的会合搜索；(4)仲裁系统中与探针复杂度相关的搜索博弈。对于模型(1)，我们得到了底层图为循环时的最优寻优策略，并将结果发表。对于模型(2)，我们通过考虑双方玩家的特殊搜索策略，解决了节点数量较少的情况，并给出了博弈值的边界。对于模型(3)，我们一直在研究底层图为星形时双方的最优策略。对于模型(4)，我们在底层图为轮状等情况下得到了双方的最优策略，并在日本运筹学学会年会上发表了演讲。

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.