Оптимизация этого динамического программного решения

Задача:



Вам дается массив m размера n, где каждое значение m состоит из веса w и процента 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, - это его упорядоченность. (то есть переставить элементы 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]



Это кажется очень близким, но я ни за что на свете не могу понять, что со мной не так. Может быть, я смотрю на это неправильно? Делает похоже, все идет по верному пути? Любая помощь или обратная связь будут очень признательны!
623   1  

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 может переключать знак, который меняет логику того, какие элементы следует переключать. Тогда мы действительно должны знать о текущем состоянии алгоритм, чтобы решить, какие элементы лучше, и я не уверен, что делать дальше.

6  
2015-07-03 11:50:58

Comments

    Ничего не найдено.
Click here to cancel reply.