“Dag’al kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala Rеja

“Dag’al kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala

Rеja:

1. Dag’al kuch usuli haqida

2. Pufakchasimon saralash usuli

3. Kommivoyajer haqida masala

• Dag’al kuch usuli

• Dag’al kuch (yoki "qo'pol kuch" usuli) matematik muammolarni hal qilish usulidir. Barcha mumkin boʻlgan variantlardan foydalanish orqali yechim topish usullari sinfiga ishora qiladi. To'liq qidiruvning murakkabligi muammoning barcha mumkin bo'lgan yechimlari soniga bog'liq. Agar yechim maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yillar yoki hatto asrlar davomida natija bermasligi mumkin.

• To'liq qidiruvning optimalligiga misol sifatida "qo'pol kuch" usuliga asoslangan algoritmga nisbatan tezlashtirib bo'lmaydigan matritsalarning zanjirli mahsulotini hisoblash vaqtini baholash algoritmini keltirish mumkin.
• Ushbu algoritm dinamik dasturlashning klassik muammosini hal qilish uchun ishlatiladi

Pufakchasimon saralash usuli

• Pufakchasimon saralash usuli
• Pufaksimon saralashga o‘tamiz. Bu usulning asosiy prinsipi kichik qiymatlarni surish natijasida ro‘yxatning yuqori qismiga o‘tkazish va shu vaqtning o‘zida katta elementlarni pastga tushurishdan iborat. Pufaksimon saralashning turli variantlari bor. Bu paragrafda variantlardan birini ko‘rib chiqamiz, qolganlarini topshiriqlarda uchratishingiz mumkin.

Pufaksimon saralash algoritmi ro‘yxat bo‘yicha bir nechta o‘tish yo‘llarini amalga oshiradi. Har bir o‘tishda qo‘shni elementlar taqqoslanadi. Agar qo‘shni elementlarning tartibi noto‘g‘ri bo‘lsa, u holda ularning joyi almashadi. Har bir o‘tish ro‘yxat boshidan boshlanadi.

• Pufaksimon saralash algoritmi ro‘yxat bo‘yicha bir nechta o‘tish yo‘llarini amalga oshiradi. Har bir o‘tishda qo‘shni elementlar taqqoslanadi. Agar qo‘shni elementlarning tartibi noto‘g‘ri bo‘lsa, u holda ularning joyi almashadi. Har bir o‘tish ro‘yxat boshidan boshlanadi.
• Dastlab birinchi va ikkinchi element taqqoslanadi, so‘ng 2- va 3-yelement, keyin 3- va 4-element taqqoslanadi va hokazo; noto‘g‘ri tartibda turgan elementlar joy almashadi.
• Birinchi o‘tishda ro‘yxatning eng katta elementi topilsa, u barcha elementlar bilan ro‘yxat oxirigacha o‘rin almashadi. 2-o‘tishda ro‘yxatning kattaligi bo‘yicha 2-yelementi oxiridan ikkinchi o‘ringa o‘tadi.