A Category Theoretic Approach to Search Algorithms: Towards a Unified Implementation for Branch-and-Bound and Backtracking
Branch-and-bound and backtracking are widely used for search and optimization problems, but their implementations vary from problem to problem. In this paper we propose a unified approach of program derivation and generation for the two classes of algorithms. We first define a generalized specification for the search strategies, and then derive the algorithms, abstract programs and generic programs by incremental refinements on PAR platform, and finally generate efficient programs for concrete problem-solving via colimit computations. Our approach achieves a high level of abstraction and mechanization without losing performance.
Category theory PAR Colimit Branch-and-Bound Backtracking
ZHENG Yujun XUE Jinyun SHI Haihe
State Key Lab of Computer Science Institute of Software, Chinese Academy of Sciences Beijing, China Provincial Key Lab of High-Performance Computing Jiangxi Normal University Nanchang, China
国际会议
第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)
南京
英文
845-850
2009-07-25（万方平台首次上网日期，不代表论文的发表时间）