首页 > 代码库 > 显示器电子枪显示一个汉字,画完所有的笔画,求最短路径算法。求讨论

显示器电子枪显示一个汉字,画完所有的笔画,求最短路径算法。求讨论



如题。
个人觉得有两种思路,第一是归结为旅行商问题,用分支限界法或者其它方法求解。假设一个汉字有n划,就对应2n个点对。每画一划,就少了2个选择,所以总共的解空间大小是2n*2(n-1)*...*2。

第二是归结为中国邮递员问题,走完一个连通图的所有边,怎么走路径最短,通过添加一些多余的边,也是能得到最优解的。但是汉字可能不是一个连通图,怎么办?也许可以先通过计算汉字各划的位置关系,将其扩展为连通图?

感觉第一种方法要简洁一些,便于处理。
请问大家思路?

显示器电子枪显示一个汉字,画完所有的笔画,求最短路径算法。求讨论