[4F1-OS-8a] AIと制約プログラミング(1/2)

[4F1-OS-8a-02] Solving the Shortest Path Reconfiguration Problem with ZDDs and Its Evaluation

〇Shou Ooba¹, Jun Kawahara¹, Shin-ichi Minato¹ (1. Kyoto University)

Keywords:Combinatorial reconfiguration, Graph algorithm, Zero-suppressed binary decision diagram

The Shortest Path Reconfiguration (SPR) Problem is the problem that the input is an unweighted simple graph G(V,E), vertices s,t in V, and shortest s-t paths P and Q, and the output is whether it is possible to obtain Q by repeatedly changing a vertex of P to obtain another shortest s-t path. This problem is known to be PSPACE complete. In this paper, we propose methods for solving the SPR problem using Zero-suppressed Binary Decision Diagram (ZDD). In giving the methods, we also propose several new ZDD operations. As a result of computer experiments, we successfully solved an instance of the 90 by 90 grid graph, whose shortest operation sequence length is 7921, in about 114.5 minutes. We also succeeded in solving an instance with 288 vertices and 781 edges and a shortest operational sequence length of 46137333 in about 349.6 minutes.