use*_*830 5 sorting algorithm optimization
我可以从一系列"动作"中进行选择,每秒执行一次.列表中的每个动作都有一个表示它值多少的数值,还有一个代表其"冷却时间"的值 - 我再次使用该动作之前必须等待的秒数.列表可能如下所示:
因此在这种情况下,ABA的总值将为(1 + 1.5 + 1)= 3.5,这是可以接受的,因为A的首次使用发生在1秒,最后一次使用A发生在3秒,然后这两者之间的差异大于或等于A的冷却时间,2秒.订单AAB不起作用,因为你只做了一秒钟,低于冷却时间.
我的问题是尝试优化使用操作的顺序,最大化一定数量的操作的总价值.显然,如果你只使用一个动作,最佳顺序是做动作D,结果总值为3.两个动作的最大值来自做CD或DC,结果总值为5.当您执行10或20或100个操作时,会变得更复杂.我找不到一种方法来优化动作的顺序而不强制它,这使得复杂性成为指向要优化顺序的动作总数的指数.总共大约15次变得不可能.
那么,有没有办法找到最少的复杂度的最佳时间？这个问题有没有被研究过？我想可能会有某种加权图形类型的算法,但我不知道它是如何工作的,更不用说如何实现它了.
对不起,如果这是令人困惑的 - 它在概念上有点奇怪,我找不到更好的方法来构建它.
编辑：在重新阅读您的问题之后，我发现需要调整加权调度算法以适应您的问题陈述；在我们的例子中，我们只想从与我们选择的操作类别匹配的集合中取出那些重叠的操作，以及那些在同一时间点开始的操作。IE 如果我们选择a1，我们想从集合中删除a2和 ，但不是。b1b2
这看起来与本 pdf 中深入讨论的加权调度问题非常相似。本质上，权重是你的动作的值，间隔是（开始时间，开始时间+冷却时间）。动态规划解决方案可以被记忆，这使得它在 O(nlogn) 时间内运行。唯一困难的部分是修改您的问题，使其看起来像加权区间问题，这样我们就可以利用预定的解决方案。
因为您的间隔没有设置开始和结束时间（即您可以选择何时开始某个操作），所以我建议假设某个设定的时间范围，枚举所有给定操作的所有可能的开始时间，然后使用这些静态开始/动态规划解决方案的结束时间。假设您只能在一整秒内开始一个操作，您可以在间隔 (0-2,1-3,2-4,...) 内运行操作 A，在 (0-3,1-4,2 -5,...)，动作 C 表示间隔 (0-5,1-6,2-7,...) 等。然后，您可以使用并集动作的集合来获得看起来像原始加权的问题空间间隔问题：
|---1---2---3---4---5---6---7---| time
|{--a1--}-----------------------| v=1
|---{--a2---}-------------------| v=1
|-------{--a3---}---------------| v=1
|{----b1----}-------------------| v=1.5
|---{----b2-----}---------------| v=1.5
|-------{----b3-----}-----------| v=1.5
|{--------c1--------}-----------| v=2
|---{--------c2---------}-------| v=2
|-------{-------c3----------}---| v=2
etc...