Institutional Repository
| a category theoretic approach to search algorithms: towards a unified implementation for branch-and-bound and backtracking | |
| Zheng Yujun; Xue Jinyun; Shi Haihe | |
| 2009 | |
| Conference Name | 4th International Conference on Computer Science and Education |
| Source | Proceedings of 2009 4th International Conference on Computer Science and Education, ICCSE 2009 |
| Conference Date | JUL 25-28, |
| Conference Place | Nanning, PEOPLES R CHINA |
| Publish Place | 345 E 47TH ST, NEW YORK, NY 10017 USA |
| Publisher | ICCSSE 2009: PROCEEDINGS OF 2009 4TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE & EDUCATION |
| ISBN | 978-1-4244-3519-7 |
| Department | Zheng Yujun Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. |
| English Abstract | 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. |
| Keyword | Category Theory Par Colimit Branch-and-bound Backtracking |
| Sponsorship | IEEE, Comp Educ Coll & Univ, Natl Res Council, Guangxi Univ, IEEE Control Syst Chapter, Guangzhou, IEEE Control Syst Chapter, Singapore, Univ Melbourne, Univ Virginia, Univ Texas, Univ British Columbia, Xiamen Univ, Chongqing Univ, Xiamen Xinhangha Ctr Comp Educ & Dev |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8312 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Zheng Yujun,Xue Jinyun,Shi Haihe. a category theoretic approach to search algorithms: towards a unified implementation for branch-and-bound and backtracking[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:ICCSSE 2009: PROCEEDINGS OF 2009 4TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE & EDUCATION,2009. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment