 |
от vesso(30-08-2005)
рейтинг (23)
[  добре ]
[  зле ]
 Вариант за отпечатване
Въведение в динамичната оптимизация
Задача: Имаме определен брой монети от различни
деноминации. Имаме и сума която трябва да платим. Да се
напише функция която да изчисли минималния брой монети
необходими за плащане на сумата. Ако не можем да формираме
сумата с наличните монети функцията трябва да върне число
по-голямо от броя на монетите като индикация за грешка.
Първи опит: Осланяме се на инстинктите си. Знаем че колкото
повече едри монети ползваме толкова по-малък брой монети ще
са необходими. Затова взимаме най-голямата монета (която все
пак е по-малка от сумата), намаляваме сумата със стойността
на монетата и извикваме същата функция с намалена сума но и
с една монета по-малко. Когато сумата стигне до нула връщаме
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 | Програмиране под Линукс. Въведение за начинаещи. >>
|
|
