我使用哪种增强图算法？

Question

我有一组节点AG,Z,定义了加权边,其中AG是漏斗中的各种节点,Z位于最底部.

可视化具有各种边缘的漏斗(V形),但最终指向最终节点Z,就像水流向单点Z.我们希望找到最便宜的路径,直到Z,覆盖漏斗中的所有节点.

以下是约束:

• 没有孤立节点(所有节点都连接/包含)
• 我们希望最小化加权边的总和
• "共享边缘",如水向下流动时合并,仅计算共享边缘的重量一次(换句话说,它可以自由地沿湿路径流动)

我应该使用哪种增强图算法来找到这个问题的最佳边缘集？

• ABDEZ是一条覆盖大量节点的廉价路径
• CGZ有点被迫,因为G只有一条到Z的路径
• FZ看起来便宜,但后来我们注意到,由于CGZ被迫,FGZ实际上比FZ便宜(因为我们不需要对GZ段进行双重计算,FG的增量成本仅为1)

所以,边缘集应该是(AB,BD,DE,EZ,CG,FG,GZ)

我确信这不是一个新问题:我只是不知道足够的图论来识别/命名算法.

更新

在对问题进行更多研究的同时,我发现如果图不是定向的,那么问题就会减少到最小生成树.换句话说,如果我们没有先验地指出Z是图中的最低点(通过使用箭头),并允许水在两个方向上流动(通常是真的,除非我们有阀门),那么这第二个模型将正常工作.

当然,我们现在可以选择新的FZ无向边缘,而不是被迫使用旧的GZ定向边缘.

根据这些结果,如果我们真的需要指向边缘,liori的答案是对原始问题的最佳响应(即算法需要编码).

产量

D <--> E with weight of 1
F <--> G with weight of 1
A <--> B with weight of 2
E <--> Z with weight of 2
C <--> G with weight of 2
F <--> Z with weight of 2
B <--> D with weight of 3
Total Weight = 13

使用最小生成树的无向非循环图代码

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>

int
main()
{
  using namespace boost;

  typedef adjacency_list < vecS, vecS, undirectedS,
    no_property, property < edge_weight_t, int > > Graph;
  typedef graph_traits < Graph >::edge_descriptor Edge;
  typedef graph_traits < Graph >::vertex_descriptor Vertex;
  typedef std::pair<int, int> E;

  char letter[] = "ABCDEFGZ";
  const int num_nodes = 8;
  E edge_array[] = { 
        E(0,1), E(1,2), E(1,3), E(3,6), E(3,5), E(3,4), E(2,5), E(2,6), 
        E(5,7), E(5,6), E(6,7), E(4,7) 
  };
  int weights[] = { 2, 6, 3, 5, 3, 1, 4, 2, 2, 1, 3, 2 };
  std::size_t num_edges = sizeof(edge_array) / sizeof(E);
  Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
  property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);
  std::vector < Edge > spanning_tree;

  kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

  int total_weight = 0;
  for (std::vector < Edge >::iterator ei = spanning_tree.begin();
       ei != spanning_tree.end(); ++ei) 
  {
    std::cout << letter[source(*ei, g)] << " <--> " << letter[target(*ei, g)]
      << " with weight of " << weight[*ei]
      << std::endl;
    total_weight += weight[*ei];
  }
  std::cout << "Total Weight = " << total_weight << std::endl;

  return EXIT_SUCCESS;
}

Answer 1

因此，您需要以最便宜的方式从Z后到每个节点。您的问题相当于在 DAG 上查找生成树，只不过您需要转换 DAG 以使边缘指向相反的方向。正如此答案中所解释的，您应该检查Chu\xe2\x80\x93Liu/Edmonds\' 算法等算法。

\n\n

不过，Boost Graph 中似乎没有现成的算法。您可能需要构建自己的算法。

\n