Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
复制标题
DOI：
10.1609/aaai.v36i4.20290
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
T. Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Y. Otachi
中科院分区：
文献类型：
--
作者：
T. Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Y. Otachi
最近，在组合问题中寻找不同的解决方案受到了相当大的关注（Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021）。在本文中，我们研究以下类型的问题：给定一个整数k，问题要求k个解决方案，使这些解决方案之间的成对（加权）汉明距离的总和最大化。这种解决方案被称为多样性解决方案。我们提出了一个多项式时间算法，在加权有向图中寻找不同的最短st-路。此外，我们还研究了其他经典组合问题的不同版本，如不同的加权拟阵基，不同的加权树形图，和不同的二部匹配。我们表明，这些问题也可以在多项式时间内解决。为了评估我们的算法找到不同的最短ST-路径的实际性能，我们进行了计算实验与合成和现实世界的实例。实验表明，我们的算法成功地计算不同的解决方案在合理的计算时间。
Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest st-paths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.