我有一组节点A-G、Z,定义了加权边,其中A-G是漏斗中的各种节点,Z在最底部。将漏斗(V形)可视化,具有各种边缘,但最终指向Z,即水流向单个点Z。我们希望找到最便宜的路径到达Z,该路径覆盖了漏斗中的所有节点。
以下是约束条件:
- 没有孤立节点(所有节点都连接/包含) - 我们希望最小化加权边的总和 - “共享边缘”(如水向下流动时合并),仅计算共享边缘的权重一次(换句话说,沿着湿润的路径自由向下流动)
应使用哪个增强图算法来查找此问题的最佳边集?
使用最小生成树的无向无环图代码
以下是约束条件:
- 没有孤立节点(所有节点都连接/包含) - 我们希望最小化加权边的总和 - “共享边缘”(如水向下流动时合并),仅计算共享边缘的权重一次(换句话说,沿着湿润的路径自由向下流动)
应使用哪个增强图算法来查找此问题的最佳边集?
- A-B-D-E-Z是一条涵盖许多节点的廉价路径
- C-G-Z有点强制,因为G只有一条通往Z的路径
- F-Z看起来很便宜,但是我们注意到由于C-G-Z是强制性的,所以F-G-Z实际上比F-Z更便宜(因为我们不需要双重计算G-Z段,F-G的增量成本仅为1)
因此,边集应为(A-B、B-D、D-E、E-Z、C-G、F-G、G-Z)
我确定这不是一个新问题:我只是不了解足够的图论来识别/命名算法。
更新
在进一步研究问题时,我发现如果图形不是有向的,那么问题就简化为最小生成树。换句话说,如果我们没有事先指定 Z 是图中最低点(通过箭头使用),并且允许水在两个方向上流动(通常是真实的,除非我们有阀门),那么这个第二个模型将工作得很好。
当然,我们现在可以选择较小权重的新F-Z无向边,而不是被迫使用旧的G-Z有向边。
考虑到这些结果,如果我们确实需要边是有向的,liori's answer 是对原问题(即需要编写算法)的最佳回应。
输出
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;
}