如何规划庭院灯最有效的路线

我正在尝试挂一些庭院灯。基于另一个问题 https://cs.stackexchange.com/questions/80134/christmas-light-route-efficiency我问，我意识到我需要一种算法来解决路由检查问题 https://en.wikipedia.org/wiki/Route_inspection_problem找出灯光应采取的最有效路线，以便最大限度地减少被灯光覆盖的重复边缘。经过一番搜索后，我意识到也许这样的东西是我最好的选择：用欧拉化求解中文Postman算法 https://stackoverflow.com/q/40576910/1152809.

但是，我在创建图表时遇到了麻烦。

它需要如下所示：

• 粉红色圆圈代表结构中我可以悬挂灯的位置
• “启动”是唯一可用的电源插座
• 黄点代表灯光应该覆盖的所有地方

这是参考这篇文章后我的图表的样子：根据权重可视化节点之间的距离 - 使用 R https://stackoverflow.com/q/9452221/1152809:

正如您所看到的，所有节点都位于正确的位置，但边缘在不应该连接的地方连接起来。这是我的代码：

library(igraph)
gg<-graph.ring(20)
ll=matrix(
  c( 0,0,    75.25,0,    150.5,0,    225.8125,0,    302.8125,0, 
     0,-87,                                          302.8125,-87,
     0,-173.8125,                                    302.8125,-173.8125,
     0,-260.9375,                                    302.8125,-260.9375,
     16,-384.3125,                                   302.8125,-384.3125,
     16,-435.9575,                                   302.8125,-435.9375,
     16,-525.1875, 75.25,-525.1875, 150.5,-525.1875, 225.8125,-525.1875, 302.8175,-525.1875),
  ncol=2,byrow=TRUE)
plot(gg,layout=ll)

我认为这与性质有关graph.ring，但我无法找出另一种方法来无错误地定义图的边长度。

我认为您可以使用 graph_from_edgelist 来精确指定要连接的节点。指定以何种顺序连接哪些节点就足够了。顺便说一句，好问题！

  gg <- graph_from_edgelist(cbind(c(1:4, 6, 8, 10, 12, 14, 16:19, 1, 6, 8, 21, 12, 14, 5, 7, 9, 11, 13, 15), 
                                  c(2:5, 7, 9, 11, 13, 15, 17:20, 6, 8, 10, 12, 14, 16, 7, 9, 11, 13, 15, 20)))
  ll=matrix(
    c( 0,0,    75.25,0,    150.5,0,    225.8125,0,    302.8125,0, 
       0,-87,                                          302.8125,-87,
       0,-173.8125,                                    302.8125,-173.8125,
       0,-260.9375,                                    302.8125,-260.9375,
       16,-384.3125,                                   302.8125,-384.3125,
       16,-435.9575,                                   302.8125,-435.9375,
       16,-525.1875, 75.25,-525.1875, 150.5,-525.1875, 225.8125,-525.1875, 302.8175,-525.1875, 16, -260.9375),
    ncol=2,byrow=TRUE)
  plot(gg,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
       edge.color="orange")

我添加了一个节点（n 21）以允许类似于您的方案的分支。这看起来或多或少是应该的吗？

I had a look at the previous post on Stack Overflow (the one you suggested) to try making this an Euler cycle. Actually, the custom function does work out of the box, but you may want to double check if you can use the resulting solution or not. Maybe, you could try defining a better connection design before "eulerizing" the circuit. This is what I got.

# load custom f(x) as in
# https://stackoverflow.com/questions/40576910/solving-chinese-postman-algorithm-with-eulerization/40596816#40596816

eulerian <- make.eulerian(gg)
eulerian$info
g <- eulerian$graph

# set the layout as before to keep the circuit formatted according to your specs
par(mfrow=c(1,2))
plot(gg,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
     edge.color="orange", main = "Proposed")
plot(g,layout=ll, edge.arrow.size = 0, vertex.size = c(rep(18, 20), 0),
     edge.color="orange", main = "Eulerized")