ADŠ prednáška 21: Dynamické programovanie 5 - pokrytie dediny zastávkami, obchodný cestujúci

Zhrnutie prednášky

Prednáška nadväzuje na tému rozmiestňovania zastávok v dedine, kde je cieľom minimalizovať súčet (alebo priemer) vzdialeností obyvateľov k zastávke, pričom optimálnym riešením pre jednu zastávku na priamke je medián, prípadne pri váhovaných domčekoch tiež medián. Úloha sa zovšeobecňuje do roviny s manhattanskou metrikou, kde sa dvojrozmerný problém rozpadá na dve nezávislé jednorozmerné úlohy (samostatne pre x a y súradnicu), zatiaľ čo pri optimalizácii súčtu štvorcov vzdialeností je optimálnym bodom aritmetický priemer, ktorý sa jednoducho zovšeobecňuje do viacrozmerných euklidovských priestorov. Ďalej sa rieši otázka efektívneho hľadania mediánu v neusporiadanom poli, pričom sa naznačuje možnosť nájsť ho v lineárnom čase pomocou randomizovaného prístupu inšpirovaného algoritmom quicksort. Vysvetľuje sa princíp výberu náhodného pivota, rozdelenie poľa na menšie a väčšie prvky a pravdepodobnostná analýza, prečo takýto prístup s vysokou pravdepodobnosťou vedie k lineárnej, respektíve n log n časovej zložitosti.

• - Optimálnym miestom pre jednu zastávku na priamke (aj s váhami) je medián.
• - Manhattanovská vzdialenosť v rovine sa dá rozložiť na súčet nezávislých x a y vzdialeností.
• - Pri optimalizácii súčtu štvorcov vzdialeností je optimálnym bodom aritmetický priemer, zovšeobecniteľný do viacerých dimenzií.
• - Ak sú dáta usporiadané v poli, medián sa nájde priamo na strednom indexe.
• - Hľadanie mediánu v neusporiadanom poli je teoreticky zaujímavé, hoci prakticky sa zvyčajne rieši triedením.
• - Randomizovaný výber pivota v quicksorte umožňuje s vysokou pravdepodobnosťou dosiahnuť n log n časovú zložitosť.
• - Pravdepodobnostná analýza ukazuje, že aj pri príležitostnom zlom výbere pivota zostáva očakávaný čas behu blízky optimálnemu.

Zhrnutie pripravené s pomocou AI z prepisu videa.