Islom karimov nomidagi toshkent davlat texnika universiteti

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS

TA’LIM VAZIRLIGI

ISLOM KARIMOV NOMIDAGI TOSHKENT DAVLAT

TEXNIKA UNIVERSITETI

“Elektronika va Avtomatika” fakulteti

“Mexatronika va Robototexnika” kafedrasi

“Axborotlarga ishlo’v berish va Algoritmlash” fanidan

MUSTAQIL

ISH

Bajardi: 143-19 guruh talabasi

Xoliqov I

Qabul qildi: Alimova N

TOSHKENT 2019

Xasis Algoritm

Xasis algoritm - bu har bir bosqichda mahalliy maqbul qarorlar qabul qilishdan iborat bo'lgan yakuniy echimi ham maqbul deb taxmin qilingan algoritmdir. Agar muammoning tuzilishi “matroid” tomonidan o'rnatilsa, ochko'z algoritmdan foydalanish global maqbullikka olib kelishi ma'lum.

Xasis algoritmlarni «qisqa ko'rish», shuningdek, «tuzatib bo'lmaydigan» sifatida tavsiflash mumkin. Ular faqat "maqbul pastki tuzilishga" ega bo'lgan muammolar uchun idealdir. Shunga qaramay, ko'plab oddiy muammolar uchun eng yaxshi mos keladigan algoritmlar ochko'z algoritmlardir. Shunisi e'tiborga loyiqki, ochko'z algoritmni tanlash algoritmi sifatida qidirish yoki tarmoq bilan bog'langan algoritmning ustuvorliklarini belgilash uchun foydalanish mumkin. Ochko'z algoritm uchun bir nechta o'zgarishlar mavjud:

Xasis algoritmlarni «qisqa ko'rish», shuningdek, «tuzatib bo'lmaydigan» sifatida tavsiflash mumkin. Ular faqat "maqbul pastki tuzilishga" ega bo'lgan muammolar uchun idealdir. Shunga qaramay, ko'plab oddiy muammolar uchun eng yaxshi mos keladigan algoritmlar ochko'z algoritmlardir. Shunisi e'tiborga loyiqki, ochko'z algoritmni tanlash algoritmi sifatida qidirish yoki tarmoq bilan bog'langan algoritmning ustuvorliklarini belgilash uchun foydalanish mumkin. Ochko'z algoritm uchun bir nechta o'zgarishlar mavjud:

Sof ochko'z algoritmlar

Ortogonal ochko'z algoritmlar

Tinchlantiruvchi ochko'z algoritmlar

Misolda ko’rish

Misol uchun Xasis algoritmlar o'zgarganda eng kam tangalar miqdorini belgilaydi. Bular inson uchun ochko'z algoritmni taqlid qilish uchun 36 sent qiymatini anglatuvchi {1, 5, 10, 20} qiymatli tangalardan foydalangan holda qilinadigan qadamlardir.

20

10

5

1

Shu tangalar ustida misol keltiraman

Misolda ko’rish

20

10

5

1

Shu tangalarni kattadan kichkinagacha saralab chiqish kerak bo’lsa, 20>x>1

Avval ularni bir-biriga qo’shib chiqish kerak bo’ladi.

10+5+1+20=36 sent bo’ldi, 36 sentli tanga qabul qilamiz

endi 36 sentdan har birini ayrib chiqish kerak

36

Misolda ko’rish

20

10

5

1

Shu qiymatlarga ega bo’lishdi.

36-10=26 -- = 26 sent

36-5=31 -- = 31 sent

36-1=35 -- = 35 sent

36-20=16 -- = 16 sent

36

36

36

36

Misolda ko’rish

26 31 35 16

Endi bu qiymatlarni bir-biri bilan solishtirib chiqiladi va kichkinadan kattaga tartibida saralanadi.

16

16<26<31<35

Endi bu sonlar o’zining eski xoliga qaytariladi.

Misolda ko’rish

20

10

5

1

16 =

26 =

31 =

35 =

Endi ular ketma-ketlikda joylashtiriladi,

Misolda ko’rish

20

10

5

1

Endi ular qiymati bo’yicha saralandi va saralash nihoyasiga yetdi.

E’tiboringiz uchun raxmat