суботу, 17 березня 2018 р.

Динамічне програмування мовою Python

Ця тема не входить в шкільний курс інформатики, проте дуже часто представлена на олімпіаді з програмування. Динамічне програмування - це вже зовсім інший рівень програмування, набагато складніший. Ось, наприклад задача:

Є матриця NxM, де N - кількість рядків, а M - кількість стовпчиків. В кожній клітинці матриці вказано число - кількість енергії, яку витратить робот, якщо потрапить в дану клітинку. Задача робота, починаючи рух з верхнього лівого кута, дійти до нижнього правого, при цьому витратити якомога менше енергії. Робот може рухатися лише вниз і вправо. На виході ми повинні мати рядок тексту (послідовність рухів), який може складатися тільки з двох літер: D (вниз) або R (вправо). Спробую це зобразити, хоча художник з мене ну ніякий)))


Не знаючи принципів динамічного програмування ви можете дійти до наступного розв'язання даної задачі: починати з верхньої клітинки і спускатися до нижнього правого кута, при цьому повертати до тієї клітинки, де знаходиться менше число. Цей метод дехто називає "сліпим рухом", тобто коли ми не бачимо інших значень, окрім сусідніх. Такий принцип цілком може спрацювати, але насправді в цьому випадку розв'язок буде наступним:


Тільки при такій послідовності рухів, робот витратить найменшу кількість енергії (RRDRD), а саме 27. Зверніть увагу на число 0. Хоча воно і найменше, але зовсім не відноситься до правильного шляху.

Саме для цього і потрібне динамічне програмування.

Динамічне програмування — розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління.

Ще одним із способів розв'язку даного завдання був би перебір всіх можливих розв'язків, а потім визначення правильного. Але така програма буде виконуватися годинами, або якщо значення будуть великими, то виконання такої програми може тривати і декілька днів. Але перебір всіх значень і буде вирішенням даної задачі, проте за певною методикою динамічного програмування.

Тож, нам потрібно обійти всі значення матриці і передбачити яка сума буде якщо ми будемо рухатися саме за методом "сліпого руху". Спочатку по вертикалі і горизонталі, бо тут аналіз не потрібен, а потім по внутрішнім клітинкам кожного стовпчика по черзі :



Щоб ви зрозуміли, зверніть увагу, наприклад на клітинку з числом 5. Аналізуємо до якого числа потрібно додати 5, і додамо ми його до min(10, 11), тобто до 10. Тому внизу клітинки і утворилося число 15. Це сума на цьому етапі.
А потім, щоб зрозуміти як нам потрібно рухатися дивимося на шлях із стрілок, який не обривається.


Ну, а тепер, коли ми зрозуміли як нам вирішити задачу, спробуємо створити програмний код.
Спочатку потрібно запитати у користувача числа N i M, а потім і саму матрицю:
N=int(input())
M=int(input())
a=[]
for i in range(N):
    a=a+[[int(i) for i in input().split()]]
А тепер нам потрібно замінити значення першого рядка і першого стовпчика на суму його і попереднього. Не змінним залишиться тільки найперше число:

for i in range(1, M):
    a[0][i]=a[0][i]+a[0][i-1]
 
for i in range(1, N):
    a[i][0]=a[i][0]+a[i-1][0]
Після цього необхідно повторити таку ж процедуру для інших клітинок, але додавати мінімальну суму сусідніх клітинок:

for i in range(1,N):
    for j in range(1,M):
        a[i][j]=a[i][j]+min(a[i-1][j],a[i][j-1])

Ну а тепер все, що потрібно на останок - це починаючи з найнижчої правої клітинки, підніматися до верхньої лівої за допомогою метода "сліпого руху", вказуючи при цьому напрям руху. А потім просто вивести обернений результат (так як ми повинні рухатися у зворотньому напрямку):
r=""
x=M-1
y=N-1
while x!=0 or y!=0:   
    if x==0:
        r=r+"D"
        y=y-1   
    elif y==0:       
        r=r+"R"      
        x=x-1   
    elif a[y-1][x]<=a[y][x-1]:       
        r=r+"D"       
        y=y-1   
    else:       
        r=r+"R"       
        x=x-1
print(r[::-1])
Спробуємо запустити програму та введемо ті дані, які зображені на фото, і перевіримо, чи буде виводитися вірна відповідь:


А виводиться, до речі саме те, що ми й очікували.

Якщо ви бажаєте спробувати свої сили в динамічному програмуванні, рекомендуємо вам спробувати розв'язати задачу про мишу і зернинки на сайті: https://www.e-olymp.com/uk/problems/15

А якщо ви бажаєте почати вчити мову Python, рекомендуємо вам придбати наші навчальні посібники

1 коментар:

  1. Я очень доволен услугами мистера Ли по ссуде, и ваши предложения помогли мне получить очень хорошую сделку по жилищному кредиту. Я был бы рад порекомендовать ваши услуги своим друзьям, ищущим ссуду ».
    Не ходите никуда, если ищете ссуду. Мистер Ли лучший. Я очень рекомендую его услуги. Лучшее, что я когда-либо имел удовольствие работать с его ссудой с низкой процентной ставкой. «Это г-н Ли. Контакт на случай, если кто-то здесь ищет ссуду. Whatsapp: + 1-989-394-3740. & Электронная почта: 247officedept@gmail.com

    ВідповістиВидалити

Динамічне програмування мовою Python

Ця тема не входить в шкільний курс інформатики, проте дуже часто представлена на олімпіаді з програмування. Динамічне програмування - це вж...