优化这种动态编程解决方案

Question

问题:

你给出的阵列米大小的Ñ,其中的每个值米由重量的瓦特和百分比p.

m = [m0, m1, m2, ... , mn] = [[m0w, m0p], [m1w, m1p], [m2w, m2p], ..., [mnw, mnp] ]

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

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

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的元素)此外,这需要比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).由于has的关系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可以切换符号,这反转了应该切换的项目的逻辑.然后,我们就需要了解该算法的当前状态,以决定哪些元素是更好的,我不知道该怎么做呢.