Ач көз алгоритмдер
Ач көз алгоритмдер: жергиликтүү эң жакшы кадам, кесилишпеген интервалдар маселеси, колдонуу чектери.
Ач көз алгоритм ар бир кадамда жергиликтүү эң жакшы тандоону жасайт жана чечимдерин эч качан кайра карабайт. Ач көздүк туура болгондо, мүмкүн болгондордун эң тез жана эң кыска чечими чыгат. Туура эмес болгондо — ишенимдүү түрдө туура эмес жооп берет. Бүт өнөр — биринчисин экинчисинен айырмалоодо.
Эталондук маселе: башталуу жана бүтүү убактысы бар n иш-чара берилген; кесилишпегендердин максимумун тандоо керек. Туура ач көздүк: ар дайым ЭҢ ЭРТЕ БҮТКӨН иш-чараны алуу — ал калгандарга убакыттын максимумун калтырат.
Кесилишпеген интервалдардын максимуму. Киргизиңиз: 4, андан кийин «башы аягы» түгөйлөрү: 1 3, 2 5, 4 7, 6 8
«Эрте бүтүү» эмнеге туура: оптималдуу жооп биринчи болуп башка бир иш-чараны алды дейли. Аны эң эрте бүткөн иш-чарага алмаштыралы — ал кечирээк бүтпөйт, демек, калган расписание толугу менен жарактуу бойдон калат. Жооп начарлаган жок. Далилдөөнүн бул ыкмасы («алмаштыруу жүйөсү») — ач көздөр үчүн стандарт.
Ал эми ач көздүктүн универсалдуу эместигин көрсөткөн каршы мисал: номиналы 1, 3 жана 4 болгон монеталар, 6 чогултуу керек. Ач көз 4+1+1 алат — үч монета. Оптимум: 3+3 — эки. Мындай монета системалары үчүн ач көздүк эмес, динамика керек (кийинки деңгээл!).
Ач көздүн иштеши МҮМКҮН экендигинин белгилери: иреттөө өзүнөн өзү суранып турат; учурдагы кадамдагы тандоо келечекти башка тандоолордон катуураак чектебейт; алмаштыруу жүйөсүн болжолдоп чийип чыгууга болот.
Тапшырма: жөнөкөйдөн баштаңыз: n аркандын узундуктары берилген, эки арканды бириктирүү алардын узундуктарынын суммасынча турат; эң кыска экөөнү ач көздүк менен бириктирүү минималдуу наркты берерин далилдеңиз (же кичине тестте төгүнгө чыгарыңыз). n = 4 үчүн кыдыруу менен өзүңүздү текшериңиз.
Сабакты өттүм деп белгилеп, DSU структурасына өтүңүз.