O’zbekiston respublikasi

Sakrab chiquvchi qurbaqa muammosi
Leaping Toad muammosi (yoki oddiygina LTP) maxsus yo'naltirilgan asiklik grafikda aylanib o'tish muammosi sifatida umumlashtirilishi mumkin, bunda qurbaqa vaznli grafik bo'ylab sayohat qiladi va maqsad bosh va maqsad cho'qqilarini bog'laydigan yo'lni topish, shu bilan birga minimallashtirish. yo'l bo'ylab chekka xarajatlar yig'indisi.
LTP ning yo'naltirilgan asiklik grafigi quyidagicha tavsiflanadi:
2 o'lchovli cho'qqilar panjarasidan olingan cho'qqilarni o'rab turgan qavariq suzish havzasi mavjud bo'lib, u erda cho'qqilar satr va ustunlarda tekislanadi . Keyin suzish havzasidagi cho'qqilar cho'qqilar panjarasidagi qatorlar bo'lgan ajratilgan bo'laklarga bo'linadi . Bo'lakning ichida har bir cho'qqi o'zining o'ng tomonidagi keyingi cho'qqi bilan yo'naltiruvchi chekka bilan bog'langan, o'zi manba va o'ng tomondagi cho'qqi esa maqsad hisoblanadi. Biz bu qirralarni oldinga qirralar deb ataymiz . Oldinga qirralar faqat suzish havzasi ichidagi cho'qqilar orasida mavjud va suzish havzasidan tashqaridagi cho'qqilar uchun mavjud emas.
Cho'qqining boshqa chiziqlardagi cho'qqilarga ishora qiluvchi qirralari ham bo'lishi mumkin. Biz bu qirralarni sakrash qirralari deb ataymiz . LTPda, cho'qqi va alohida bo'lak uchun, bu bo'lakda ko'pi bilan bitta cho'qqiga ishora qiluvchi ko'pi bilan bitta sakrash chekkasi bo'lishi mumkin. Boshqacha qilib aytganda, bitta cho'qqidan bir xil chiziqqa ishora qiluvchi bir nechta qirralar bo'lishi mumkin emas. Biz, shuningdek, bir xil chiziqdagi barcha cho'qqilarning bir xil turdagi sakrash qirralarini bo'lishlarini talab qilamiz: bir xil yo'nalish va uzunliklar. Ko'rinib turganda, ikkita chiziq orasidagi sakrash qirralari parallel o'qlar qatoridir. E'tibor bering, ba'zi sakrash qirralarining manba va/yoki maqsad cho'qqilari suzish havzasidan tashqarida bo'lishi mumkin va biz bu chekkalarni chetlar deb ataymiz . Hovuz muhofazasidan tashqarida turli yo'laklar orasidagi cho'qqilarni bog'laydigan tashqi qirralar mavjud.
Har qanday chekkada manfiy bo'lmagan butun son og'irligi mavjud. Bir xil kelib chiqish va boradigan yo'llarni taqsimlovchi sakrash qirralari bir xil, ijobiy vaznga ega. Oldinga qirralarning nol yoki musbat og'irliklari bor. To'siqlar sifati-da ijobiy og'irlikdagi oldinga qirralarni chaqiramiz . To'siqdan o'tish, to'siqdan o'tish deyiladi . To'siqlar har xil xarajatlarga ega bo'lishi mumkin.
Hovuzda biz bir qator qatorlarni boshlang'ich yo'lak sifatida va bir qator qatorlarni maqsad yo'lak sifatida belgilaymiz . Kelish yo'llari va boradigan yo'laklar to'plami bir-biriga mos kelishi mumkin. LTP ning umumiy maqsadi yo'naltirilgan grafikda chekka og'irliklarining minimal yig'indisiga ega bo'lgan yo'lni topishdan iborat bo'lib, u boshlang'ich bo'lakning birinchi cho'qqisidan (bo'lakning suzish havzasidagi eng chap cho'qqi) boshlanadi va yoki yo'nalishga boradi. belgilangan yoʻlakning oxirgi choʻqqisi yoki belgilangan yoʻlga chiqayotganda suzish havzasidan tashqariga chiqish.
Oddiylik uchun biz chekka og'irliklarni energiya xarajatlari deb ataymiz ; biz sakrashlar deb sakrab chekka bo'ylab sayohat deymiz . Bundan tashqari, yechimni ishlab chiqishning soddaligi uchun biz barcha sakrab chiqadigan qirralarning chapdagi oldingi ustunlardagi cho'qqilarga hech qachon orqaga qaramasligini talab qilamiz. Ushbu cheklovni yumshatish Muhokama bo'limida muhokama qilinadi yo'lni almashtirmaydi yoki faqat to'siqlardan oldin o'tadi.
Teoremani isbotlashdan oldin, biz avval ba'zi terminologiyani aniqlaymiz: biz boshlang'ich cho'qqidan maqsad cho'qqigacha bo'lgan yo'lga oddiygina yo'l sifatida murojaat qilamiz . Yo'lda hech qanday bo'lak kalitlari bo'lishi mumkin yoki bo'lmasligi mumkin. Har safar chiziqli o'tish joyi mavjud bo'lsa, biz uni sakrash deb ataymiz . Ikki sakrash o'rtasida qurbaqa faqat oldinga boradi va biz yo'lning bunday to'g'ri segmentlarini segmentlar deb ataymiz . Bundan tashqari, biz segmentlarni ikkita guruhga ajratamiz: maqsad cho'qqisi yoki to'siq bilan tugaydigan segmentlar to'liq segmentlar va to'liq bo'lmagan segmentlar kabi shartlar bilan tugamaydigan segmentlar . To'liq bo'lmagan segmentni maqsad cho'qqisiga yoki to'siqqa yetguncha uzaytiradigan operatsiyani segmentni yakunlash deb ataymiz