r - 如何规划最有效的露台灯路线

我想把院子里的灯串起来。根据我的要求，我意识到我需要一个算法来解决aanother question问题，以找出灯光应该走的最有效的路线，从而使覆盖灯光的重复边最少。经过一番搜索，我意识到也许这样的事情是我最好的选择：Route Inspection Problem。
但是，创建图表时遇到问题。
以下是它的外观：
Solving Chinese Postman algorithm with eulerization
粉红色的圆圈代表建筑中我可以悬挂灯光的地方
“启动”是唯一可用的电源插座
黄色的圆点代表灯光应该覆盖的所有地方
下面是我引用这篇文章后的图表：

如您所见，所有节点都位于正确的位置，但边连接到了不应该连接的位置。这是我的代码：

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的性质有关，但我无法找到另一种方法来定义图的“边”长度而不出错。

最佳答案

我认为您可以使用edgelist中的graph_精确地指定要连接的节点。指定按哪个顺序连接哪些节点就足够了。好问题顺便问一下！

  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）以允许类似于您的方案的分支。这看起来差不多吗？

我看了上一篇关于堆栈溢出（你建议的那个）的文章，试图使这成为一个euler循环。实际上，自定义函数确实是开箱即用的，但是您可能需要再次检查是否可以使用生成的解决方案。也许，你可以先定义一个更好的连接设计，再“歌颂”电路。这就是我得到的。

# 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")