※ 引述《lanniba (烂泥巴)》之铭言： : 想请问一下 : 不知道是否有相关或类似的演算法能知道 : 一个无向图里面，能够走完每个"边"的最短路径(节点重复走过没关系) : 希望有大大可以给我提示@@ 这是属於图论 graph theory 的问题， 这个问题的正式名称叫做中国邮差问题 Chinese postman problem， 它是七桥问题（每条边刚好只走一次）的加强版本， 如果想要学会中国邮差问题的演算法，得先学会七桥问题的演算法。 然後也要想办法了解一下图论里的 shortest path 和 matching 这两个概念。 中国邮差问题的演算法大意是： 奇点(连接奇数条边的点)最後一定得重复走到某一条边， 要让总路线最短，最好的方式是把奇点与奇点双双对对连接起来，尽量减少重复。 找到最短的连接方式之後， 最後再套用七桥问题的解法即可。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 36.225.134.133