最小化动态“度量”的生成树
让我们有一个图表。当我们删除一条边时，会创建 2 辆“汽车”，边的每个顶点各一辆。当这两辆车相遇时，他们停下来。问题是创建一棵生成树，使得通过每个顶点的汽车数量之和最小。
额外的困难是，如果一个顶点有 n 辆汽车经过，那么成本是 K^n 而不是 n*K。
一些想法。我们可以找到最短的无弦周期作为开始，但这些无弦周期的位置（即它们是否相互接触）会改变度量，从而改变最短周期。
这不是最小生成树问题。我想解决这个问题，因为每辆车代表一个变量，而生成树是计算优化问题的最有效方法。当来自同一边缘的两辆车相遇并停下来时，我从优化中减少了一个变量。
编辑：
过程是这样的。我们删除一些边以使图成为生成树。每条移除的边都会创建 2 辆汽车，在移除的边的每个顶点各有一辆车，它们需要彼此相遇。我们为这对双胞胎车中的每一辆车都确定了一条路径。然后我们检查有多少辆车（从我们删除的所有边中）穿过每个顶点。如果从某个顶点经过的汽车数量为 n，则成本为 K^n，其中 K 是常数。然后我们将所有成本相加，这就是需要最小化的全局成本。
如果有不清楚的地方请告诉我。 https://mathoverflow.net/questions/86301/spanning-tree-that-最小化动态指标
Let us have a graph. When we remove an edge, 2 'cars' are created, one from each vertice of the edge. when these 2 cars meet they stop. The problem is to create a spanning tree so that the sum of the numbers of cars that pass through each vertice is minimal.
The added difficulty is that if a vertice has n cars passing from it, then the cost is K^n and not n*K.
some thoughts. We could find the shortest chordless cycles as a start but the position of those chordless cycles, ie whether they touch each other, changes the metric and thus what the shortest cycle is.
This is not a minimum spanning tree problem. I want to solve this because each car represents a varriable and the spanning tree is the most efficient way to compute an optimization problem. When 2 cars from the same edge meet and stop, I have a reduction of one varriable from the optimization.
edit:
The process is like this. We remove a number of edges to make the graph a spanning tree. Each removed edge creates 2 cars, one at each vertice of the removed edge, that need to meet each other. We fix a path for each of those twin cars. We then check how many cars (from all the edges that we removed) pass through each vertice. If the number of the cars that pass from a vertice is n, the cost is K^n where K is a constant. We then add all the costs and that is the global cost that needs to be minimized.
please tell me if something is unclear.
https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这里有一个见解 - 汽车永远不会通过铰接点，因此您可以将图分解为多个块，并分别求解每个块（最小总体成本函数是每个块的最小成本之和）。
要找到一个块的最小成本 - 您可以枚举该块的所有生成树并计算每个生成树的成本 - 这是一种蛮力方法，但它应该可行。
Here's one insight - cars will never pass through an articulation point, so you can break the graph up into its blocks and solve for each block separately (the minimum overall cost function is the sum of the minimum cost for each block).
To find the minimum cost for a block - you could enumerate all the spanning trees for that block and calculate the cost for each one - a brute force approach, but it should work.