a category theoretic approach to search algorithms: towards a unified     implementation for branch-and-bound and backtracking

	a category theoretic approach to search algorithms: towards a unified implementation for branch-and-bound and backtracking
	Zheng Yujun; Xue Jinyun; Shi Haihe
	2009
会议名称	4th International Conference on Computer Science and Education
会议录名称	Proceedings of 2009 4th International Conference on Computer Science and Education, ICCSE 2009
会议日期	JUL 25-28,
会议地点	Nanning, PEOPLES R CHINA
出版地	345 E 47TH ST, NEW YORK, NY 10017 USA
出版者	ICCSSE 2009: PROCEEDINGS OF 2009 4TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE & EDUCATION
ISBN	978-1-4244-3519-7
部门归属	Zheng Yujun Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.
摘要	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
主办者	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
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8312
专题	基础软件与系统重点实验室
推荐引用方式 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.