Studies on Permutation Set Manipulation Based on Decision Diagrams
祐馬 井上 · Hokkaido University Collection of Scholarly and Academic Papers (Hokkaido University) · 2017
In real life, we often face ordering problems of items: sorting items with some priorities, processing many tasks sequentially, ranking search results on the Web, traveling famous sites one by one, and so on.In mathematical terms, ordering of items is called a permutation.Since a permutation can be considered as a bijective function on a set, permutations can also represent e.g., reversible functions and pair-matching of items.There are a lot of previous research results to find a "good" permutation for problems on which solutions can be described as permutations.For example, the traveling salesman problem requires us to find a "shortest" path consisting of a permutation of all vertices, and the single-machine scheduling problem requires us to find a permutation of all tasks with the "minimum" penalty.On the other hand, in real situations, conditions such as roads or priorities can be dynamically changed.In such cases, we have to calculate a "good" permutations again and again.Enumeration of permutations is a way to overcome difficulties of dynamic changes.If we store all solutions and index to extract a "good" permutation from the solutions, we may obtain a "good" permutation faster than repeatedly calculating under new conditions.Furthermore, enumeration of all solutions is useful for other applications: obtain the number of solutions, random sampling of solutions, extracting solutions satisfying additional conditions, etc.For several conditions, enumeration of permutations has been also deeply studied.However, the number of the permutation is huge, namely factorial in the number of items.Hence the listing all permutations seems to be infeasible even for a few items.An idea to avoid the factorial explosion is the usage of a compressed data structure to store and to index solutions.In this thesis, we focus on permutation decision diagrams (πDDs) as such a data structure.This data structure can store permutations compactly and possesses a permutation-set algebra including union and intersection.Moreover, manipulation and extraction of permutations in the data structure can be achieved in time depending only on the size of πDDs, not on the number of permutations represented by πDDs.This means that if the solutions could be well compressed by a πDD, manipulation of the solutions can also be efficiently processed.Although a πDD is a powerful data structure, there are few results applying πDDs permutations.These will be hints when we utilize πDDs and Rot-πDDs for other permutation problems.In addition, we provide a new method that improves a part of existing decision diagram based algorithms.It can be expected that the results in this thesis will lead to efficient methods for practical applications of permutation problems in this thesis and many other permutation problems.