带约束的图匹配
Graph matching with constraints
我遇到了以下问题，我没有看到有效的解决方案，而是采用了蛮力方法。有人介意帮我一把吗？
该问题由图 G= (V,E) 有向加权无环图组成。边的权重为 w(u,v)。 w(u, v) 的值仅取决于原点 ( w(u,x)= w(u,y)如果 (u,x) 和 (u,y) 存在）。最初，每个顶点可能有多个传入和/或传出边。目标是以总剩余权重最大的方式在每个顶点最多保持一条出边。有出边的顶点不能有入边。例如，考虑图 1。左侧图是原始图。最多保留一个出边，右边的图代表了最大总权重17的解。
但是，这个问题还有另一个限制条件。每个顶点都分配有 2 个值，容量和负载。容量表示它可以附加多少负载。在找到最大总重量配置时，还必须考虑容量。图 2 显示了与图 1 相同的图表，但现在容量约束起着决定性的作用。看到在这种情况下最大总重量配置是不同的（右图，图 2）。
综上所述，为了得到最大的总权重，有3个限制条件：
- 遵守容量限制；
- 有出边的顶点没有入边；
- 顶点最多有一条出边
我提出的唯一解决方案是测试所有可能的配置，检查它是否有效并跟踪最大值。有没有人有更好的方法来解决这个问题？
你的问题对我来说看起来像 knapsack 问题：选择一组边以最大化利润。
你可以肯定的是，使用 constraint satisfaction approach. For example, check this code 解决背包问题。根据您的需要调整它应该是一项相当简单的任务。
使用此方法不需要任何匹配算法 - 求解过程将直接构建可能的最佳解决方案。但是，对于较大的图（数千 edges/nodes）可能需要很多 time/memory。
我遇到了以下问题，我没有看到有效的解决方案，而是采用了蛮力方法。有人介意帮我一把吗？
该问题由图 G= (V,E) 有向加权无环图组成。边的权重为 w(u,v)。 w(u, v) 的值仅取决于原点 ( w(u,x)= w(u,y)如果 (u,x) 和 (u,y) 存在）。最初，每个顶点可能有多个传入和/或传出边。目标是以总剩余权重最大的方式在每个顶点最多保持一条出边。有出边的顶点不能有入边。例如，考虑图 1。左侧图是原始图。最多保留一个出边，右边的图代表了最大总权重17的解。
但是，这个问题还有另一个限制条件。每个顶点都分配有 2 个值，容量和负载。容量表示它可以附加多少负载。在找到最大总重量配置时，还必须考虑容量。图 2 显示了与图 1 相同的图表，但现在容量约束起着决定性的作用。看到在这种情况下最大总重量配置是不同的（右图，图 2）。
综上所述，为了得到最大的总权重，有3个限制条件：
- 遵守容量限制；
- 有出边的顶点没有入边；
- 顶点最多有一条出边
我提出的唯一解决方案是测试所有可能的配置，检查它是否有效并跟踪最大值。有没有人有更好的方法来解决这个问题？
你的问题对我来说看起来像 knapsack 问题：选择一组边以最大化利润。
你可以肯定的是，使用 constraint satisfaction approach. For example, check this code 解决背包问题。根据您的需要调整它应该是一项相当简单的任务。
使用此方法不需要任何匹配算法 - 求解过程将直接构建可能的最佳解决方案。但是，对于较大的图（数千 edges/nodes）可能需要很多 time/memory。