| dbo:abstract
|
- A számítástudományban a hegymászó algoritmus egy eljárás, amely a keresőalgoritmusok osztályába tartozik. Az eljárás egy kezdeti - véletlenszerű - megoldásból indul ki, majd iteratívan megkísérel egy mind jobb megoldást találni minden lépésben, mindig egy elemet megváltoztatva az eredményhalmazon, ameddig nem talál jobbat. Az algoritmus relatíve egyszerűsége okán az egyik leggyakrabban elsőnek választott optimizáló eljárás. Széles körben használja a mesterséges intelligencia tudománya, mivel bár fejlettebb algoritmusok is léteznek, sok esetben ez is elég jó teljesítményt képes felmutatni. A hegymászó algoritmus megtalálja az optimális megoldást a konvex problémákhoz – más problémák esetén csak a helyi szélsőértéket fogja megtalálni (azokat a megoldásokat, amelyeken a szomszédos konfigurációk sem képesek javítani), amely nem feltétlenül a legjobb megoldás (a globális szélsőérték) az összes lehetséges megoldás közül. A hegymászó algoritmussal konvex problémákat megoldó algoritmusokra példa a lineáris programozás és a bináris keresés szimplex algoritmusa. Hogy elkerülje a helyi szélsőértéken ragadást, újra is indulhat (azaz ismételt helyi keresés), vagy bonyolultabb sémákat alkalmazhat iterációkon (például iterált helyi keresés), vagy memórián (például reaktív keresésoptimalizálás és tabukeresés), vagy memóriamentes sztochasztikus módosításokon (mint például a szimulált hűtés). A hegymászó algoritmus gyakran jobb eredményt nyújthat, mint más algoritmusok, ha a keresés elvégzésére álló idő korlátozott, például valósidejű rendszereknél, mindaddig, amíg kis számú lépés elegendő a jó megoldáshoz (az optimális megoldás vagy egy megközelítése). A buborékrendezés hegymászó algoritmusnak tekinthető (minden szomszédos elemcsere csökkenti a rendezetlen elempárok számát), ám ez a megközelítés messze nem hatékony még egyszerű N esetében sem, mivel a cserék száma négyzetesen növekszik. További előnye, hogy a futtatás bármely pillanatában is szakítjuk meg a működését, a (rész)megoldás mindig elérhető. (hu)
- A számítástudományban a hegymászó algoritmus egy eljárás, amely a keresőalgoritmusok osztályába tartozik. Az eljárás egy kezdeti - véletlenszerű - megoldásból indul ki, majd iteratívan megkísérel egy mind jobb megoldást találni minden lépésben, mindig egy elemet megváltoztatva az eredményhalmazon, ameddig nem talál jobbat. Az algoritmus relatíve egyszerűsége okán az egyik leggyakrabban elsőnek választott optimizáló eljárás. Széles körben használja a mesterséges intelligencia tudománya, mivel bár fejlettebb algoritmusok is léteznek, sok esetben ez is elég jó teljesítményt képes felmutatni. A hegymászó algoritmus megtalálja az optimális megoldást a konvex problémákhoz – más problémák esetén csak a helyi szélsőértéket fogja megtalálni (azokat a megoldásokat, amelyeken a szomszédos konfigurációk sem képesek javítani), amely nem feltétlenül a legjobb megoldás (a globális szélsőérték) az összes lehetséges megoldás közül. A hegymászó algoritmussal konvex problémákat megoldó algoritmusokra példa a lineáris programozás és a bináris keresés szimplex algoritmusa. Hogy elkerülje a helyi szélsőértéken ragadást, újra is indulhat (azaz ismételt helyi keresés), vagy bonyolultabb sémákat alkalmazhat iterációkon (például iterált helyi keresés), vagy memórián (például reaktív keresésoptimalizálás és tabukeresés), vagy memóriamentes sztochasztikus módosításokon (mint például a szimulált hűtés). A hegymászó algoritmus gyakran jobb eredményt nyújthat, mint más algoritmusok, ha a keresés elvégzésére álló idő korlátozott, például valósidejű rendszereknél, mindaddig, amíg kis számú lépés elegendő a jó megoldáshoz (az optimális megoldás vagy egy megközelítése). A buborékrendezés hegymászó algoritmusnak tekinthető (minden szomszédos elemcsere csökkenti a rendezetlen elempárok számát), ám ez a megközelítés messze nem hatékony még egyszerű N esetében sem, mivel a cserék száma négyzetesen növekszik. További előnye, hogy a futtatás bármely pillanatában is szakítjuk meg a működését, a (rész)megoldás mindig elérhető. (hu)
|
