| dbpprop:abstract
|
- In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is relatively simple to implement, making it a popular first choice. Although more advanced algorithms may give better results, in some situations hill climbing works just as well. Hill climbing can be used to solve problems that have many solutions, some of which are better than others. It starts with a random (potentially poor) solution, and iteratively makes small changes to the solution, each time improving it a little. When the algorithm cannot see any improvement anymore, it terminates. Ideally, at that point the current solution is close to optimal, but it is not guaranteed that hill climbing will ever come close to the optimal solution. For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much better route is obtained. Hill climbing is used widely in artificial intelligence, for reaching a goal state from a starting node. Choice of next node and starting node can be varied to give a list of related algorithms.
- Bergsteigeralgorithmus (englisch hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Von einer gegebenen Startlösung aus wird solange zum besten Punkt - aus der Nachbarschaft der aktuellen Lösung - gegangen, bis keine Verbesserung des Zielfunktionswertes mehr möglich ist. Da das Verfahren sehr leicht in lokalen Optima steckenbleibt, wird das Verfahren meist mit zufällig ausgewählten Startpunkten wiederholt. Anschaulich gesprochen wird ein virtueller Bergsteiger auf eine bestimmte Stelle in die Wertelandschaft gesetzt. Von allen benachbarten Stellen dieser Stelle sucht er sich nun diejenige aus, die am höchsten ist oder eine aus denjenigen heraus, die höher sind als die aktuelle Stelle. (schwächer) Wenn es zur neuen Stelle bergauf geht, dann geht der Bergsteiger diesen Weg und führt das Verfahren erneut aus, sonst hört er auf und beendet das Verfahren. Die Ausgabe des Bergsteigeralgorithmus ist damit die Position des Bergsteigers in der Wertelandschaft. Es ist klar, dass diese Position einer Stelle eines lokalen Maximums entspricht. Da es bei vielen Problemen viele lokale Maxima gibt, ist damit ein globales Maximum, was häufig das Ziel der Lösung eines Optimierungsproblems ist, nicht notwendigerweise gefunden. Der Bergsteigeralgorithmus kann als simpler evolutionärer Algorithmus aufgefasst werden, wobei es nur ein Individuum, keine Rekombination und eine "seltsame" Mutations-Operation gibt. Das Problem, dass der Bergsteigeralgorithmus nur ein lokales Maximum liefert, wird zum Beispiel so angegangen: mehrere Bergsteiger (eine ganze Population davon) an verschiedenen Startpunkten ein zufälliger großer Hüpfer (Mutation) der aktuellen Position in eine beliebige Richtung, danach ein erneutes Anwenden des Bergsteigeralgorithmus liefert mit gewisser Wahrscheinlichkeit ein höheres lokales Maximum. Eine praktische Implementierung so eines Bergsteigeralgorithmus mit Schrittweitensteuerung ist im Artikel Downhill-Simplex-Verfahren beschrieben. Die erwähnten Maßnahmen zum Vermeiden lokaler Optima lassen sich dort genauso ergänzen.
- Gradientní algoritmus (Hill-climbing, horolezecký algoritmus) je nejjednodušší informovaná metoda prohledávání stavového prostoru. Jedná se o gradientní metodu expandující nejlépe ohodnocený uzel stavového prostoru. Po expanzi uzlu jsou zapomenuti jeho předchůdci. Metoda se pohybuje stále dopředu, dokud nenarazí na uzel, jehož potomci mají horší hodnocení než tento expandovaný uzel. Jakmile je takovýto uzel nalezen, je ukončeno hledání. Gradientní metody jsou jednoduché, ale nemusí nalézt globálním maximum. Při průchodu mohou zůstat v lokálním extrému, ze kterého se již nedostanou. Navíc si žádným způsobem nepamatují cestu a tak se může stát, že uváznou v nekonečné smyčce.
- 山登り法（やまのぼりほう、英 hill climbing HCと略記）とはアルゴリズムの一種である。最も代表的な局所探索法として知られている。
- 爬山算法是一种局部择优的方法，采用启發式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 局部最大 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。 解决方法：随机重启爬山算法
|
| rdfs:comment
|
- In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is relatively simple to implement, making it a popular first choice. Although more advanced algorithms may give better results, in some situations hill climbing works just as well. Hill climbing can be used to solve problems that have many solutions, some of which are better than others.
- Bergsteigeralgorithmus (englisch hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Von einer gegebenen Startlösung aus wird solange zum besten Punkt - aus der Nachbarschaft der aktuellen Lösung - gegangen, bis keine Verbesserung des Zielfunktionswertes mehr möglich ist. Da das Verfahren sehr leicht in lokalen Optima steckenbleibt, wird das Verfahren meist mit zufällig ausgewählten Startpunkten wiederholt.
- Gradientní algoritmus (Hill-climbing, horolezecký algoritmus) je nejjednodušší informovaná metoda prohledávání stavového prostoru. Jedná se o gradientní metodu expandující nejlépe ohodnocený uzel stavového prostoru. Po expanzi uzlu jsou zapomenuti jeho předchůdci. Metoda se pohybuje stále dopředu, dokud nenarazí na uzel, jehož potomci mají horší hodnocení než tento expandovaný uzel. Jakmile je takovýto uzel nalezen, je ukončeno hledání.
- 山登り法（やまのぼりほう、英 hill climbing HCと略記）とはアルゴリズムの一種である。最も代表的な局所探索法として知られている。
- 爬山算法是一种局部择优的方法，采用启發式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 局部最大 高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。 解决方法：随机重启爬山算法
|
![[RDF Data]](/statics/sw-cube.png)
