от vesso(30-08-2005)

рейтинг (23)   [ добре ]  [ зле ]

Printer Friendly Вариант за отпечатване

Въведение в динамичната оптимизация

Задача: Имаме определен брой монети от различни деноминации. Имаме и сума която трябва да платим. Да се напише функция която да изчисли минималния брой монети необходими за плащане на сумата. Ако не можем да формираме сумата с наличните монети функцията трябва да върне число по-голямо от броя на монетите като индикация за грешка.

Първи опит: Осланяме се на инстинктите си. Знаем че колкото повече едри монети ползваме толкова по-малък брой монети ще са необходими. Затова взимаме най-голямата монета (която все пак е по-малка от сумата), намаляваме сумата със стойността на монетата и извикваме същата функция с намалена сума но и с една монета по-малко. Когато сумата стигне до нула връщаме 0 монети. Когато броя монети стигне до 0 връщаме 1 (грешка). На питон функцията изглежда така:

def coins1(purse, amount):
     if amount == 0:
         return 0
     if amount < 0 or len(purse) == 0:
         return len(purse) + 1
     purse.sort()
     for index in range(len(purse) - 1, -1, -1):
         if purse[index] <= amount:
             new_purse = purse[:index] + purse[index+1:]
             new_amount = amount - purse[index]
             return 1 + coins1(new_purse, new_amount)
     return len(purse) + 1

Тестваме набързо:

print coins1([50], 20), ' -> >1'
print coins1([50], 50), ' -> 1'
print coins1([10, 20, 50], 20), ' -> 1'
print coins1([5, 5, 10, 10, 10, 20, 50], 25), ' -> 2'
print coins1([5, 5, 10, 10, 10, 50], 25), ' -> 3'
print coins1([5, 5, 10, 20, 20, 20, 50, 50], 60), ' -> 2'

Нещата изглеждат добре ... докато не пробваме:

print coins1([2, 2, 2, 5], 6), ' -> 3'

Очакваме резултат 3 (3 монети по 2 ст) но функцията връща 5, т.е. не може да направи сумата от зададените монети. А не може защото веднъж решила да ползва монетата от 5 ст няма как да направи остатъка от 1 ст.

Този алгоритъм може да се усложни така че ако не може да направи new_amount да опита с по-малка монета - тогава винаги ще успява и извикването coins1([2, 2, 2, 5], 6) ще връща коректна стойност. Обаче извикване coins1([1, 1, 1, 1, 1, 1, 5, 20, 20, 20, 50], 60) ще връща 7 (50 + 5 + 1 + 1 + 1 + 1 + 1) вместо коректното 3 (20 + 20 + 20).

Описаният алгоритъм в опит 1 е алчен (greedy) защото винаги започва от най-голямото кандидат-решение. Тези алгоритми са лесни за писане и работят бързо но не винаги работят коректно.


Втори опит: Явно настояването да ползваме най-голямата монета не винаги е удачно. Затова за всяка монета ще опитаме какво ще стане (1) ако монетата участва и (2) ако монетата не участва в сумата. След това ще вземем по-доброто решение. Отново се оформя рекурсивна функция:

def coins2(purse, amount):
     if amount == 0:
         return 0
     if amount < 0 or len(purse) == 0:
         return len(purse) + 1
     without = coins2(purse[1:], amount)
     if without >= len(purse):
         without = len(purse) + 1
     with = coins2(purse[1:], amount - purse[0])
     if with >= len(purse):
         with = len(purse) + 1
     return min([without, with + 1])

Пускаме горните тестове и всичко върви добре, включително и тези примери които затрудняваха първата функция ... докато не опитаме:
print coins2([1, 1, 1, 1, 1, 1, 2, 2, 5, 5, 5, 10, 10, 10 ,10, 20, 20, 20, 20, 50, 50, 50], 275), ' -> 12'

Функцията работи вярно но неприемливо дълго време. Причината е че ако има 1 монета функцията че обработи 2 случая (2^1) - единия със а другия без монетата. Ако има 2 монети функцията ще обработи 4 случая (2^2) и съответно ако има N монети функцията ще трябва да обработи 2^N случая. Или записано в т.нар. О нотация сложността на функцията е О(2^N). Такава функция, дори написана на асемблер, ще работи години наред да сметне сума от стотина монети.


Трети опит: решение с динамична оптимизация.

Името на понятието "динамична оптимизация" идва от поведението на програмите които динамично изграждат таблици с междинни резултати. Ползвайки тези междинни резултати лесно и бързо се стига до крайния резултат. Ето и функцията:

def coins3(purse, amount):
     big = len(purse) + 1
     current_row = [0]
     for amount_idx in range(amount):
         current_row.append(big)
     all_rows = [current_row]
     for coin in purse:
         prev_row = current_row
         current_row = []
         for amount_idx in range(amount + 1):
             if amount_idx < coin:
                 current_row.append(prev_row[amount_idx])
             else:
                 without = prev_row[amount_idx]
                 with = 1 + prev_row[amount_idx - coin]
                 current_row.append(min([with, without]))
         all_rows.append(current_row)
     return current_row[amount]

Обяснение:
Нека извикаме функцията с coins3([2, 2, 2, 2, 5, 5, 10], 11). Функцията си избира произволен код за "невъзможна комбинация", по-голям от броя на монетите. След това си създава един списък (едномерен масив) със следното съдържание:

[0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]

Списъкът има толкова елемента колкото е сумата която ни трябва (11) плюс едно (за сума 0). Смисълът на така полученият ред е че с никакви монети (защото още никакви монети не са обработени) можем да постигнем сума 0 със 0 монети (първия елемент) и не можем да направим никакви други суми (8 = код за невалидна сума). Индексът в този списък е сумата която искаме да направим, а стойностите - броя монети необходими за постигането на сумата.

След това за всяка монета си създаваме нов списък, в които:
- Ако индексът (сумата) е по-малък от монетата просто копираме стойностите от предишния ред.
- в противен случай сравняваме броя монети от същия индекс на предишния ред (т.е. броя монети без текущата) с едно плюс броя монети от предишния ред, необходим за постигане на сума намалена със стойността на текущата монета. Добавяме по-малката от тези стойности към текущия ред.

След обработване на първата монета (2 ст) списъкът изглежда така:

[0, 8, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8],

Смисълът на това е че с 0 монети можем да постигнем сума 0, с 1 монета можем да постигнем сума 2 (индекс 2) а останалите суми не могат да бъдат направени с 1 монета от 2 ст.

Когато програмата завърши списъкът all_rows съдържа следното:

[
[0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 3, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 8, 8],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 8, 4],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 2, 4],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 1, 4]]

Последният ред съдържа броя монети необходими за сума равна на индекса в реда. Можем да постигнем:
- с 0 монети: сума 0
- с 1 монета: сума 2, 5 и 10 ст (с такива монети разполагаме)
- с 2 монети: суми 4 и 7 ст.
- с 3 монети: суми 6 и 9 ст.
- с 4 монети: суми 8 и 11 ст.
- не можем да направим суми 1 и 3 ст.

Отговорът на нашата задача е в последния ред, последната колона.
Парадокс е че намерихме решенията на всички суми по-малки от търсената, при това - поне в някои случаи - по-ефективно отколкото намирането само на едно решение от втория ни опит.

По-внимателните може би са забелязали че към списъкът all_rows само се добавя но от него не се чете. Програмата може да работи чудесно и без него. Такъв списък е необходим когато искаме да видим кои монети участват в решението. Правилото е:
1. Тръгваме от долния десен ъгъл и от последната монета
2. Сравняваме числото над текущото:
2.1. Ако е същото значи текущата монета не участва в резултата. Запазваме същия индекс.
2.2. Ако е различно значи текущата монета участва в резултата. Намаляваме индекса със стойността на текущата монета.
3. Минаваме на по-горния ред и на предишната монета.
4. Ако сме стигнали до 0 сме готови, в противен случай отиваме на т. 2.


Задачи за упражнение:

1. Преправете функцията coins3 така че да използва само един списък (едномерен масив)

2. Пешо има да дава на Гошо дадена сума. Знаем какви монети имат и Пешо и Гошо. Да се напише програма която да изчисли минималния брой монети сменяващи собственика си така че Пешо да се издължи. Знаем че е допустимо Гошо да връща ресто. Функция:

def exer2(pesho_coins, gosho_coins, amount):

Извикване:

print exer2([10, 10, 20, 50], [5, 10, 20], 40)

резултат: 2 - Пешо дава една монета от 50 и получава ресто една монета от 10

3. Можем да носим максимум X кг. Има N предмета с тегло Gi kg и стойност Vi. Каква е максималната стойност на предметите които можем да вземем. Функция:

def exer3(MaxWeight, Weights, Values):

Извикване:

print exer3(50, [24, 25, 45], [5, 6, 10])

резултат: 11 - първия и втория предмет

(Подсказка: Google "knapsack problem")


24 Август 2005
Веселин Костадинов

Редакция от 31 Август 2005: Вместо термина "динамична оптимизация" статията ползваше "динамично програмиране" (буквален превод от английския термин "dynamic programming"). Благодаря на d.vasilev.


<< Крайна цел: FreeBSD | Програмиране под Линукс. Въведение за начинаещи. >>