1. Dinamik dasturlashning tamoyili Dinamik dasturlash masalalarini yechish sxemasi



Download 115,71 Kb.
bet3/3
Sana22.07.2022
Hajmi115,71 Kb.
#836785
1   2   3
Bog'liq
AL 10 maruza dinamik dastur

4. Masalalar

Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:


1-qadam. n = 1, S1(i) = Si9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 7, 8 nuqtalaridan borish mumkin. Shuningdek: S1(6) = 15; S1(7) = 3; S1(8) = 10.
2-qadam. N = 2, bu yerda biz uchinchi bosqichning (4 va 5) nuqtalaridan ikkinchi bosqichga qadar bo'lgan yo'llarni ko'rib chiqamiz. Bu yerda funktsional Bellman tenglamasi quyidagi shaklga ega bo’ladi:

Shuningdek quyidagiga ega bo’lamiz:

Shartli ravishda optimal yo'l (5-7);

Shartli ravishda optimal yo'llar (4-6 va 4-8).


3-qadam. n = 3, bu yerda to'rtinchi bosqichning (2 va 3) nuqtalaridan uchinchi bosqichgacha bo'lgan yo'llarni ko'rib chiqiladi.

Shartli ravishda optimal yo'l (2–5).

Shartli optimal yo'l (3-4).


4-qadam. n = 4, bu erda 1-nuqtadan to'rtinchi bosqichning nuqtalarigacha bo'lgan yo'llarni ko'rib chiqiladi.
S4(1) = min {S12 + S3(2), S13 + S3(3)} = min {(1 + 22); (2 + 20);} = 22.
Shartli ravishda optimal yo'l (1-3).
Endi biz 1-nuqtadan 9-gacha bo'lgan eng qisqa shartsiz yo'lni topamiz. Shartli optimallashtirish bosqichida minimal yo'lning uzunligi S4(1) = 22 ekanligi aniqlandi, bu natija birinchi nuqtadan uchinchisiga o'tganda erishiladi, keyin to'rtinchisiga o'tish kerak. Ushbu bosqichdan boshlab, 2-bosqichda ko'rsatilgandek, 6 va 7-nuqtalarga ikkita mumkin bo'lgan ekvivalent yo'nalish mavjud. Shunday qilib, optimal yechimga 10.2-rasmda ko'rsatilgan ikkita yo'nalish orqali erishiladi, aniqrog'i (1-3–4–6–9) va (1-3–4–8–9).



10.2-rasm. Optimal yo’l
Dinamik dasturlash odatda muammolarni yechishda ikkita yondashuvga amal qiladi:
Yuqoridan pastga: vazifa kichikroq qismlarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Tez-tez uchraydigan kichik qismlarni yechimlari xotirada saqlanadi.
Quyidan yuqoriga: Dastlabki muammoni hal qilish uchun kerak bo'ladigan barcha pastki jadvallar oldindan hisoblab chiqiladi va keyinchalik asl muammoni hal qilishda foydalaniladi. Ushbu usul kerakli stek hajmining kattaligi va funktsiyalarni chaqirish soni nuqtai nazaridan yuqoridan pastga bo'lgan dinamik dasturlashga qaraganda yaxshiroqdir, ammo ba'zida kelajakda biz uchun qaysi kichik masala natijasi kerak bo'lishini oldindan aniqlash oson emas.
Odatda dinamik dasturning ishlash vaqti quyidagi funktsiyalardan iborat:

Umuman olganda, ish vaqti quyidagi shaklda bo'ladi:
Dastlabki ishlov berish + Loop * Takrorlash + Post-ishlash
Dinamik dasturlar uchun katta-O bilan tanishish uchun punchcard muammosining ishlash vaqtini tahlil qilaylik. Bu yerda punchcard muammolari dinamik dasturi:
def punchcardSchedule (n, qiymatlar, keyingi):
# Eslatma qatorini boshlang - 4 bosqich
memo = [0] * (n + 1)
# Asosiy korpusni o'rnatish
memo [n] = qiymatlar [n]
# N dan 1 gacha xotiralar jadvalini tuzing - 2 bosqich
diapazondagi i uchun (n-1, 0, -1):
memo [i] = maks (v_i + memo [next [i]], memo [i + 1])
# OPT (1) muammosiga echim - 3 bosqich
qaytish eslatmasi [1]
Uning ish vaqti buzilsin:

  • Dastlabki ishlov berish: Bu yerda yodlash massivini yaratish kerak. O (n).

  • Loop necha marta ishlaydi: O (n).

  • Loop iteratsiyasi uchun birida ishlash uchun takroriylik qancha vaqtni oladi: takrorlanish doimiy ishlash vaqtini oladi, chunki har bir iteratsiyada ikkita variant o'rtasida qaror qabul qilinadi. O (1).

  • Post-qayta ishlash: Bu yerda yo'q! O (1)

Muammoli dinamik dasturning umumiy ish vaqti O (n) O (n) * O (1) + O (1) yoki soddalashtirilgan shaklda O (n).




Nazorat savollari



  1. Dinamik dasturlashning umumiy vazifasini qanday o'rnatish kerak?

  2. Dinamik dasturlash muammosi qanday shakllantirilgan va uning chiziqli dasturlash muammolaridan farqi nimada?

  3. Dinamik dasturlashning matematik modelining xususiyatlari qanday?

  4. Dinamik dasturlash usulining asosi nimada?

  5. Optimallashtirish tamoyili nima va Bellman tenglamalari qanday yozilgan?

Download 115,71 Kb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish