我正在看几个类似格式但难度不同的问题.对多项式(优选相对较快,但不一定),甚至任何这些的强力解决方案都应该有所帮助.
所有问题的想法是你有一个加权的无向图,并且代理在开始时控制图的一些节点.如果节点已经控制了两个相邻节点,则代理可以获得对节点的控制.代理正在尝试最小化控制一定数量节点所花费的时间.问题在某些细节上有所不同.
(1)您按顺序获得节点控制(即,您不能同时接管多个节点).控制节点所花费的时间定义为用于控制节点的两个节点的边缘的最小值.目标是控制图中的每个节点.
(2)同样,您按顺序获取节点,目标是控制图中的每个节点.控制节点所花费的时间定义为用于控制节点的两个节点的最大值.
(3)(1)或(2),但目标是控制一定数量的节点,不一定是所有节点.
(4)(3),但您可以同时控制多个节点.基本上,假设节点2和4用于在5的时间内接管节点3.在5的时间期间,节点2和4不能用于接管不是节点3的节点.但是,节点5和6例如,可以同时接管节点1.
(5)(4),但有一个未加权的图.
我从问题开始(4).我逐渐使问题从(4)到(3)到(2)到(1)变得更容易,希望我可以从中构建(4)的解.最后,我已经解决了(1)但不知道如何解决任何其他问题.我对(1)的解决方案是:在我们控制的两个相邻节点的所有候选节点中,只需要花费最短时间的节点.这类似于Dijkstra的最短路径算法.但是,这种解决方案不应该解决任何其他问题.我相信动态编程解决方案可能会起作用,但我不知道如何制定一个.对于4个问题中的任何一个,我也没有找到蛮力解决方案.有些问题也可能不是多项式可解决的,我很想知道为什么会出现这种情况.
问题的想法是我自己的,我正在解决我自己的娱乐.但如果能在其他地方找到,我也不会感到惊讶.
这不是问题的答案。它证明了贪婪方法对于问题 1 是失败的。
假设我们有一个有 7 个节点的图。A我们从控制和开始B。A往返B的费用都是。B 和都连接到、和且具有成本。 连接到、、、 和且具有成本CCD1EFABD10GABCD100。
您描述的贪婪策略将分别连接到E和F成本10，然后D是 成本10，然后C是 成本1，然后G是 成本 ，100总成本为131。
G最佳策略是按成本连接100，然后C按D成本连接1，然后E按F成本连接10，总成本为122 < 131。
这个例子表明贪婪并不总是能产生正确的答案。