通过所有边的最短路径算法

Question

这是一个朋友最近问我的一个有趣的问题/谜语：

您正在绘制网球场的线条。你有一台画直线的机器，但是一旦它打开，你就不能停止工作，直到工作完成。很明显，您需要两次检查某些行。您必须使用的最少额外油漆量是多少，以英尺为单位？

法院的尺寸：

所有线的总和是 480 英尺。我碰巧知道答案是 63 英尺（总共 543 英尺），但我不禁想知道解决这个问题的最佳算法是什么。

这似乎类似于旅行商问题，其中球场上的每条线都由图中的一个顶点表示，而球场线的交汇点则转化为边。（否则，如果线是边，角是顶点，则需要一条穿过所有边的路径，而我不知道有任何算法）。也许您需要更聪明地了解如何表示线的交叉点，我对此有一些想法，但还没有真正奏效。

不过，我认为问题足够小，可以对通过折线图的所有路径进行蛮力检查。你会如何编码？

Answer 1

无向图具有欧拉迹当且仅当至多两个顶点具有奇数度，并且其所有具有非零度的顶点都属于单个连通分量。\xef\xbc\x88 从http://en.wikipedia.org/wiki/Eulerian_path \xef\xbc\x89找到

\n\n

当我们得到一个非欧拉图时，我们可以通过向奇数度顶点添加边来将其变为欧拉图。\n因此，这个问题就转化为：找到将图变为欧拉图的最低成本。

\n\n

该算法应该是：

\n\n

\n
1. 列出所有度数为奇数的顶点，建议是一个list_vodd[]；
\n
2. 求list_vodd[]中顶点之间的最短边，得到边的两个顶点：pa, pb；
\n
3. 在 pa,pb 之间添加一条边（这意味着该边应该绘制两次）；
\n
4. 从list_vodd[]中删除pa,pb；
\n
5. 转到 2 直到 list_vodd[] 中只剩下两个顶点。
\n
6. 使用任何现有算法找出新图中具有添加边的欧拉路由器。
\n

\n