|
|||||
|
|
| 绣字问题及其动态规划算法 | |
| 引用本文： | 汪定伟.绣字问题及其动态规划算法[J].运筹学学报,1988(2). |
| 作者姓名： | 汪定伟 |
| 作者单位： | 东北工学院 |
| 摘 要： | 一、问题的提出如何用最短的线在织物上不间断地绣一个汉字是一个有趣的图论问题。一个由n条直线段组成的汉字可以看成是一个有2n个节点的图G。每条线段连接一对顶点,n条线段构成G的一个完美对集M。如图1中的“六”字,4条直线段连接了8个顶点。将顶点间的距离作为顶点间连线的权,则问题变为如何寻找一条经过所有M中元素的路P,使P中边的权和为最小。由于顶点间的连线是任意的,P交替地通过M中元素和非M中元素,所以问题的实质是在一个2n阶的完全图中找一条M交错路, |
| 本文献已被 CNKI 等数据库收录！ | |