Reja: Algoritm tushunchasi



Download 6,66 Mb.
bet62/87
Sana31.12.2021
Hajmi6,66 Mb.
#252783
TuriПрограмма
1   ...   58   59   60   61   62   63   64   65   ...   87
Bog'liq
Algotim loyiha toliq maruza

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:



  • Oldindan ishlov berish

  • Loop for loopi necha marta ishlaydi

  • Qayta ishlashni takrorlash uchun birida ishlash uchun qancha vaqt ketishi kerak

  • Post-qayta ishlash

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).



Download 6,66 Mb.

Do'stlaringiz bilan baham:
1   ...   58   59   60   61   62   63   64   65   ...   87




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