|
10 amaliy ish. Mantiqiy dasturlash
|
| Sana | 12.01.2024 | | Hajmi | 22.94 Kb. | | #135581 |
Bog'liq 10- amaliy mashgulot Aftomabillar devigatelini qisimlarga ajratish va yig’ish chilangari, Boynazarov 1m RQY, Ўзбекистон Республикаси илк ва мактабгача Таълим ёшдаги болалар -fayllar.org, 1-amaliy mashg’ulot Mavzu Axborotni o‘lchash va tasvirlash. Mav-fayllar.org, 4-maruza Turli jinsli sistemalar klassifikatsiyasi. Filtrlash. , Milliy xavfsizlikni ta\'minlash borasida amalga oshirilayotgan is-fayllar.org, 2-mavzu. Falsafiy tafakkur taraqqiyoti bosqichlari Sharq falsaf, 000000000000, 6 mavzu Kepler qonunlari, 5mavzu Funksiyaning uzluksizligi Funksiyaning uzulish nuqtalari, 5-amaliy mashgulot, nigga, 27 maktab 2021 obektivka hodimlar lotincha -rahbaryat, fizika-fanini-o-qitish-uchun-zamonaviy-texnollogiyalar
10 - amaliy ish. Mantiqiy dasturlash
Mantiqiy dasturlash - bu avtomatik teoremani isbotlashga asoslangan dasturlash paradigmasi, shuningdek berilgan faktlar va xulosalar qoidalari asosida axborotni mantiqiy xulosa qilish tamoyillarini o'rganadigan diskret matematikaning bo'limi. Mantiqiy dasturlash qarorlarning matematik tamoyillaridan foydalangan holda matematik mantiq nazariyasi va apparati asosida amalga oshiriladi.
Eng mashhur mantiqiy dasturlash tili - Prolog.
Mantiqiy dasturlashning birinchi tili Planner tili bo'lib , unda ma'lumotlardan natijani avtomatik ravishda chiqarish imkoniyati va variantlarni sanab o'tish qoidalari berilgan (ularning kombinatsiyasi reja deb yuritilgan). Planner yordamida hisoblash talablarini kamaytirish (backtracking - backtracking yordamida) va stekni faol ishlatmasdan faktlarni namoyish etish qobiliyatini ta'minlash uchun foydalanilgan. Keyin takrorlash rejasini talab qilmaydigan va shu ma'noda Planner tilini soddalashtiradigan Prolog tili ishlab chiqildi .
Planner tili QA-4, Popler, Conniver va QLISP mantiqiy dasturlash tillarini ham yaratdi. Mercury, Visual Prolog, Oz va Fril dasturlash tillari Prolog tilidan kelib chiqqan. Planner tili asosida backtracking usuliga asoslanmagan bir qancha muqobil mantiqiy dasturlash tillari ishlab chiqilgan, masalan, Eter .
Mantiqiy dasturlash nima va nima uchun biz bunga muhtojmiz
Bolalikda Prologda yozmaganning yuragi yo'q, bugun yozganning miyasi yo'q.
Agar siz doimo og'riqli shubhalar bilan qiynashgan bo'lsangiz - bu mantiqiy dasturlash (LP) nima jahannam va umuman nega bunga ehtiyoj bor ?
Siz dasturlash tillarini guruhlarga har xil usulda ajratishingiz mumkin (ular ko'pincha dasturlash paradigmalari deb ataladi), masalan, quyidagicha:
tizimli: dastur bloklarga bo'linadi - subroutines (bir-biridan ajratilgan) va asosiy boshqaruv elementlari buyruqlar ketma-ketligi, tarmoqlanish va tsikldir.
ob'ektga yo'naltirilgan : vazifa bir-biriga xabar yuboradigan ob'ektlar sifatida modellashtirilgan. Ob'ektlarning xususiyatlari va usullari mavjud. Abstraktsiya. Kapsülleme. Polimorfizm. Xo'sh, umuman, hamma biladi.
funktsional: asosiy element funktsiya bo'lib, vazifaning o'zi funktsiya sifatida modellashtirilgan yoki aniqrog'i, ko'pincha ularning tarkibi ko'rinishida, agar f (.) va g (.) funktsiyalar bo'lsa, f (g (.)) ularniki tarkibi.
mantiqiy: bu erda, odatda, g'ayritabiiylik boshlanadi - agar birinchi uchtasi haqida yuzlab maqolalar, kitoblar, sharhlar, taqdimotlar va darsliklar yozilgan bo'lsa, unda biz eng yaxshi holatda Prolog va Pink Floyd va Procol Harum davridagi voqealarni ko'rmoqdamiz (hech bo'lmaganda, hech bo'lmaganda). ular musiqa bilan omadli edilar) va bu erda hikoya tugaydi.
Men bugun bu xatoni to'g'irlayman.
Mantiqiy dasturlash ! = Prolog.
Umuman olganda, ehtimol siz ikkinchisiga muhtoj emassiz. Ammo birinchisi yaxshi bo'lishi mumkin.
Ushbu maqolada (ehtimol) birinchi marta rus tilida zamonaviy mantiqiy dasturlashning asosiy jihatlari nima uchun kerakligini tushuntirish bilan birga to'plangan . Mantiqiy dasturlash (LP) bevosita bog'liq yozuvchining bo'ladi mening fanlari nomzodi (bu haqda alohida batafsil post mavjud bo'ladi). Ish jarayonida men rus tilida deyarli hech qanday ma'lumot yo'qligini payqadim va bu bo'shliqni to'ldirishga qaror qildim (ruscha Vikipediyada ASP haqida yozishga arziydigan maqola ham yo'q).
Maqolaning alohida qismlari bir-biri bilan to'g'ridan-to'g'ri bog'liq bo'lmasligi mumkin, masalan , Sketching va Problog - qaysidir ma'noda bu mantiqiy dasturlash sohasidagi eng qiziqarli mavzular va ishlanmalarning shaxsiy sharhi. Bu beradi , albatta, LP bilan bog'liq barcha mavzularni qamrab mumkin emas - lekin, biz bu mavzu sho'ng'idi bir qiziqish o'quvchi uchun birinchi qadam, deb faraz yoki LP bunday hayvon, deb tasavvur qilish mumkin.
Prologue nima va nima uchun ehtimol sizga kerak emas
Prolog ( Programming in Logic , dastlab: programlama en logique) Marselda 70-yillarning boshlarida Alen Kolmero tomonidan ishlab chiqilgan . Til Horn ning mantiqiy ifodalar (bir paqir mashina amalga qanday aniq, deb) shakldagi jadvallar protsessual talqin asoslangan:
a : - b , c , d, ..., z.
Qaysi birini o'qish mumkin: "agar b, c, d, ..., z shartlari bajarilsa, unda" a "ham to'g'ri bo'lishi kerak.
Va sodda qilib aytganda (bu erda biz barcha texnik ma'lumotlarni qoldirib ketamiz), uni mantiqiy ketma-ketlik sifatida qayta yozish mumkin:
$ b \ wedge c \ wedge d \ wedge \ dots \ wedge z \ rightarrow a . $
Darhaqiqat, ser Bob Kovalski - shunday fikrni o'ylab topdi: agar unga qo'yilgan barcha joylar haqiqat ekanligini isbotlasak, "a" degan gap to'g'ri. (Aytgancha, ajoyib va quvnoq yigit - hali ham sog'lom va hazil va ertaklarni tarqatib yubormoqda, bir yil oldin Londonda Qirollik jamiyatida bo'lib o'tgan anjumanda u Prolog va mantiqiy dasturlash tarixi bo'yicha juda zo'r va ba'zan kulgili ma'ruza o'qidi.)
Kovalski , tuz nima ? Agar "a : - b, c, d" ifodasini olsak , u holda quyidagicha o'qilishi mumkin:
agar imkonim bo'lsa " a " to'g'ri: "b" ni isbotlang, "c" ni isbotlang va "d" ni isbotlang.
Keyin har bir dastur tasdiqlarni keltirib chiqarish uchun teoremalar to'plami bo'lib, har bir ifoda "isbotlangan" (diqqatli o'quvchi bu erda albatta Kori-Xovard izomorfizmini payqaydi).
Agar bu erda inkorni qo'shsangiz, vazifa biroz qiziqarli bo'ladi. Prologda bu inkor etishmovchilik deb nomlanadi va klassik inkordan mantiq bilan farq qiladi. Nazariy jihatdan bu shunday ko'rinadi: agar men "a" so'zini isbotlay olmasam, demak bu uning noto'g'ri ekanligini anglatadi. Mantiqan, bu taxmin yopiq dunyo taxminlari deb nomlanadi va ba'zida u juda mazmunli bo'ladi.
Muvaffaqiyatsizlik va dunyoning yopiq farazlari kabi inkor
Samara shahrining 11-avtobus yo'nalishi jadvalini tasavvur qiling, fragment:
15:15
15:45
16:15
16:45
17:15
Savol: soat 16:00 da avtobus bormi? U erda yo'q, chunki biz uning jadvalga muvofiqligini isbotlay olmaymiz - ya'ni. jadvalda Samara shahridagi 11-marshrut yurish dunyosi haqida to'liq tasavvur mavjud. Demak, yopiq dunyo gumoni degan nom - ushbu dastur tomonidan barcha shartli dunyo tasvirlangan degan taxmin - tashqaridagi hamma narsa yolg'ondir. Sifatida qoida, u ham ma'lumotlar bazalari ishlatiladi - yo'li bilan, men bu erda ular haqida yozgan.
Prouring Turingning to'liq dasturlash tili sifatida
Bir nechta boshqa qiziqarli operatorlar bilan birgalikda (masalan, kesilgan), Prolog chiqadi - Turing - bu to'liq til - qisqacha - agar P prologidagi dastur f (x) funktsiyasini baholasa, u holda boshqa har qanday Turing to'liq tilida M dasturi mavjud va u ham f (x) ni hisoblaydi. ). Shunday qilib, agar siz Prolog-da dasturni hal qila olsangiz, boshqa har qanday tilda (Python, Java, C, Haskell va boshqalar) echim yozishingiz mumkin. Bu erda chakralar ochilmaydi.
Umuman olganda, Prolog-dagi muammoning echimi Bob Kovalskiyga ko'ra sxemaga ajraladi
Algoritm = Mantiq + Boshqarish
Prologda yaxshi tuzilgan va echilgan muammoning yaxshi namunasi - ma'lum bir shart bajarilgan yoki bajarilmagan qoidalar to'plami. Biroq, siz o'zingizning echimingizni topish algoritmini belgilashingiz kerak - qabul qilinadigan qiymatlarning maydoni qanday, ular qanday tartibda bosib o'tiladi va hokazo. Yilda Aslida, siz xulosa qoidalar shaklida muammo model va, xulosa qoidalarini foydalanib, bir yechim (qoidalar tartibini, bichish, boshiga qoidaga tanadan ro'yxatda qadriyatlar o'tish, va boshqalar) va maqbul yechim oraliq topish tartibini belgilash.
Biz tezkor predikatning ikkita holat uchun - bo'sh ro'yxat va bo'sh bo'lmagan ro'yxat uchun aniqlanganligini ko'rishimiz mumkin. Bizni bo'sh bo'lmagan holat qiziqtiradi: u [X | Xs] ro'yxatini o'z ichiga oladi, bu erda X - ro'yxatning boshi, ya'ni birinchi element (mashina bu dastur ozgina qavs ichida deb o'ylaydiganlar uchun) va Xs - bu dum (dum, aka cdr) ikkita Bigs va Littles ro'yxatiga bo'lingan - kattaroq va kichikroq bo'lganlar, X. Keyin ikkala ro'yxat ham rekursiv ravishda saralanadi va yakuniy chiqish ro'yxatiga qo'shiladi . Ko'rib turganimizdek , umuman olganda, biz butun algoritmning ishlashini xulosa qoidalari bo'yicha o'rnatamiz .
Prolog nima uchun yaxshi? U rasmiy semantikani yaxshi ishlaydi - ya'ni. siz rasmiy ravishda xususiyatlarni ko'rsatishingiz mumkin (masalan, yuqoridagi dastur haqiqatan ham raqamlarni saralashini isbotlang), ehtimollik holatiga yaxshi tarqaladi (ProbLog bo'limiga qarang) va umuman yaxshi kengayadi, mantiqiy muammolarni modellashtirish uchun qulay til, matematik ish uchun juda mos, meta-lingvistik uchun operatsiyalar va boshqalar.
Muxtasar qilib aytganda, agar siz dasturning xulq-atvorining xususiyatlarini rasmiy ravishda ko'rsatishingiz kerak bo'lgan ilmiy ish yozmasangiz, ehtimol sizga Prolog kerak emas. Lekin , balki mantiq dasturlash bo'ladi siz uchun foydali ?
Sizga nima uchun kerak yoki Javoblar Dasturlash (ASP) ga tez kirish
ASP nima ekanligini qisqacha tushuntirish:
agar SAT assambleyer bo'lsa, u holda zamonaviy ASP C ++ bo'ladi.
Bu erda deklarativ dasturlash va Jon Makkartining (LISPni ixtiro qilgan, Algolga ta'sir ko'rsatgan va umuman "Sun'iy intellekt" atamasini taklif qilgan) bag'rikenglik printsipi kabi narsadan boshlash kerak.
Deklarativ yondashuv nima? Muxtasar qilib aytganda, biz uni qanday hal qilish kerakligini emas, balki muammoni va uning xususiyatlarini tasvirlaymiz. Bunday holda, topshiriq ko'pincha quyidagi shaklda taqdim etiladi:
Muammo = Model + Izlash
Ushbu yondashuv bilan qaerda muntazam uchrashamiz? Masalan, ma'lumotlar bazalarida SQL deklarativ so'rovlar tili bo'lib, ma'lumotlar bazasi bu so'rovga javob izlaydi. MBBning samarali ishlashi uchun minglab samarali algoritmlar ixtiro qilingan, ma'lumotlar optimallashtirilgan shaklda saqlanadi, indekslar hamma joyda, so'rovlarni optimallashtirish usullari va boshqalar.
Lekin eng muhimi, foydalanuvchi aysbergning uchini ko'radi: SQL. Va ma'lumotlar bazasini bir oz tushungan holda foydalanuvchi samarali so'rovlar yozishi mumkin. Keling, avvalo o'zgarishga chidamlilik printsipini oddiy misol bilan tushuntiraylik. Aytaylik, biz kompaniyadagi bo'limlar bo'yicha o'rtacha ish haqini hisoblab chiqadigan Q oddiy so'rovini yozdik. Biroz vaqt o'tgach, bizdan so'rovni biroz o'zgartirishni so'rashdi - masalan, hisob-kitoblarda boshqaruvni e'tiborsiz qoldirish - biz texnik mutaxassislarning o'rtacha ish haqi bilan qiziqdik. Bu holda Q so'roviga "roli ! = 'Menejer'" qo'shishingiz kerak bo'ladi .
Bu shuni anglatadiki, Q_updated yangi so'rovimiz asosiy so'rov + qo'shimcha shart sifatida taqdim etilgan. Umuman olganda, biz buni ko'ramiz
Muammoning o'zgarishi = Asosiy model + Qo'shimcha shart
Bu shuni anglatadiki, biz ba'zi bir qo'shimcha X shartlari uchun muammoning holatini biroz o'zgartirganda, qo'shimcha C_X shartini qo'shish orqali modelni (ba'zi rasmiy tillarda asl masalani modellashtiradigan - masalan, SQL) o'zgartirishimiz kerak.
ASP va Mantiqiy dasturlashning bunga nima aloqasi bor?
Prolog va ASP o'rtasidagi tub farq nimada? Aslida, ASP deklarativ cheklov tili, ya'ni biz hisoblash qoidalarini tanlash qoidalari deb nomlangan maxsus cheklovlar shaklida aniqlaymiz, masalan:
1 {rang (X, C): ranglar (C)} 1: - tugun (X).
Bunday qoidalar sanash maydonini belgilaydi - so'zma-so'z quyidagicha o'qing: predikatdagi har bir X uchun (bu erda o'qing - to'plamda) tugun, ya'ni har bir vertex uchun bitta X bo'lishi kerak - "{" ning chap tomonida va bitta bittasi - o'ngda bitta "}" atom rangi (X, C), masalan , C ranglar to'plamidan kelib chiqadi (unary predikat ranglari / 1).
ASP-ning asosiy xususiyatlaridan biri shundaki, cheklovlar echim NIMA ekanligini belgilaydi, masalan - quyidagi qoidani ko'rib chiqing:
: - chekka (X, Y), rang ( X, Cx ), rang ( Y, Cy ), Cx = Cy.
Cheklovlar (ingliz tilidagi ilmiy adabiyotlarda bu atama: yaxlitlik cheklovlari qo'llaniladi) - aslida, maqolaning boshidanoq qoidalar - faqat ular "bo'sh bosh" ~ bo'sh boshga ega: va aslida, bu shakl qoidalarining qisqartmasi:
noto'g'ri : - a_1, a_2, ... a_n
o'sha. a_1,… a_n bajarilgan bo'lsa, u holda "false" chiqadi va bu model emas.
(aniqrog'i: yolg'on b uchun sintaktik tuzilishi hisoblanadi : -. a_1, ... Butunlik oblasti, B emas - bir ziddiyat bo'lgan - b b noto'g'ri ekanligini taxmin ostida xulosa qilinadi.).
Bu nazariy ekskursiyani yakunlaydi va qoidaga diqqat bilan qaraydi - unda quyidagilar ko'rsatilgan: agar X va Y o'rtasida kamon bo'lsa, X rangi Cx va Y rangi C y va Cx == Cy bo'lsa, unda bu echim emas.
Aytgancha, ASP bilan tanish bo'lgan odamlar, ehtimol, ushbu qoidani shunday yozishlari mumkin :
: - chekka (X, Y), rang (X, C), rang (Y, C).
Xuddi shu qoida ichidagi bir xil nomdagi o'zgaruvchilar teng deb hisoblanadi (va ehtimol, bu erga ulanish bosqichida yordam beradi - ammo bu boshqa hikoya).
Keling, butun vazifani bir butun sifatida tavsiflashga o'tamiz (va yana ikkitasi).
Biz bir nechta mashhur kombinatoriya muammolarini tahlil qilamiz: NP to'liq va unchalik emas
Bu erda tasvirlangan kod eng yaxshi Clasp-da ishlaydi (u erda badiiy ishlov berish va sharhlarni yozishdan oldin sinovdan o'tgan va sinovdan o'tgan).
Biz quyidagi vazifalar haqida gaplashamiz:
grafik rang berish: grafigi berilgan holda, uni uchta rangda bo'yash mumkinmi yoki yo'qligini aniqlash kerak, shunda biron bir tepalik bir xil rangda bo'lmaydi
qora va oq malikalar: taxtada n by n, har xil rangdagi ikkita malikalar bir-birini mag'lub qilmasligi uchun k qora va oq malikalarni joylashtiring.
Va biz ularning har birini ASP yordamida hal qilamiz va shu bilan birga asosiy modellashtirish usullarini tahlil qilamiz.
Biz allaqachon ASP kodining asosiy konstruksiyalarini tahlil qildik - qolgan elementlardan o'tamiz: tugun / 1 (tugun (a). Tugun (b) ...) - grafika tepalari to'plamini e'lon qiladi, tartib muhim emas, chekka / 2 - yoylarni e'lon qiladi. ASP (va mantiqiy dasturlash) dagi bunday atomlar deyiladi - faktlar, aslida bu "a : - true." Ning qisqartmasi , va shunchaki har doim to'g'ri bo'lgan, ya'ni atomlar dastur ma'lumotlarini aniqlaydigan bayonotdan olinadi.
% Har bir narsa kabi bir fikr, deb "%" belgi keyin liniyada ketadi
% Grafikning to'rtta tepasini e'lon qilamiz
tugun (a). tugun (b). tugun (c). tugun (d).
% Grafik qirralarini e'lon qiling
chekka ( a, b ). chekka ( a, d ).
chekka ( b, c ). chekka ( b, d ).
chekka ( c, d ).
% Agar biz X va Y o'rtasida tepalik bo'lsa, demak Y va X o'rtasida ham vertex bor - biz grafani yo'naltirilmagan qilamiz
chekka ( Y, X): - chekka (X, Y).
% E'lon amal ranglar
ranglar ( qizil). ranglar ( yashil). ranglar ( ko'k).
% Biz har bir tepalik uchun bitta va bitta rangga ega bo'lishi kerakligini aytamiz va yuqoridagi ranglardan (.) Bashorat qiling
1 {rang (X, C): ranglar (C)} 1: - tugun (X).
% Agar X, Y (istalgan qirralarning) tepalari to'satdan bir xil rangga ega bo'lsa, aka Cx = Cy bo'lsa, u holda bu yechim emas
: - chekka (X, Y), rang (X, C), rang (Y, C).
% Faqat vertex ranglarini chiqishda ko'rsating
#show color / 2.
Qora va oq malikalar
Qirolichalarning joylashuvi haqida (men ushbu o'zgarishni o'z ichiga olaman) oldinroq bu erda batafsilroq yozgan edim.
(bu erda eng ko'p qirolichalar soni bor va siz xoch o'rnida oq rangni qo'yishingiz mumkin, va qora nuqta o'rniga - lekin ikkalasi ham birdan emas; maqoladan olingan)
Bu erda keltirilgan kod malika tartibining oddiy polinom versiyasini ham, NP-to'liq versiyasini ham hal qiladi (malika haqidagi habra maqolasiga qarang; bu erda klassik versiya uchun murakkablik natijasi ham ushbu o'zgarishga tegishli).
Qora va oq malikalar uchun barcha ASP kodlari
Keling, kodni batafsil ko'rib chiqaylik, quyidagi qoidalar taxta parametrlarini o'rnatdi - aslida biz ko'p sonli malikalar ranglari bilan muammoni hal qilishimiz mumkin edi - bu erda ranglar rang / 1 predikati qiymatlari sifatida yozilgan.
% har bir "k" rangidagi malikalar sonini va "m" taxtaning hajmini e'lon qiladi.
# doimiy k = 2.
# Const m = 4.
% taxtaning ranglari va o'lchamlarini e'lon qiladi
rang ( b). rang ( w).
kol ( 1..m). qator ( 1..m).
Keyinchalik, qidiruv maydonini e'lon qilishimiz kerak:
% har bir rang uchun aniq k malikalar bo'lishi kerak va o'lchamlari taxtada
k {malika ( C, Row, Col ): col (Col), satr (Row)} k: - rang (C).
Darhaqiqat, ushbu qoida quyidagicha o'qiladi: har bir C rang uchun C rangning k va to'liq k malikalari bo'lishi kerak, va satr va Col qiymati predmetatlar to'plamidan bo'lishi kerak col / 1 va satr / 1. Oddiy qilib aytganda, har bir rang uchun biz to'g'ri (taxtada) malika sonini k ga tenglashtiramiz .
Keyinchalik, biz echim bo'lmagan narsani tasvirlaymiz : agar biz bir xil satrda, ustunda yoki diagonalda turli xil ranglarga ega bo'lsak:
% agar bitta chiziqda oq va qora malikalar bo'lsa
: - malika ( w, Rw, Cw ), malika ( b, Rb, Cb ), Rw = Rb .
Agar bitta ustunda oq va qora malikalar bo'lsa%
: - malika ( w, Rw, Cw ), malika ( b, Rb, Cb ), Cw = Cb .
Agar bir xil diagonalda oq va qora malikalar bo'lsa%
: - malika (w, Rw, Cw), malika (b, Rb, Cb), | Rw - Rb | = | Cw - Cb |.
Yilda Aslida, bu ASP - qidiruv bo'sh joy (tahminim) javob (tekshirish) ning + tekshirish: biz kodi shuningdek, ikki qismga irib-chirib bo'lgan ekanini, tenglama Muammo = Data + Model bilan yaxshi gumon-va-check misol deb ataladi, va butun kodi og'riqqa - SAT-dan farqli o'laroq, agar men ma'lumotni o'zgartirsam - yangi qirolichalarni qo'shsam, u holda cheklovlar (model qoidalari) o'zgarmaydi. Umuman olganda, biz ushbu qoidalarni hatto ranglarni parametr sifatida qabul qilishi uchun qayta yozishimiz mumkin edi.
Qisqacha kombinatorial optimallashtirish
Pastki chiziq oddiy: Xamilton tsiklini topish kabi kombinatoriya muammosi mavjud (NP bilan yakunlangan muammo), lekin yuqorida qo'shimcha shart mavjud : biron narsani kamaytirish kerak - masalan, yo'lning og'irligi (grafani bo'yash uchun ranglar soni, malikalar yoki malikalar ranglarini maksimal darajada oshirish va boshqalar). ) Qoida tariqasida, bu muammoning murakkabligiga o'tish imkonini beradi va qidirishni ancha qiyinlashtiradi. ASP kombinatorial optimallashtirish muammolarini hal qilishning standart mexanizmiga ega.
Yo'lning og'irligini optimallashtirish bilan Xamilton tsiklini topish masalasini tahlil qilaylik (javoblar to'plamini amalda hal qilish kitobidan olingan kod. Martin Gebser va boshq. Sharhlar meniki)
% === GUESS ===
% qidiruv maydonini o'rnatdi - har bir tepalik uchun pastadirda kamon bo'lishi kerak
1 {tsikl (X, Y): chekka (X, Y)} 1: - tugun (X).
% Simmetriya ning yoylari
1 {tsikl (X, Y): chekka (X, Y)} 1: - tugun (Y).
% 1 tepadan boshlanadi
% === Yordamchi ma'lumotnoma ===
yetdi (Y) : - tsikl (1, Y).
% o'tish davri vertexning yopilishi
erishildi ( Y): - tsikl (X, Y), (X) ga yetdi.
% === CHECK ===
Agar biron bir tepalikka erishib bo'lmaydigan bo'lsa,% - bu echim emas
: - tugun (Y), (Y) ga etib bormagan.
% === MINIMIZE ===
% va shuningdek - har bir yoyning narxi bor va siz yo'lning umumiy og'irligini minimallashtirishingiz kerak
# minimallashtirish [tsikl (X, Y) = C: xarajat (X, Y, C)].
Yilda Aslida, biz ASP Kombinatöryel optimallashtirish vazifasi hamda bir deklarativ tenglama irib-chirib, deb qarang:
Muammo modeli = Tahmin + Tekshirish + Minimallashtirish
Muammo, shuningdek, yangi faktlarni (yordamchi xulosalar) keltirib chiqarishning bir qismini o'z ichiga oladi, keyinchalik ular cheklovlarda qo'llaniladi. Bu ASP dasturlari uchun juda yaxshi standart.
|
| |
