Amaliyot ishi №1 Mavzu

Nazorat savollari:

1. 
   Qidirish tarixi haqida ma’lumot bering?
   
2. 
   Optimal qidiruv ni tushuntirib bering?
   
3. 
   Optimallashtirish texnikasi deganda nimani tushunasiz?
   

Amaliyot ishi № 12

Mavzu: O`yinlar. To`rtlikni birlashtirish.

Ishdan maqsad: O`yinlar. To`rtlikni birlashtirishni davlat chegaralari orqali o`rganish.

Nazariy qism:

Bu davlatlar domen maxsus intuitiv algoritmlarni tomonidan baholanadi va ular gol davlatlar bor yoki yo'qligini ko'rish uchun sinov bo'ladi Qidiruv algoritm nuqtai nazaridan, har bir davlat, hech shubhasiz, ichki ammo sekin tomonlarini esa bir qora quti hisoblanadi. Bu salbiy faqat kirish mumkin bo'lgan arbitrary ma'lumotlar strukturasi muayyan tartiblarini-vorisi funktsiyasi vakili test qilinadi, evristik funksiyasi va maqsadi.

Ushbu bobda kimning maqsadi test va cheklov qondirish problemasni davlatlar tekshiradi

Juda oddiy tuzilgan va vakillik standarti a) bo'limga mos keladi. Qidiruv algoritmlarni davlatlar tarkibida foyda olish va katta muammolarni hal qilish uchun umumiy-maqsadiga ko'ra ta'minlash usuli foydalanishi belgilangan bo'lishi mumkin. Ehtimol, eng muhimi, maqsadi test standart vakillik muammosi o'zi tuzilishini ochib beradi. Bu muammo o’rtasida parchalanish va bir muammoning tuzilishini va uni hal qilish uchun yaqin aloqa usullar olib keladi.

Rasman aytganda, bir cheklov muommasini qondirish yoki CSP o'zgaruvchilar bir majmui tomonidan belgilab, XI, X2 ,. . . , Xn, va cheklovlar to'plamidir. (C1,..., C ,… Ci) Har bir o'zgaruvchi Si mumkin qadriyatlar bir bo'sh bo'lmagan domen Di ega. Har bir cheklov o'zgaruvchilar ba'zi kichik majmuini o'z ichiga oladi va qadriyatlar ruxsat etilganko’pligini kombinatsiyasini belgilaydi. Muammoning bir davlat, o'zgaruvchilar, {Xi = VI, Xj = VJ ayrim yoki barcha qadriyatlar bir topshiriq bilan belgilanadi...). har qanday cheklashlar buzilmasa uni izchil yoki yuridik belgilash deb ataladi. A to'liq belgilash, har bir o'zgaruvchi uchun GTS bir yechimi barcha cheklovlarni qondiradi. Ba'zi CSPs ham ob'ektiv vazifasini eng yuqori darajada yechimini bajaradi.

Avstraliya xaritasida bir nechta qo'shni viloyatlar bor shunday tarzda, qizil, yashil, ko'k yoki yo har bir mintaqada bo'yash vazifasi berilgan. (a), va bu rasm 5.l o'z davlatlar va hududlar, har biri bir xil rangda ko'rsatgan. 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'zgaruvchilarni aniqlaydi. Cheklovlar uchun alohida rang bor, 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 =) bo`ladi.

Bu rasm 5.l (b) da ko'rsatilganidek, bir cheklov chizma sifatida CSP tasavvur qilish uchun foydali bo'ladi. a CSP bir qancha muhim foyda bermoqda, CSP davlatlar sentation muvofiq standart namuna-deb, tayinlangan qadriyatlar-vorisi vazifasi va maqsadi test barcha CSPs uchun amaliy umumiy tarzda yozilgan bo'lishi mumkin bo'lgan. Bundan tashqari, biz hech qanday qo'shimcha, domen maxsus tajriba talab qilmaydigan, umumiy buluşsal usul rivojlantirishimiz 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 chiqiladi, vakillik loyihalarni bir qator, birinchi va eng oddiylari hisoblanadi.

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

a cheklov qondirish muammosi sifatida qarash. maqsad yo'q, qo'shni viloyatlarda har$ xil rang bor, shunday qilib, har bir mintaqa uchun rang belgilash hisoblanadi.