如何规划最有效的露台灯路线 [英] How to plan the most efficient route for patio lights

问题描述

我正试图将一些露台灯串起来。根据我问的

• 粉色圆圈表示中的位置我可以挂起灯光的结构


• 开始是唯一可用的电源插座


• 黄点代表灯光应覆盖的所有地方

这是我的图表在引用此帖子后的样子：

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

 库（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_from_edgelist用于精确说明要连接的节点。指定以什么顺序连接哪些节点就足够了。好的问题btw！

  gg<-graph_from_edgelist（cbind（c（1：4，6，8，8，10，12， 14，16:19，1，6，8，21，12，14，5，7，9，11，13，15），
c（2：5，7，9，11，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），
边.color = orange）
  

我添加了一个节点（n 21）来允许分支与您的方案类似。

我看了以前的文章尝试使用堆栈溢出（建议的堆栈溢出）进行欧拉循环。实际上，自定义功能确实是开箱即用的，但是您可能要仔细检查是否可以使用生成的解决方案。也许，您可以在平衡电路之前尝试定义更好的连接设计。这就是我得到的。

 ＃加载自定义f（x），如
＃https：// stackoverflow。 com / questions / 40576910 / solving-chinese-postman-algorithm-with-eulerization / 40596816＃40596816 
 
 eulerian<-make.eulerian（gg）
 eulerian $ info 
g <-eulerian $ graph 
 
＃像以前一样设置布局，以保持电路根据您的规格格式化
 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 ）
  

I'm trying to string up some patio lights. Based on another question I asked, I realize I need an algorithm to solve a Route Inspection Problem to figure out the most efficient route the lights should take so there's minimal duplicate edges covered with lights. After some searching I realized that perhaps something like this would be my best bet: Solving Chinese Postman algorithm with eulerization.

However, I'm having trouble creating the graph.

Here's what it needs to look like:

• pink circles represent places in the structure I can hang lights from
• "Start" is the only available electrical outlet
• The yellow dots represent all the places lights should cover

And here's what my graph looks like after referencing this post: Visualizing distance between nodes according to weights - with R:

As you can see, all the nodes are in the correct place, but the edges are connecting where they shouldn't connect. Here's my code:

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)

I think this has something to do with the nature of graph.ring, but I am unable to figure out another way to define the graphs' edges' lengths without error.

解决方案

I think you can use graph_from_edgelist for a precise specification of which nodes to connect. It is sufficient to specify which nodes to connect in which order. Nice question 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")

I added a node (n 21) to allow a branching that is similar to your scheme. Does this look more or less as it should?

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

这篇关于如何规划最有效的露台灯路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！