24b - Metódy lokálneho prehľadávania
- používajú sa na riešenie úloh, pri kotrých je podstatné nájdenie optimálneho riešenia (cesta k nemu je nedpostatná)
- príklady úloh: rozmiestnenie súčiastok na dosku s plošnými spojmi, rozloženie tovaru v obchode
- neprehľadávajú stavový priestor systematicky, ale majú 2 prednosti:
- majú úplne zanedbateľnú časovú náročnosť
- často dospejú k riešeniu v rozsiahlych stavových priestoroch
Metóda Hill - climbing
- používa na hodnotenie uzla len heuristickú funkciu, ktorá ohodnocuje kvalitu riešenia
- Vytvoř uzel Current totožný s počátečním uzlem s0 (včetně jeho ohodnocení).
- Expanduj uzel Current, ohodnoť jeho bezprostřední následníky a vyber z nich nejlépe ohodnoceného (nazvěme jej Next).
- Je-li ohodnocení uzlu Current lepší než ohodnocení uzlu Next, ukonči řešení a vrať jako výsledek uzel Current. Jinak pokračuj.
- Ulož uzel Next do uzlu Current a vrať se na bod 2.
- hlavným problémom sú lokálne extrémy (cez ne sa metóda nedostane)
Metóda simulovaného žíhania
- stochastická metóda, cieľom je prekonanie lokálnych extrémov
- vychádza z princípu žíhania kovov
- Vytvoř tabulku s předpisem pro klesání teploty v závislosti na kroku výpočtu.
- Vytvoř uzel Current totožný s počátečním uzlem s0 (včetně jeho ohodnocení). Nastav krok výpočtu na nulu (k = 0).
- Z tabulky zjisti aktuální teplotu T (T = f(k)). Je-li tato teplota nulová (T = 0) ukonči řešení a vrať jako výsledek uzel Current.
- Expanduj uzel Current a z jeho bezprostředních následníků vyber náhodně jednoho z nich (nazvěme jej Next).
- Vypočítej rozdíl ohodnocení uzlů Current a Next: DE = value(Next) – value(Current).
- Jestliže DE > 0, tak ulož uzel Next do uzlu Current, jinak ulož uzel Next do uzlu Current s pravděpodobností eDE/T.
- Inkrementuj krok výpočtu k a vrať se na bod 3.