Энгүүнбаяр Ганзориг

• 2025-04-25
• algorithm, competitive programming, greedy, programming, Шуналтай

Энэ нийтлэлийг уншиж буй танд энэхүү өдрийн мэндийг хүргэе . Та өөрийгөө хэр шуналтай хүн гэж боддог вэ ? Хэрвээ та өөрийгөө шуналтай гэж бодож байвал энэхүү алгоритм танд яг таг тохирно гэсэн үг . Харин шуналгүй гэж бодож байвал тэр боломжгүй юм . Хүн төрөлхтний хамгийн эртний сэтгэл хөдлөлийн нэг бол яахын аргагүй шунал юм . Тэгэхээр далд санаагаа ил гаргаад гол сэдэв рүү гээ орцгооё . Өнөөдрийн нийтлэлээр Шуналтай алгоритм (Шунахай ч гэж нэрлэгддэг) буюу Greedy Algorithm-ийн тухай ярилцах гэж байна . Шуналтай алгоритм гэж юу вэ ? Ямар үед шуналтай алгоритм ашиглах хэрэгтэй вэ ? Ямар үед шуналтай алгоритм бүтэлгүйтдэг вэ ? хэмээх маш чухал зүйлсийн талаар би тайлбарлахад бэлэн болсон байна . Харин та уншихад бэлэн үү ?

Шуналтай алгоритм гэж юу вэ ?

Шуналтай алгоритм гэдэг нь тухайн үед хамгийн сайн харагдаж байгаа сонголтыг хийж, дараагийн алхмуудыг бус, зөвхөн одоогийн нөхцөлд хамгийн их ашигтай шийдлийг олох арга юм. Энэ нь ирээдүйн талаар бодолгүйгээр одоо л хамгийн сайн сонголтыг хийнэ гэсэн үг . Энгийн сонсогдож байна уу ? . Би хэлсэн шүү дээ . Шуналтай хүнд яг тохирдог алгоритм гэж хэлээд байхад .

Жишээ нь :

Таньд 12 төгрөг байлаа гэж бодье . Таньд энэхүү 12 төгрөгийг зоос болгох шаардлага гарлаа . Та салан баавгай шиг учир 12 төгрөгийг аль болох хамгийн бага тооны зоосоор солихийг хүсэж байлаа. Таний амьдарч байгаа улсад 1 зоос , 5 зоос , 10 зоосууд л байдаг ажээ . Та хэрхэн хамгийн бага ширхэг зоосоор өөрийн мөнгөө солих вэ ?

Хариулт :

Та эхлээд 12 төгрөгөө хамгийн том зоос болох 10 зоосоор солих хэрэгтэй . Таньд 2 төгрөг 1 ширхэг 10 төгрөгний зоос байгаа . Одоо таньд 2 төгрөг байгаа ба 1 төгрөгний 2 ширхэг зоосоор солиод л болно шүү дээ . Эцэст нь та 12 төгрөгөө боломжит хамгийн бага хувилбар буюу 3 зоосоор сольж чадлаа .

Аргачлал :

Энэхүү хариулт нь хэрхэн шуналтай алгоритм байсан ба гэхээр та солих зоосоо сонгохдоо нөхцөл болгонд авж болох хамгийн их зоосыг авж байгаа билээ . Шунахай алгоритмийн хувьд бид нарт үлдэх зоосны хэмжээ огт хамаагүй юм .

Ямар үед шуналтай алгоритм ашиглах хэрэгтэй вэ ?

Хэрвээ таны бодох гэж бодлогод ШУНАЛТАЙ ШИНЖ ЧАНАР буюу Greedy Property байвал тухайн бодлогийг Greedy Algorithm-оор бодогдоно хэмээн үзэж болох нь ээ .

1. Шуналтай сонголтийн шинж
   • Энэхүү шинж нь тухайн үед буюу локал хамгийн сайн шийдэл нь глобал хамгийн сайн шийдэлд хүргэх шинж.
2. Сайн дэд-бүтцэд хуваагддаг
   • Бодлогыг дэд асуудлуудад хуваах боломжтой бөгөөд эдгээр дэд асуудлуудын хамгийн сайн шийдлүүдийг нэгтгэхэд нийт асуудлын хамгийн сайн шийдэл үүсдэг байх шинж.

Хэрвээ бидний бодох бодлогод дээрх хоёр шинж аль аль нь байгаа бол Greedy алгоритм бат үр дүнтэй байх болно .

Ямар үед шуналтай алгоритм бүтэлгүйтдэг вэ ?

Энэ бол үнэхээр чухал хэсэг юм . Яагаад энэхүү шуналтай алгоритм бүтэлгүйтдэг вэ ? .

1. Зөв локал шийдлүүд != Зөв глобал буюу хариу
   • Greedy нь тухайн агшинд хамгийн ашигтайг сонгодог. Гэхдээ энэ сонголт хожмын нийт дүнгийн хувьд муу байж болно. Яг л манай улс төрчид шиг тухайн үед хамгийн ашигтайг нь сонгодог боловч энэ нь ирээдүйд муугаар нөлөөлөх талаар тэд огт боддоггүйтэй төстэй юм. Жаахан улс төржчихлөө .
2. Шуналтай шинж чанар байхгүй үед
   • Шуналтай алгоритм ашиглах шаардлага буюу шуналтай шинж чанарыг хангаж чадахгүй байгаа тохиолдолд бид нар шуналтай алгоритмийг ашиглах нь тун буруу билээ .
3. Хэрэв дэд асуудлууд нь давхцаж байвал
   • АНХААРААРАЙ !!! Энэ сэдэв дээр маш чухал зүйлийн талаар дурьдах гэж байна . (Дараагийн нийтлэлийн сэдэв ч байж болох юм ) . Greedy өмнөх шийдвэрүүдийг санадаггүй. Хэрэв ирээдүйн шийдвэрүүд өмнөхөөс хамаардаг буюу давхацдаг бол greedy алгоритм ажиллахгүй .(Энэ үед нь бид нар DP ашиглана . Гэхдээ энэ талаар одоо хэлэхгүй дараагийн нийтлэл дээр гоё тайлбарлаж өгье)

Дүгнэлт :

Шунахай алгоритм нь хурдан, энгийн, зарим асуудалд тун ухаалаг сонголт байж чадна. Гэвч тухайн мөчид зөв сонголт ирээдүйд зөв шийдэл болно гэсэн баталгаа хэзээ ч байдаггүй. Тиймээс бодлогоо зөв таньж, greedy шинж чанартай эсэхийг сайтар нягтласны дараа энэ аргыг ашиглах хэрэгтэй. Хэрвээ та бүхэн хүсвэл энэхүү Greedy Algorithm-оор хэд хэдэн бодлого бодон бодолтийг нь ярилцан нийтлэл бичиж болох юм . Доор санал хүсэлтээ бичээрэй . Дараа уулзая баяртай . Geronimooooo