摘要
通过建立合适的模型对公园道路规划的3个问题进行了求解。第一个问题主要基于遍历的思想,采用深度优先搜算方法以及剪枝法对问题进行求解。第二、三个问题的模型主要基于局部最优到整体最优的思想,把公园内的道路设计分成了4个部分,运用子网络与整体网络的关系从不满足椭圆覆盖的约束入手来求解。最后通过斯坦纳树的理论对结果进行了检验,保证了结果的正确性。
This paper establishes a proper model for solving three problems of ＂ Optimal Park Road Design＂. The first problem is solved via adopting depth-first search algorithm and pruning method based on the traverse idea. The theory of ＂from local to the whole＂ is applied in the second and third problems. We divide the park road into four parts, employ the relationship between the overall network and sub-networks, and then start from the constraints which do not satisfy elliptical cover. Finally, results aa：e checked by Steiner tree.
出处
《电子科技》
2014年第2期3-6,共4页
Electronic Science and Technology
基金
青年科学基金资助项目(11201360)
关键词
深度优先搜索
子网络
整体网络
椭圆覆盖
斯坦纳树
depth-first search
sub-networks
ow^rall network
elliptical cover
Steiner tree
