Algebraic Methods in Search

点击翻译按钮获取中文摘要

The principal theme of this research is the application of group- theoretic techniques to a wide variety of search problems. The ultimate objective is to combine algebraic techniques with standard search methods to solve problems which are currently solvable by neither method alone. The research has three major aspects; the development of an experimental system for testing algorithmic ideas; and the exploration of methods for representing search problems in an algebraic setting, and of tools for solving them. The algorithms to be studied play a central role in most applications of group theory to real world problems. Group membership is used to construct a solution, minimum word algorithms correspond to the simplification of a solution, and a change of basis represents a transformation of the group data structure into a domain which is more suitable for improving time and space utilization. Applications are numerous. Examples range from the transporation problem in operations research to minimization of pin count in VLSI. Both algorithms and applications are being implemented in the context of a unified environment which is engineered to support experimentation with a variety of data structures and approaches.