5

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

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

法院的尺寸：

法庭

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

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

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

4

2 回答 2

3

一个无向图有欧拉轨迹当且仅当至多两个顶点的度数为奇数，并且其所有非零度数的顶点都属于一个连通分量。（取自http://en.wikipedia.org/wiki/Eulerian_path）</p>

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

算法应该是：

  1. 列出所有具有奇数度的顶点，建议它是一个 list_vodd[];
  2. 在list_vodd[]中找到顶点之间的最短边，得到边的两个顶点：pa，pb；
  3. 在 pa,pb 之间添加一条边（这意味着这条边应该被绘制两次）；
  4. 从 list_vodd[] 中删除 pa,pb；
  5. 转到 2 直到 list_vodd[] 中只有两个顶点。
  6. 使用任何现有算法在带有添加边的新图中找出欧拉路由器。
于 2013-02-28T08:24:24.917 回答
0

我在这里玩游戏有点晚了，但是当我试图找到一种算法来确定在州立公园的每条小径上徒步旅行的最短路径时，我遇到了这个问题。这是一个草图，解释了为什么答案是 63 在此处输入图像描述 正如理查德所说，这是一个中国邮递员问题。由于问题没有指定我们必须在同一位置开始和结束，我们可以使用半欧拉图，这就是为什么所有节点都有偶数，除了共享公共边的起点和终点。

这是一个非常好的视频，它解释了如何绘制和解决此类问题。 https://www.youtube.com/watch?v=spaUY8PlyYA

于 2021-04-01T18:04:29.990 回答