nechodím na prednáškyADŠ prednáška 16: Spojitá a diskrétna verzia problému batoha. Technika meet in the middle.
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška sa vracia k problému batoha a skúma, či naň možno aplikovať pažravé (greedy) stratégie. Postupne sa testujú tri prístupy: zoraďovanie vecí podľa hmotnosti od najmenšej, podľa ceny od najvyššej a podľa pomeru cena/hmotnosť (mernej ceny). Pre každú z týchto stratégií sa konštruuje konkrétny protipríklad, na ktorom sa ukazuje, že výsledné riešenie môže byť ľubovoľne ďaleko od optimálneho, takže nedávajú žiadnu aproximačnú záruku. Zdôvodňuje sa to aj tým, že diskrétny (0/1) problém batoha je NP-ťažký, takže neexistencia jednoduchého efektívneho pažravého algoritmu nie je prekvapivá. Na záver sa naznačuje rozdiel oproti spojitej verzii úlohy (deliteľné predmety, napríklad syr), kde by pažravý prístup mohol fungovať inak.
- - Problém batoha (0/1 knapsack) s Robinom Hoodom ako metaforou.
- - Stratégia radenia podľa hmotnosti od najmenšej zlyháva – protipríklad s ťažkou drahou vecou a kopou lacných malých vecí.
- - Stratégia radenia podľa ceny od najvyššej tiež zlyháva – protipríklad ukazuje ľubovoľne veľkú stratu oproti optimu.
- - Stratégia podľa pomeru cena/hmotnosť (merná cena) tiež nefunguje, dokázané konkrétnym trojprvkovým protipríkladom.
- - Žiadna z troch pažravých stratégií nedáva rozumnú aproximačnú záruku voči optimálnemu riešeniu.
- - Diskrétny problém batoha je NP-ťažký, čo vysvetľuje zlyhanie jednoduchých greedy prístupov.
- - Naznačený rozdiel medzi diskrétnou a spojitou (deliteľnou) verziou úlohy, kde by greedy mohol fungovať lepšie.
Zhrnutie pripravené s pomocou AI z prepisu videa.
