LINUX-BG   Адрес : http://www.linux-bg.org
Въведение в динамичната оптимизация
От: vesso
Публикувана на: 30-08-2005
Адрес на статията: http://www.linux-bg.org/cgi-bin/y/index.pl?page=article&id=devs&key=374961042
Въведение в динамичната оптимизация

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

Първи опит: Осланяме се на инстинктите си. Знаем че колкото повече едри монети ползваме толкова по-малък брой монети ще са необходими. Затова взимаме най-голямата монета (която все пак е по-малка от сумата), намаляваме сумата със стойността на монетата и извикваме същата функция с намалена сума но и с една монета по-малко. Когато сумата стигне до нула връщаме 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 | Програмиране под Линукс. Въведение за начинаещи. >>

Авторите на сайта, както и техните сътрудници запазват авторските права върху собствените си материали публикувани тук, но те са copyleft т.е. могат свободно да бъдат копирани и разпространявани с изискването изрично да се упоменава името на автора, както и да се публикува на видно място, че те са взети от оригиналния им URL-адрес на този сървър (http://www.linux-bg.org). Авторските права на преводните материали принадлежат на техните автори. Ако с публикуването тук на някакъв материал неволно са нарушени нечии права - след констатирането на този факт материалът ще бъде свален.

All trademarks, logos and copyrights mentioned on this site are the property of their respective owners.
Linux is copyright by Linus Torvalds.
© Линукс за българи ЕООД 2007
© Slavei Karadjov 1999 - 2006

All rights reserved.

Изпълнението отне: 0 wallclock secs ( 0.16 usr + 0.02 sys = 0.18 CPU)