Amaliyot ishi №1 Mavzu

Nazaorat savollari:

1.”Alfa betta ”qidiruvi haqida nimani tushunasiz?

2.”Alfa betta”qidiruvidan foydalanishni tushuntiring?

3. .”Alfa betta ”qidiruviga misollar keltiring?

Amaliyot ishi №14.

Mavzu: Cheklovlarni qondirish masalasi.

Ishdan maqsad: cheklovlarni qondirish masalasini o’rganish.

Nazariy qism:

Davlatlar domen maxsus intuitiv algoritmlari tomonidan baholanadi va ularning bor yoki yo'qligini ko'rish uchun sinov bo'ladi. Qidiruv algoritm nuqtai nazaridan, har bir davlat, hech shubhasiz, ichki tomonlarini esa bir qora quti hisoblanadi. Bu salbiy faqat kirish mumkin bo'lgan ma'lumotlar strukturasi vakili hisoblanadi. Ushbu bobda har qanday davlatlarning maqsadi test cheklovini qondirish va p ~ roblemalarni hal qilish.

Qidiruv algoritmlari davlatlar tarkibida foyda olish va katta muammolar hal qilishni ta'minlash uchun umumiy-maqsadiga ko'ra muammo-spec $ c buluşsal usuldan foydalanish belgilangan bo'lishi mumkin. Ehtimol, eng muhimi, yani maqsadi test siovlarini o’tkazish bo’lgan. Bu muammo parchalanishi va bir muammoning tuzilishi va uni hal qilinishi kerak.

Rasman aytganda, bir cheklovni qondirish muammosi (yoki CSP) o'zgaruvchilar bir majmui tomonidan belgilab, XI, X2 ,. . . , Xn, va cheklovlar, C1 to'plamidir, (72 ,..., C ,. Har bir o'zgaruvchi Si qadriyatlar biri bo'sh bo'lmagan domen Di ega. Har bir cheklov Ci o'zgaruvchilar ba'zi kichik majmuini o'z ichiga oladi va qadriyatlar ruxsat etilgan kombinasyonları belgilaydi. Muammolardan biri bir davlat, o'zgaruvchilar, {Xi = VI, Xj = VJ ayrim yoki barcha qadriyatlar biri bilan belgilanadi...). A to'liq belgilash, har bir o'zgaruvchining qaysi biri GTS bir yechimli bo’lsa barcha cheklovlarni qondiradigan cheklovalar to'liq belgilash hisoblanadi.

Avstraliya xaritassida biz boshqa viloyatlar tarzda, qizil, yashil, ko'k yoki boshqa har bir mintaqada bo'yash vazifasi berilgan. o'z davlatlar va hududlar, har bir, deb ko'rsatgan bir xil rang. WA, NT, Q, NSW, V, SA, va T. har bir o'zgaruvchining domen to'plami {qizil, yashil, ko'k): a GTS, bu shakllantirish, biz viloyatlariga bo'lish o'zgaruvchilar aniqlash. cheklovlar alohida rang bor, qo'shni mintaqalarga talab qilish; Misol uchun, wà va NT uchun ruxsat etilgan birikmasi juft {(qizil, yashil), (qizil, ko'k), (yashil, qizil), (yashil, ko'k), (ko'k, qizil), (ko'k, yashil)) bo'ladi .

(Cheklov ham cheklov qondirish algoritm kabi iboralarni baholash uchun bir necha yo'l bor bo'lsa, ko'proq ixcham tengsizlik WA # NT sifatida bo'lishi mumkin.) kabi qizil WA =, yashil NT =, Q = {kabi ko'plab mumkin bo'lgan echimlar bor, qizil, NSW = yashil, V = qizil, SA = ko'k, T =).

Bu bir cheklov chizma sifatida CSP tasavvur qilish foydali bo'ladi. CSP davlatlar sentation muvofiq standart namuna-deb, tayinlangan qadriyatlar-vorisi vazifasi va maqsadi test barcha CSPs uchun amal umumiy tarzda yozilgan bo'lishi mumkin bo'lgan parametrlarga. Bundan tashqari, biz hech qanday qo'shimcha, domen maxsus tajriba talab samarali, umumiy buluşsal usul rivojlantirish mumkin. Nihoyat, cheklov grafik tuzilishi murakkabligi bir ko'rsatkichli kamaytirishni berib, ayrim hollarda, hal jarayonini soddalashtirish uchun foydalanish mumkin. CSP vakillik kitob bo'ylab ishlab qilinadi vakillik loyihalarni bir qator, birinchi va eng oddiy hisoblanadi.

(A) asosiy davlatlar va Avstraliya hududlar. Ushbu xaritada rang bo'lishi mumkin

a cheklovni qondirish muammosi sifatida qarash mumkin. Qo'shni viloyatlar bir xil rangda. Shunday qilib, har bir mintaqa uchun rang belgilash kerak.