Lokálne prehľadávanie a susedstvá: definície, typy problémov a algoritmy
Enviado por Anónimo y clasificado en Informática
Escrito el en 
eslovaco con un tamaño de 16,91 KB
Okruh 4: Lokálne prehľadávanie a susedstvá
1. Čo je susedstvo v lokálnom prehľadávaní? Ako je definované? Uveďte príklady a obmedzenia pre každý typ definície.
Susedstvo N(s) je podmnožina priestoru kandidátov obsahujúca kandidátov „blízkych“ kandidátovi s. Zahŕňa platných aj neplatných kandidátov, ktorí sú susedmi s. Susedstvo nemusí byť symetrické – ak x je sused y, y nemusí byť nutne sused x.
Existujú dva spôsoby definovania susedstiev:
Definícia založená na vzdialenosti
Použije sa funkcia vzdialenosti a definuje sa N(x) = {y | dist(x,y) ≤ ε} pre nejaký prah ε.
- Euklidovská vzdialenosť: geometrická vzdialenosť vzdušnou čiarou, používa sa pre spojitú optimalizáciu.
- Hammingova vzdialenosť: počíta pozície, kde sa dva reťazce líšia, používa sa pre diskrétne problémy ako SAT.
Obmedzenie: Treba zvoliť vhodnú metriku a správny parameter ε.
Definícia založená na mapovaní
Použije sa funkcia, ktorá explicitne vymenúva susedov pre každého kandidáta. Štandardné príklady sú k-výmenné susedstvá.
- 1-flip (SAT): zmení sa hodnota jednej premennej, veľkosť susedstva = n premenných.
- 2-swap (TSP): vymenia sa pozície dvoch miest, veľkosť susedstva = n(n-1)/2.
Obmedzenie: Väčšie k znamená väčšie susedstvo a pomalšie vyhodnocovanie.
2. Čo je lokálne prehľadávanie, na čo sa používa a ako funguje? Ako je definované globálne riešenie pre rôzne typy problémov? Aký je rozdiel medzi globálnym a lokálnym riešením pre rôzne typy problémov?
Lokálne prehľadávanie sa zameriava na malý podpriestor kandidátov namiesto celého priestoru. Cieľom je prehľadávať celý priestor kandidátov, ale pohybovať sa len lokálne v rámci definovaného susedstva. Používa sa vtedy, keď je systematické prehľadávanie príliš drahé.
Definície globálneho riešenia
- Optimalizačný problém: kandidát x s najlepšou hodnotou účelovej funkcie spomedzi všetkých kandidátov (minimum alebo maximum).
- Rozhodovací problém: akýkoľvek kandidát x, pre ktorý platí valid(x) (spĺňa všetky podmienky).
Rozdiel medzi lokálnym a globálnym riešením
- Optimalizačný problém: lokálne optimum sa nemusí rovnať globálnemu optimu, môžeme nájsť suboptimálne riešenie. Ide o fundamentálne obmedzenie lokálneho prehľadávania.
- Rozhodovací problém: lokálne sa rovná globálnemu. Ak nájdeme akékoľvek platné riešenie cez lokálne prehľadávanie, je to riešenie celého problému. Všetci platní kandidáti sú ekvivalentní.
3. Popíšte definíciu susedstva pre lokálne prehľadávanie založenú na vzdialenosti. Uveďte príklady a popíšte, ako by sa mohli použiť pre rôzne inštancie problémov. Ako je definovaná funkcia vzdialenosti?
Susedstvo založené na vzdialenosti: N(x) = {y | dist(x,y) ≤ ε} pre funkciu vzdialenosti dist a prah ε.
Všeobecný vzorec vzdialenosti: dist(x,y) = (Σ|xᵢ − yᵢ|ⁿ)^(1/n), kde n určuje typ.
Euklidovská vzdialenosť (n = 2)
Odmocnina zo súčtu štvorcov rozdielov. Používa sa pre spojitú optimalizáciu, kde kandidáti sú vektory reálnych čísel. Pri optimalizácii funkcie f(x₁,x₂) je susedstvo tvorené všetkými bodmi v kruhu s polomerom ε. Meria geometrickú vzdialenosť „vzdušnou čiarou“.
Hammingova vzdialenosť (n = 1)
Súčet absolútnych rozdielov, ktorý počíta pozície, na ktorých sa reťazce líšia. Používa sa pre diskrétne problémy. Pre SAT s binárnymi priradeniami (1011 vs 1001) je Hammingova vzdialenosť 1 (líšia sa v jednej pozícii). Pri farbení grafov by susedstvo mohlo tvoriť všetky farbenia líšiace sa v najviac k vrcholoch.
Parameter ε určuje veľkosť susedstva:
- Menšie ε → užšie susedstvo, menej susedov
- Väčšie ε → širšie susedstvo, viac susedov
- Výber závisí od problému a škálovania kandidátov
4. Popíšte definíciu susedstva pre lokálne prehľadávanie založenú na mapovaní. Uveďte príklady a popíšte, ako by sa mohli použiť pre rôzne inštancie problémov. Ako môže byť mapovanie kandidátov použité v prehľadávaní?
Susedstvo založené na mapovaní: funkcia map: S → 2^S explicitne špecifikuje, ktorí kandidáti sú susedmi každého kandidáta. Susedstvo N(x) je dané ako zoznam kandidátov mapovaných ako susedia x.
Štandardné k-výmenné susedstvá menia naraz k komponentov kandidáta.
1-flip susedstvo (SAT)
Zmení sa hodnota jednej premennej. Pre n premenných je veľkosť susedstva n, pretože môžeme prepnúť ktorúkoľvek z n premenných. Príklad: pre kandidáta (T, F, T) sú susedia {(F, F, T), (T, T, T), (T, F, F)}. Pre SAT inštanciu so 100 premennými má susedstvo 100 kandidátov.
2-swap susedstvo (TSP)
Vymenia sa pozície dvoch miest. Pre n miest je veľkosť susedstva n(n-1)/2, pretože môžeme vymeniť ľubovoľnú dvojicu. Príklad: pre trasu (1, 2, 3, 4) dáva výmena pozícií 1 a 3 trasu (3, 2, 1, 4). Pre 50 miest má susedstvo 50×49/2 = 1225 kandidátov.
Všeobecná k-výmena
Zmení sa k komponentov súčasne. Väčšie k znamená viac možností, ale pomalšie vyhodnocovanie.
Použitie mapovania v prehľadávaní
Funkcia map môže generovať susedov procedurálne – nemusíme uchovávať celý zoznam susedov, ale generujeme ich podľa potreby. Šetrí to pamäť pre veľké susedstvá.
5. Čo je graf susedstva a čo vyjadruje? Vysvetlite vlastnosti symetria, stupeň vrcholu, ako aj regularita, súvislosť a priemer grafu.
Graf susedstva je orientovaný graf indukovaný reláciou susedstva na priestore kandidátov. Vrcholy sú kandidáti S a orientovaná hrana vedie z x do y, keď y ∈ N(x). Vyjadruje štruktúru vzťahov susednosti a ovplyvňuje správanie lokálneho prehľadávania.
- Symetria: ak je relácia susedstva symetrická (x ∈ N(y) implikuje y ∈ N(x)), graf je neorientovaný. Príklad: 2-swap v TSP je symetrický. Asymetrické susedstvá vytvárajú orientované grafy.
- Stupeň vrcholu: rovná sa veľkosti susedstva, deg(x) = |N(x)|. Určuje, koľko možností existuje v každom kroku prehľadávania. Vyšší stupeň znamená viac volieb, ale väčšie náklady na vyhodnotenie.
- Regularita: všetky vrcholy majú rovnaký stupeň, |N(x)| je konštantné pre všetky x. Príklad: 1-flip pre SAT je regulárny (vždy n susedov). Neregulárne susedstvá majú rôzne veľkosti pre rôznych kandidátov.
- Súvislosť: existuje cesta medzi každou dvojicou vrcholov. Súvislý graf susedstva zaručuje, že z ľubovoľného kandidáta môžeme dosiahnuť ľubovoľného iného kandidáta postupnosťou lokálnych krokov. Dôležité pre možnosť dosiahnuť globálne optimum.
- Priemer: maximálna najkratšia cesta medzi ľubovoľnými dvoma vrcholmi. Menší priemer znamená rýchlejší pohyb priestorom kandidátov – medzi vzdialenými kandidátmi sa dostaneme v menej krokoch.
6. Aké sú komponenty lokálneho prehľadávania? Vysvetlite ich úlohu a uveďte príklady.
Algoritmus lokálneho prehľadávania pre inštanciu π vyžaduje niekoľko komponentov:
Priestor kandidátov, susedstvo a pamäť
- S(π): priestor kandidátov závislý od inštancie problému
- N(π): relácia susedstva definujúca, ktorí kandidáti sú susedia
- M(π): pamäť algoritmu uchovávajúca aktuálny stav a históriu prehľadávania
Inicializačná funkcia init(π)
Vytvára počiatočného kandidáta a inicializuje pamäť. Vstupom je inštancia problému, výstupom dvojica (s, m) s počiatočným kandidátom a pamäťou. Príklad: Uniform Random Picking (URP) vyberá každého kandidáta s pravdepodobnosťou 1/|S|.
Krokova funkcia step(π)
Vykoná jeden krok prehľadávania. Vstupom je aktuálny kandidát s a pamäť m, výstupom nový kandidát s' a aktualizovaná pamäť m'. Určuje stratégiu prehľadávania – môže byť náhodná (URW), zlepšujúca (iteratívne zlepšovanie) alebo sofistikovanejšia.
Terminačný predikát term(π)
Rozhoduje, či prehľadávanie ukončiť. Vstupom je aktuálny kandidát a pamäť, výstupom TRUE (zastav) alebo FALSE (pokračuj). Príklady:
- Dosiahnutie lokálneho optima (žiadni zlepšujúci susedia)
- Dosiahnutie limitu iterácií
- Vypršanie časového limitu
- Nájdenie platného riešenia (pre rozhodovacie problémy)
7. Pre aký typ problému sa používa nasledujúca štruktúra lokálneho prehľadávania? Popíšte jednotlivé kroky.
Táto štruktúra sa používa pre rozhodovací problém, kde cieľom je nájsť akéhokoľvek kandidáta spĺňajúceho všetky podmienky.
Inicializácia: (s, m) = init(π) vytvorí počiatočného kandidáta s a inicializuje pamäť m. Typicky používa uniformný náhodný výber z priestoru kandidátov.
Iteračná slučka: slučka opakuje kroky, kým nie je splnená podmienka ukončenia. Každá iterácia volá step(s, m), ktorý vykoná jeden krok prehľadávania a aktualizuje kandidáta aj pamäť. Pokračuje až do dosiahnutia podmienky ukončenia (napr. lokálne optimum alebo limit iterácií).
Validácia a výstup: po ukončení slučky skontroluj, či je finálny kandidát s platný. Ak je platný, vráť ho ako riešenie. Ak nie je platný, vráť prázdny výsledok (riešenie sa nenašlo).
Kľúčová charakteristika: žiadne sledovanie najlepšieho kandidáta – pre rozhodovací problém stačí nájsť akéhokoľvek platného kandidáta. Všetci platní kandidáti sú ekvivalentné riešenia, takže kontrolujeme len finálneho.
8. Pre aký typ problému sa používa nasledujúca štruktúra lokálneho prehľadávania? Popíšte jednotlivé kroky.
Táto štruktúra sa používa pre optimalizačný problém, konkrétne minimalizáciu (kvôli podmienke f(s) < f(r) – aktualizujeme, keď nájdeme menšiu hodnotu).
Inicializácia: (s, m) = init(π) vytvorí počiatočného kandidáta a pamäť. Potom r = s nastaví počiatočného kandidáta ako najlepšieho doteraz nájdeného.
Iteračná slučka so sledovaním najlepšieho: slučka opakuje kroky až do ukončenia. Po každom kroku porovnaj aktuálneho kandidáta s s najlepším kandidátom r pomocou f(s) < f(r). Ak je aktuálny lepší (menšia hodnota účelovej funkcie), aktualizuj r = s. Premenná r udržiava najlepšieho kandidáta nájdeného počas celého prehľadávania.
Validácia a výstup: po ukončení slučky skontroluj platnosť najlepšieho kandidáta r. Ak je platný, vráť ho ako najlepšie nájdené riešenie. Ak nie je platný, vráť prázdny výsledok.
Kľúčová charakteristika: udržiava najlepšieho kandidáta r, aktualizovaného po každom kroku. To umožňuje vrátiť najlepšie riešenie aj vtedy, keď algoritmus neskôr navštívi horších kandidátov. Trajektória prehľadávania môže prechádzať horšími riešeniami, ale najlepšie si vždy pamätáme.
9. Čo je trajektória prehľadávania, od čoho závisí a čo nám hovorí o prehľadávaní? Uveďte a vysvetlite príklady neinformovaných stratégií prehľadávania.
Trajektória prehľadávania je postupnosť kandidátov (s₀, s₁, ..., sₙ) navštívených počas prehľadávania. s₀ je počiatočný kandidát a každý nasledujúci sᵢ₊₁ sa získa aplikovaním krokovej funkcie na sᵢ. Ukazuje cestu algoritmu priestorom kandidátov.
Trajektória závisí od:
- funkcie init() (určuje štartovací bod)
- funkcie step() (určuje stratégiu pohybu)
Trajektória nám hovorí:
- či je prehľadávanie systematické alebo náhodné
- či zostáva lokálne, alebo skáče po priestore
- či konverguje k lokálnym optimám
Neinformované stratégie prehľadávania
URP (Uninformed Random Picking): každý kandidát je vybraný nezávisle s pravdepodobnosťou 1/|S|, bez ohľadu na predchádzajúcich kandidátov. Žiadny vzťah medzi po sebe nasledujúcimi kandidátmi – môže skočiť kamkoľvek v priestore. Nepoužíva susedstvo ani vyhodnocovaciu funkciu. Veľmi neefektívne, pretože ignoruje všetku štruktúru.
URW (Uninformed Random Walk): každý kandidát je vybraný uniformne zo susedstva predchádzajúceho kandidáta s pravdepodobnosťou 1/|N(s)|. Po sebe nasledujúci kandidáti sú vždy susedia v grafe susedstva. Používa susedstvo na lokálny pohyb, ale stále nepoužíva vyhodnocovaciu funkciu na smerovanie prehľadávania k lepším riešeniam.
Kľúčový rozdiel: URP môže skočiť kamkoľvek v priestore S, kým sa URW pohybuje len lokálne v rámci susedstva. Obe sú neinformované, pretože ignorujú vyhodnocovaciu funkciu – nepreferujú lepších kandidátov pred horšími.
10. Nasledujúci pseudokód popisuje lokálne prehľadávanie pre optimalizačný problém. Popíšte jednotlivé kroky, napíšte, či ide o minimalizačnú alebo maximalizačnú úlohu, a vysvetlite, čo by sme potrebovali zmeniť na riešenie druhého typu úlohy.
Ide o maximalizačný problém, čo je viditeľné z podmienky f(s) > f(r) – najlepšieho aktualizujeme, keď nájdeme väčšiu hodnotu účelovej funkcie.
Inicializácia: vytvor počiatočného kandidáta a pamäť pomocou (s, m) = init(π). Nastav r = s, aby bol počiatočný kandidát najlepší doteraz.
Hlavná slučka: opakuj kroky, kým nie je splnená podmienka ukončenia. Každá iterácia generuje nového kandidáta pomocou step(s, m).
Aktualizácia najlepšieho: porovnaj aktuálneho kandidáta s najlepším pomocou f(s) > f(r). Ak má aktuálny väčšiu hodnotu účelovej funkcie (lepší pre maximalizáciu), aktualizuj r = s.
Výstup: skontroluj platnosť najlepšieho kandidáta r a vráť ho, alebo vráť prázdny výsledok, ak nie je platný.
Zmena na minimalizáciu
- Zmeň porovnanie z f(s) > f(r) na f(s) < f(r).
- Týmto sa r aktualizuje, keď nájdeme kandidáta s s menšou hodnotou účelovej funkcie.
- Voliteľne inicializuj s f(r) = ∞ namiesto použitia prvého kandidáta, aby bolo zaistené správne porovnanie.