python - 优化此动态规划解决方案

Question

问题:

给你一个大小为 n 的数组 m，其中 m 的每个值都由一个权重 w 和百分比 p。

m = [m<sub>0</sub>, m<sub>1</sub>, m<sub>2</sub>, ... , m<sub>n</sub>] = [[m<sub>0</sub><sup>w</sup>, m<sub>0</sub><sup>p</sup>], [m<sub>1</sub><sup>w</sup>, m<sub>1</sub><sup>p</sup>], [m<sub>2</sub><sup>w</sup>, m<sub>2</sub><sup>p</sup>], ..., [m<sub>n</sub><sup>w</sup>, m<sub>n</sub><sup>p</sup>] ]

所以我们将在 python 中将其表示为列表的列表。

然后我们试图找到这个函数的最小值:

# chaima is so fuzzy how come?
def minimize_me(m):
    t = 0
    w = 1
    for i in range(len(m)):
        current = m[i]
        t += w * current[0]
        w *= current[1]
    return t

关于 m 我们唯一可以改变的是它的顺序。 (即以任何方式重新排列 m 的元素)此外，这需要在 O(n!) 内完成。

暴力解决方案:

import itertools
import sys

min_t = sys.maxint
min_permutation = None

for permutation in itertools.permutations(m):
    t = minimize_me(list(permutation), 0, 1)
    if t < min_t:
        min_t = t
        min_permutation = list(permutation)

关于如何优化的想法:

想法:

不是寻找最佳顺序，而是看看我们是否可以找到一种方法来比较 m 中的两个给定值，当我们知道问题的状态时。 (代码可能会更清楚地解释这一点)。如果我可以使用自下而上的方法构建它(因此，假设我没有最佳解决方案，从头开始)并且我可以创建一个方程来比较 m 中的两个值并说一个是明确优于另一个，然后我可以通过使用该新值并比较下一组 m 值来构建最佳解决方案。

代码:

import itertools

def compare_m(a, b, v):
    a_first = b[0] + b[1] * (a[0] + a[1] * v)
    b_first = a[0] + a[1] * (b[0] + b[1] * v)

    if a_first > b_first:
        return a, a_first
    else:
        return b, b_first

best_ordering = []
v = 0

while len(m) > 1:
    best_pair_t = sys.maxint
    best_m = None

    for pair in itertools.combinations(m, 2):
        m, pair_t = compare_m(pair[0], pair[1], v)
        if pair_t < best_pair_t:
            best_pair_t = pair_t
            best_m = m

    best_ordering.append(best_m)
    m.remove(best_m)
    v = best_m[0] + best_m[1] * v

first = m[0]
best_ordering.append(first)

但是，这并没有按预期工作。第一个值总是正确的，大约 60-75% 的时间，整个解决方案是最优的。但是，在某些情况下，看起来我更改值 v 的方式评估的值比它应该的要高得多，然后将其传递回我的比较。这是我用来测试的脚本:

import random

m = []
for i in range(0, 5):
    w = random.randint(1, 1023)
    p = random.uniform(0.01, 0.99)
    m.append([w, p])

这是一个演示错误的特定测试用例:

m = [[493, 0.7181996086105675], [971, 0.19915848527349228], [736, 0.5184210526315789], [591, 0.5904761904761905], [467, 0.6161290322580645]]

最佳解决方案(仅索引)= [1, 4, 3, 2, 0]我的解决方案(只是索引)= [4, 3, 1, 2, 0]

感觉非常接近，但我终究无法弄清楚哪里出了问题。我是不是看错了？这看起来像是在正确的轨道上吗？非常感谢任何帮助或反馈!

Answer 1

我们不需要有关算法当前状态的任何信息来决定 m 的哪些元素|更好。我们可以使用以下键对值进行排序:

def key(x):
    w, p = x
    return w/(1-p)

m.sort(key=key)

这需要解释。

假设 (w1, p1)就在(w2, p2)之前在数组中。然后处理完这两项后，t将增加 w * (w1 + p1*w2) 的增量和 w将乘以因子 p1*p2 .如果我们调换这些项目的顺序，t将增加 w * (w2 + p2*w1) 的增量和 w将乘以因子 p1*p2 .显然，如果 (w1 + p1*w2) > (w2 + p2*w1)，我们应该执行切换，或者等价地在一点代数之后，如果 w1/(1-p1) > w2/(1-p2) .如果w1/(1-p1) <= w2/(1-p2) , 我们可以说 m 的这两个元素是“正确”排序的。

在 m 的最优排序中, 不会有一对相邻的项目值得切换;对于任何相邻的 (w1, p1)和 (w2, p2) , 我们将有 w1/(1-p1) <= w2/(1-p2) .由于有w1/(1-p1) <= w2/(1-p2)的关系是 w/(1-p) 值的自然总排序，即 w1/(1-p1) <= w2/(1-p2)对任何一对相邻项都成立意味着列表按 w/(1-p) 值排序。

---

您尝试的解决方案失败了，因为它只考虑了一对元素对数组尾部值的影响。它没有考虑这样一个事实，即与其现在使用低 p 元素来最小化尾部的值，不如将其保存以备后用，因此您可以将该乘数应用于 m 的更多元素。

---

请注意，我们算法有效性的证明依赖于所有 p值至少为 0 且严格小于 1。如果 p 为 1，则不能除以 1-p，如果 p 大于 1，则除以 1-p 会反转不等式的方向。这些问题可以使用比较器或更复杂的排序键来解决。如果 p 小于 0，则 w can switch 标志，它反转了应该切换哪些项目的逻辑。然后我们确实需要了解算法的当前状态来决定哪些元素更好，但我不确定接下来该怎么做。