algorithm - 图的临界点 : reach all nodes in minimum number of points and weight

Question

这是一个数据结构和算法类(class)的问题，所以我不是在寻找一个具体或完整的答案，但希望能提供一些提示来帮助我确定我是否在正确的轨道上(或者可以指出我的方向)在正确的轨道上)

给定一个位置的无向图，其中节点是位置，道路是边缘(由穿过某条道路所需的时间加权)，找到可以到达所有节点的最小点数*最大重量为 5。*点是图表上的任何点。它们可以在边缘或节点上。从现在开始我将它们称为临界点。

例如，如果我们有这个图:

节点1->节点3(权重1)->节点2(权重7)

节点2->节点1(权重7)->节点4(w 1)->节点7(w 8)

节点3->节点1(1)->节点4(2)->节点5(2)->节点6(2)

节点4->节点2(1)->节点3(2)->节点5(2)

节点5->节点3(2)->节点4(2)->节点7(3)

节点6->节点3(2)->节点7(5)

节点7->节点6(5)->节点5(3)->节点2(8)

然后关键点将是:一个在节点 1 和 2 之间的边上，节点 1 的权重为 2，节点 2 的权重为 5(注意它们的总和必须仍然等于 7，节点的原始权重1 到 2)，第二个在节点 7 上。第一个临界点可以到达最大权重为 5 的节点 1 到 6。从该点开始，只有节点 7 在权重 5 中无法到达，因此第二个临界点在节点 7 本身上。因此，整个图可以从这 2 个权重为 5(或更小)的临界点到达。

我的想法:为每个 Nose 保留一个 bool 值“完成”，表示可以或不能从已经找到的关键点之一到达它。从某个节点开始。使用 BFS 并遍历图形。在未完成的节点上，执行以下操作:

检查节点的邻接列表。忽略权重大于 10 的边，因为您无法放置到达您所在节点的临界点以及这些边导致的节点。忽略通向“完成”节点的边。如果没有剩余边，则将与当前节点位置相同的临界点添加到临界点列表中。否则，检查剩余的最大权重边，并在该边上创建一个临界点:临界点的 2 个选项。 curr_node 到 critical_point 的权重=5，critical_node 到 adjacent_node(边通往的节点)的权重为 edgeWeight-5，或者:crtical_point 到 adjacent_node 的权重为 5，curr_node 到 critical_point 的权重为 edgeWeight-5。尝试两者并检查哪个临界点可以到达权重为 5 的更多节点。使用具有更多可到达节点的那个并将这些节点标记为完成。

这里的问题是有效性证明。每个临界点(使用最大权重边时)有不止 2 个选项，我只考虑 2 个。但另一方面，如果我考虑更多，我们会遇到复杂性问题，算法已经不是太优化。此外，我们可能需要在节点周围的边缘放置多个临界点。该算法只放置一个或不放置一个并继续前进，因为我假设放置多个可能会放置比需要更多的点。

所以基本上，我不太确定从这里到哪里去。非常感谢任何帮助。

Answer 1

以下是我的脑洞，欢迎大家找找推理的漏洞。

看来您手头有布景问题。 IE。给定一个集合封面问题的实例，可以构建您的问题的一个实例，这样解决后者也可以解决前者。当然，集合覆盖问题是 NP 完全问题。

这是减少量。给定一个通用集 U 和覆盖所有 U 的子集的一些集合 S，构建一个仍然覆盖所有 U 的 S 的最小子集。

我们如下构建图 G。 U 的每个元素 u 是一个红色顶点。 S 的每个元素 s 都是一个蓝色顶点。如果u\in s，我们用长度为5的边连接相应的顶点。如果S的两个元素s_i和s_j相交，我们用长度为5的边连接相应的顶点。没有其他边。

假设我们已经确定了 G 中的一组临界点 Q。如果 Q 中有任何非蓝色点，请将其删除并替换为最近的蓝色顶点(如果有多个顶点，则替换为其中任何一个)。 可达顶点的集合不会变小。因此对于任何最小临界集，我们可以构建一个只有蓝色的最小临界集，而只有蓝色的临界集恰好是 U 的集合覆盖。 p>