5 laboratoriya ishi mavzu: Dinamik dasturlash masalasini yechish Ishning maqsadi

5 - LABORATORIYA ISHI

Mavzu: Dinamik dasturlash masalasini yechish

Ishning maqsadi: Masalalarni yechishda dinamik dasturlash usullaridan foydalanishni o'rganish, dinamik dasturlash usullari uchun algoritmlar tuzish va ularning vaqt bo’yicha samaradorligini aniqlash ko'nikmalariga ega bo'lish.

Nazariy qism.

Ushbu mavzuni amaliy jihatda o’rganish uchun kommivoyajer masalasidan foydalanamiz. Kommivoyajer-daydi sotuvchi maʼnosini bildirib, masalaning qoʼyilishi juda ham soddadir. Yaʼni kommivoyajer h ta shaharning har biriga faqat bir martadan tashrif buyurib, barcha shaharlarni shunday aylanib chiqishi kerakki, natijada umumiy ketadigan xarajat (chiqim, sarf) minimal boʼlsin. Аgar, biz shaharlarni bir marta aylanib chiqishni marshrut deb atasak, aniqki, bunday marshrutlar soni koʼpi bilan (h-1)!ta boʼladi.

Kommivoyajer masalasi NP sinfiga tegishli. Bizga shaharlar toʼplami va ular orasidagi sayohat «narxi» berilgan. Shunday tartibni aniqlash kerakki, hamma shaharlarga tashrif buyurib, dastlabki shaharga qaytib kelganda, sayohatning umumiy narxi minimal boʼlsin.

Har bir shaharni grafning choʼqqisi, shaharlar orasidagi yoʼlni qirralar, ular orasidagi sayohat bahosini shu qirraning ogʼirligi deb tasavvur qilishi mumkin. Bundan shunday xulosa chiqarish mumkinki, qisqa yoʼlni qidirish algoritmi kommivoyajer masalasini hal qiladi, biroq bu unday emas. Kommivoyajer haqidagi masalaning qanday ikki sharti uni qisqa yoʼl haqidagi masaladan farqlaydi? Birinchidan biz hamma shaharlarga tashrif buyurishimiz kerak, qisqa yoʼlni izlash algoritmi esa berilgan ikki shaharlar orasidagi yoʼlni beradi. Аgar qisqa yoʼlni tanlash algoritmi bergan qisqa boʼlakli yoʼlni yigʼsak, bu yoʼl baʼzi shaharlardan bir necha marta oʼtadi. Ikkinchi farq qisqa yoʼlni izlashda dastlabki nuqtaga qaytishni talab qilishdan iborat. Bu masala NP sinfiga tegishli ekanligini koʼrsatish uchun uni yuqorida yoritilgan ikki qadamli amal yordamida qanday yechish mumkinligini tushunish zarur.

Kommivoyajer haqidagi masalaning birinchi qadamida shaharlarning baʼzi tartiblashtirilishi asosiy oʼringa chiqadi. Bu determinallashmagan jarayon boʼlganligi uchun har safar yangi tartib paydo boʼladi. Generatsiya jarayonini polinomial vaqtda amalga oshirish mumkin: biz shaharlar roʼyxatini saqlashimiz mumkin, tasodifiy raqamni asosiylashtirishimiz, shu nomdagi shaharni roʼyxatdan tanlashimiz va u Yana paydo boʼlmasligi uchun roʼyxatdan chiqarishimiz mumkin. Bunday jarayon O(N) ichida amalga oshiriladi, bu yerda N – shaharlar soni. Ikkinchi qadamda berilgan tartibdagi shaharlar boʼyicha sayohatlar bahosini hisoblash amalga oshiriladi. Buning uchun biz roʼyxatdagi shaharlarning ketma-ket juftlari orasidagi sayohat bahosini jamlashimiz kerak, buning uchun ham O(N) jarayoni talab qilinadi. Ikala qadam ham polinomial, chunki kommivoyajer masalasi NP sinfiga tegishli.

Tarmoqlar va chegaralar usuli. Kommivoyajer masalasini yechish uchun tarmoqlar va chegaralar usulini qoʼllanishini koʼramiz. Faraz etaylik Cij sonlari i shahardan j-shaharga oʼtish uchun ketadigan xarajatni bildirsin. Аgar i shahardan j shaharga oʼtishning iloji boʼlmasa, Cij ni yetarlicha katta son deb olamiz (buni Cij=∞ deb belgilaymiz), i-shahardan yana i-shaharga oʼtildi, deyish maʼnosiz boʼlganligi sababli Cij =∞ deb olinadi. Shundan soʼng NxN oʼlchamli (Cij) jadval (matritsa) hosil boʼladi, u xarajat jadvali deb ataladi. Yana bir bor taʼkidlab oʼtamizki, jadvalning i satri j ustuni kesishgan joydagi Cij yelement i-shahardan j-shaharga oʼtish uchun ketgan sarf-xarajatni bildiradi. Endi jadvalni keltirish tushunchasini kiritamiz. Buning uchun, avval jadval satrlari keltiriladi, yaʼni jadvalning har bir satr elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi. Demak, keltirilgan jadvalning har bir satri va ustunida kamida bitta nol element ishtirok etgan boʼladi. Jadval satr va ustunlari eng kichik elementlarining yigʼindisi h bilan belgilanib, u jadvalning keltirish koeffitsienti deyiladi. Misol sifatida quyidagi harajat jadvalini koʼraylik:


C =

Jadval satrlarini keltirish uchun, uning oʼng tarafiga mos satrning eng kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi jadvalga ega boʼlamiz:

C* =

Hosil boʼlgan C* jadvalning ustunlarini keltirish maqsadida jadval ostiga mos ustunning eng kichik elementi yoziladi va u ustun elementlaridan ayirib chiqiladi, natijada quyidagi jadval hosil boʼladi:


C** =

C ** jadval keltirilgan boʼlib, uning har bir satr va ustunida kamida bittadan nol element bor. Koʼrilayotgan jadvalning keltirish koeffitsienti h quyidagi songa teng
h=3+1+2+1+4+4+0+3+0+0+0+0=18.
Keltirish koeffitsienti h eng kam xarajatli oʼtishlarning umumiy harajatini bildirib, bu xarajatni beruvchi marshrutni xar vaqt ham aniqlab boʼlmaydi. Yuqorida koʼrilgan misolda eng kam harajatli (h=18) marshrutni aniqlasak, u ikkita bir biriga bogʼlanmagan oʼtishlardan (tsikllardan) iborat boʼlib qoladi, yaʼni 1→5→3→2→1 va 4→6→4. Bu esa qoʼyilgan masalaning yechimini bermaydi. Demak, jadvalni keltirish bilan har vaqt ham qoʼyilgan masalaning yechimini olib boʼlmas ekan. Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqichdan iboratdir:

1) tarmoqlash;

2) chegaralarni aniqlash.

Bu graf oʼzaro birlashtirilgan doirachalardan iborat boʼlib, ularning har biri maʼlum bir xossali marshrutlar toʼplamini aniqlaydi. Yuqorida koʼrgan misolda h=18 edi, demak, xarajati 18 dan kichik boʼlgan marshrut yoʼq ekan. Barcha marshrutlar toʼplamini tarmoqlash uchun keltirilgan C** jadvalning nol elementlari darajalari aniqlanadi. Masalan, C₁₅**=0 ning darajasini topish uchun, birinchi satrdagi eng kichik element-1ga, beshinchi ustundagi eng kichik element-1 qoʼshiladi va hosil boʼlgan 2 soni shu nolning darajasi sifatida yozib qoʼyiladi. Xuddi shunday C₃₂**=0 ning darajasini topish uchun uchinchi satrdagi eng kichik-0 ga ikkinchi ustundagi eng kichik element - 4 qoʼshiladi va hosil boʼlgan 4 soni C₃₂ **ning darajasi sifatida yozib qoʼyiladi. Darajasi eng katta boʼlgan nol element C₅₃ **=0 dir, demak, tarmoqlanish grafi koʼrinishda boʼladi. Jadvalning oʼlchami bittaga kamayadi. Bunda, shuni alohida taʼkidlash lozimki, shaharlarning tartib raqamlari albatta saqlanib (yozilib) qolishi shart, aks holda chalkashliklar kelib chiqadi. Shundan soʼng, toʼla boʼlmagan marshrut i→j, j→i (i→j) belgi i-shahardan j-shaharga oʼtishni bildiradi) yoʼqotiladi, buning uchun C_ij**element belgisiga almashtirilib yozib qoʼyiladi. Bizning misolda bu jadval quyidagi koʼrinishga ega boʼladi:

Shundan soʼng, hosil boʼlgan yangi jadval keltirilib, uning keltirish koeffitsienti, oldingi keltirish, koeffitsienti boʼlgan h ga qoʼshib yoziladi (h₂*). Oxirgi jadvaldan koʼrinib turibdiki, u keltirilgan jadval ekan, demak, uning keltirish koeffitsienti nolga teng. Bunda belgini olgan chap doirachaga mos chegara (h₄), h₁ga nolning eng katta darajasi qoʼshib aniqlanadi. ( k, l ) belgili oʼng doirachaga mos kelgan chegarani (h₃*) topish uchun oxirgi jadvaldan k-satr va l-ustun chiqarib (oʼchirib tashlanadi) va toʼla boʼlmagan marshrutlar ∞ belgisi yordamida taqiqlanadi. Shundan soʼng, hosil boʼlgan jadvalning keltirish koeffitsienti h ga h₁* qoʼshilib oʼng doiracha yoniga yozib qoʼyiladi.

k, l juftlik sifatida 3→2ni, yoki 6→4ni olish mumkin. Masalan, 3→2ni olaylik. U holda quyidagi grafga ega boʼlamiz. (2,1) belgili doirachada 5→3→2→1 oʼtishlarni oʼz ichiga olgan marshrutlar toʼplami boʼlib, toʼla boʼlmagan 5→3→2→1→5 marshrutni yoʼqotish maqsadida birinchi satr, beshinchi ustun kesishgan elementni ∞ belgiga almashtiramiz va ikkinchi satr birinchi ustunni oʼchirib tashlaymiz, natijada, quyidagi jadval hosil boʼladi:

Kommivoyajer masalasini eng kam xarajatni topish masalalarni yechishda ham ishlatish mumkin.