10-mavzu. Dinamik dasturlash tamoyillari Dinamik dasturlashning tamoyili

4. Masalalar

Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:

1-qadam. n = 1, S₁(i) = S_i9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 7, 8 nuqtalaridan borish mumkin. Shuningdek: S₁(6) = 15; S₁(7) = 3; S₁(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.
S₄(1) = min {S₁₂ + S₃(2), S₁₃ + S₃(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 S₄(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).

Nazariy topshiriqlar

1.To'la tanlov algoritmi
To'la tanlov (yoki brute force) algoritmini analiz qilishdan oldin algoritm dunyosida asosan 2 ta asosiy tushuncha juda muhim ahamiyatga egadir.
Misol tariqasida tushuntirshga harakat qilaman. Sizga savol qo’limda ma’lumot bor, ushbu ma’lumotni Toshkentdan Londonga yuborishim kerak bu holda qaysi yo’llar orqali yuborsam bo’ladi (masalan:Telegram, facebook, google drive, yandex disk). Siz aytishingiz mumkin ma’lumotni telegramdan yuborishimiz maqul deb chunki tez va qulay. Bu javob doim ham to’g’ri bo’lmaydi sababi siz javob berishdan oldin mendan so’rashingiz kerak edi. Ma’lumotning hajmi qancha deb. Mendagi ma’lumot hajmi 10Gb edi. Endi siz aytgan usul o’zini oqlamasligi mumkin sababi telegram orqali yuborilgan axborot (100Gb lik) tarmoq tezligi 25Mb/s bo’lganda ham yetib borish vaqti 8 soat 53 min 20s da yetib boradi. Eng optimal yo’l samolyotda ma’lumotni yuborsam maqsadga muvofiq bo’ladi.
Istalgan muammoni hal qilishda masala yechimining vaqt va xotiradan oladiga joy jihatlariga alohida e’tibor qaratiladi. Yuqoridagi masala agar ma’lumot telegram orqali yuborilsa biz vaqtdan yutqazar edi.
Algoritmlashda Time Complexity va Space complexity degan tushunchalar mavjud. Endi to’la tanlov algoritmi ni analiz qiklishga kirishsak
To'la tanlov (yoki brute force) algoritmi - matematik muammolarni hal qilish usuli. Har qanday variantni tugatib, echim topish usullari sinfiga tegishli. To'liq qidirishning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan echimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.
To'la tanlov (yoki brute force) algoritmi yuqoridagi vaqt va xotiradan oladigan joy ni deyarli hisobga olmaydi. Bu esa masala yechimini topadi lekin eng yomon holatlarda yechadi degani
NP (non-deterministic polynomial) sinfidagi har qanday muammoni to'liq izlash orqali hal qilish mumkin. Bu holda, har qanday aniq echimdan ob'ektiv funktsiyani hisoblash barcha mumkin bo'lgan echimlarning soniga qarab, ko'paytirilgan vaqt ichida amalga oshirilishi mumkin bo'lsa ham, to'liq qidiruv eksponensial vaqtni talab qilishi mumkin.
Misol tariqasida quyidagi savollarni nazariy jihatdan yechishga harakat qilamiz - bu sayohat qiluvchi sotuvchi muammosi (Traveling Salesman Problem TSP). Aytaylik, sotuvchi butun mamlakat bo'ylab 10 ta shaharga tashrif buyurishi kerak. Qat'iy belgilangan masofani minimallashtirish uchun qaysi shaharlarga borish kerakligini qanday aniqlash mumkin? To'la tanlov (yoki brute force) yechimi oddiygina har bir marshrut uchun umumiy masofani hisoblash va keyin eng qisqa yo'lni tanlashdir. Bu ayniqsa samarali emas, chunki aqlli algoritmlar yordamida ko'plab mumkin bo'lgan yo'nalishlarni yo'q qilish mumkin.

2. Algoritmni loyihalash

Saylovlar barcha shakl va o'lchamlarda bo'ladi. Buyuk Britaniyada bosh vazir rasman monarx tomonidan tayinlanadi, u odatda Jamoatlar palatasida eng ko'p o'rinni egallagan siyosiy partiya rahbarini tanlaydi. Amerika Qo'shma Shtatlari ko'p bosqichli Saylov Kollejidan foydalanadi, bunda fuqarolar har bir shtat Prezidentni saylaydigan saylovchilarni qanday ajratishi kerakligi to'g'risida ovoz beradi. Ehtimol saylovni eng oddiy yo'li "ko'plik ovozi" usuli orqali amalga oshiriladi (xuddi yurtimizdagidek). Ko'pchilik ovoz berishda har bir saylovchi bitta nomzodga ovoz beradi. Saylov oxirida qaysi biri eng ko'p ovoz to'plagan bo'lsa, u g'olib deb e'lon qilinadi.
Masala sharti quyidagicha
Sizga erkanda saylovdagi nomzodlar ismlari berilgan bo’ladi.
Ularning soni #define MAX 5 (const) bu doimiy (MAX ga teng) degan ma'noni anglatadi, bu dastur davomida ishlatilishi mumkin bo'lgan sintaksisdir. Bu erda bu saylovda qatnashishi mumkin bo'lgan nomzodlarning maksimal sonini anglatadi.
Keyin fayl nomzod deb nomlangan tuzilmani belgilaydi. Har bir nomzod ikkita maydonga ega: nomzodning ismini ko'rsatadigan satr va satrda berilgan ovozlar sonini bildiruvchi satr. Keyinchalik, fayl global nomzodlarni belgilaydi, bu erda har bir element o'zi nomzod.
Keyin dastur har bir saylovchiga ovoz berishda qatnashish imkoniyatini beradi int main() funktsiyasiga saylovda g'olibni (yoki g'oliblarni) bosib chiqarish uchun qo'ng'iroq qiladi.
Dastur kompilyatisya qilinganda oyndana quyidachi chiqsa maqsadga muvofiq bo’ladi.
./saylov – bu tuzilgan dasturning nomi ketida nomzodlar ismlari
Ovozlar_soni: 5 ovoz beradigan shaxslarning soni bizda 33 mln bo’lishi mumkin
Tuzmoqchi bo’lgan dasturimiz quyidagicha ishlashi kerak
./saylov Mirziyoyev Saidov Narimanov // dasturning cosole da ishlash jarayoni
Ovozlar_soni: 5
Ovoz: Narimanov
Ovoz: Saidov
Ovoz: Mirziyoyev
Ovoz: Mirziyoyev
Ovoz: Mirziyoyev
Mirziyoyev // g’alaba qozongan nomzod nomi
Dastur implementatsiyasi
#include
#include
#include
//Nomzodlarning maksimal soni
#define MAX 5
//Nomzodlarning ismi va ular to’plagan ovozlarini yozish uchun o’zgaruvchilar
typedef struct
{
string name;
int votes;
}
candidate;
// Nomzodlar massivi
candidate candidates[MAX];
// Nomzodlar soni
int candidate_count;
// Funksiya prototipi asl funksiya pastda yozilgan
bool vote(string name);
void print_winner(void);
int main(int argc, string argv[])
{
// Dastur ishga tushirilganda uning to’g’ri ishlashini tekshirish
if (argc < 2)
{
printf("To’g’ri qiymat kiriting: saylov [Nomzodlar...]\n");
return 1;
}
// Nomzodlar quyidagilar
candidate_count = argc - 1;
if (candidate_count > MAX)
{
printf("Saylovdagi mavjud nomzodlarnning umumiy soni %i\n", MAX);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
}
int voter_count = get_int("Ovozlarning umumiy soni: ");
// ovozlar bo’yicha yurib chiqish
for (int i = 0; i < voter_count; i++)
{
string name = get_string("Ovoz: ");
// Ovozni tekshirish
if (!vote(name))
{
printf("Noto’g’ri ovoz kiritfingiz.\n"); }
}
// Saylov g’olibi
print_winner(); }
// Berilgan ovoz bilan umumiy ovozlarni yangilash
bool vote(string name)
{
bool exist = false;
for (int i = 0; i < candidate_count; i++)
{
//Kiritilgan nomzodning ismi bazadagisi bilan solishtirish
if (strcmp(name, candidates[i].name) == 0)
{
candidates[i].votes += 1;
exist = true;
break; }
}
return exist;
}

void print_winner(void)

{
//o’zgaruvchilarga boshlang’ich qiymat berish
int most = 0;
string winner;
//Eng ko’p ovozni aniqlash
for (int y = 0; y < candidate_count; y++)
{
if(candidates[y].votes >= most )
{
most = candidates[y].votes;
winner = candidates[y].name;
}
}
printf("Nomzod %s %i ovoz bilan g’olib bo’ldi\n", winner , most);
}