14-amaliy ish np-to’liq masalalar np-to’liq masalalarga keltirish usullari

4. Kommivoyajer masalasi uchun algoritmlar
Deykstra algoritmi

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.

Tarmoqlar va chegaralar usuli

Аgar, biz shaharlarni bir marta aylanib chiqishni marshrut deb atasak, aniqki, bunday marshrutlar soni koʼpi bilan (h-1)!ta boʼladi.

Biz tarmoqlar va chegaralar usulini kommivoyajer masalasini yechish uchun qoʼllanishini koʼramiz. Faraz etaylik cij sonlari ishahardan 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 cijelement 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’ramiz:

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.

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 ** 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 S** jadvalning nol elementlari darajalari aniqlanadi. Masalan, c15 **=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 c32 **=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 c32 **ning darajasi sifatida yozib qoʼyiladi. Darajasi eng katta boʼlgan nol element s53 **=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 Cij**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 (h2*). Oxirgi jadvaldan koʼrinib turibdiki, u keltirilgan jadval ekan, demak, uning keltirish koeffitsienti nolga teng. Bunda (k,l) ̅ belgini olgan chap doirachaga mos chegara (h4), h1ga nolning eng katta darajasi qoʼshib aniqlanadi.(k,l) belgili oʼng doirachaga mos kelgan chegarani (h*3) 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*1 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: