如何规划天井灯的最有效路线

我想串起一些天井灯。基于another question我问，我意识到我需要一个算法来解决Route Inspection Problem找出最有效的路线，灯应该采取，所以有最小的重复边缘灯。经过一番搜索，我意识到也许这样的事情是我最好的选择：Solving Chinese Postman algorithm with eulerization。如何规划天井灯的最有效路线

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

下面是它需要看起来像：

粉红色圆圈代表我可以从
挂灯结构的地方“开始”是唯一可用的电源插座
黄色点代表灯应覆盖的所有位置

这里就是我的图表看起来像引用这篇文章后：Visualizing distance between nodes according to weights - with R：

正如你可以看到，所有的节点都在正确的位置，但是边缘连接，他们不应连接。这里是我的代码：

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性质，但我无法找出另一种方式来定义图表边缘的长度没有错误。

来源

2017-08-17 Travis Heeter

我想你可以使用graph_from_edgelist来精确指定要连接的节点。指定按哪个顺序连接哪些节点就足够了。很好的问题btw！

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），以允许与您的方案类似的分支。这看起来应该多少还是少一些？

我看了上一篇关于堆栈溢出（您建议的那篇文章）的文章，试图将其作为一个欧拉循环。实际上，自定义功能确实可以工作，但您可能需要仔细检查是否可以使用生成的解决方案。也许，你可以尝试在“电路化”之前定义一个更好的连接设计。这就是我得到的。

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

来源

2017-08-17 03:13:09

是的，这正是它！谢谢！然而，我怎样才能把它变成一个图形对象，它可以用于这个：'eulerian.g1 < - make.eulerian（g1）$ graph'，其中'g1'是图形？（从这篇文章中解决邮差问题：https://stackoverflow.com/a/40596816/1152809） –

有趣的是，我并不知道这一点。所以，你想让eulerian成为一个不是eulerian本身的循环。我会研究一下。自定义f（x）不在我手中的盒子里工作..但我明天早上会看看这个！ :-) –

是的，我不确定它为什么不能开箱即用，但如果你检查这个问题：https://stackoverflow.com/a/40596816/1152809，接受的答案给出了一个“make .eulerian'替换你可以使用。我基本上复制/粘贴它，然后做到这一点：'eulerian <-make。欧拉（GG）;克<-eulerian $曲线图。帕（mfrow = C（1,2））;情节（GG）;图（G）'。但是，我不确定这是否是我需要的，因为它似乎没有考虑到结构（所有边缘长度）。 –

如何规划天井灯的最有效路线

回答

相关问题