Mathematical Studies on Optimal Decisions for Search Problems on Finite Graphs

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

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.