CêIT Homeسەرەکی
Glossaryفەرهەنگی زاراوەکان
Artificial Intelligenceژیریی دەستکرد

Chapterبەش 5 · Lectureوانە 5.1

Hill Climbing and Its Problemsچیاهەڵەگڕی و کێشەکانی

Hill climbing is a local search algorithm for optimization problems: it keeps one current state and moves to a better neighbour until none is better. Learn its features, the state-space landscape, the simple, steepest-ascent and stochastic types, run them in Python, and see why they get stuck on local maxima, plateaus and ridges — and how random restarts and sideways moves help.

ئەلگۆریزمێکی بۆ : یەک ئێستا ڕادەگرێت و دەچێتە دراوسێیەکی باشتر تا هیچ دراوسێیەک باشتر نەبێت. تایبەتمەندییەکانی، ، جۆرەکانی سادە، تیژ و هەڕەمەکی دەناسیت، بە کاریان پێ دەکەیت و دەبینیت بۆچی لە ، و دەچەقن — هەروەها هەڕەمەکی و جووڵەی لاتەنیشت چۆن یارمەتی دەدەن.

24 min read22 خولەک خوێندنەوە · 19 stepsهەنگاو

What you will learnچی فێر دەبیت

  • Explain what an optimization problem is and how local search differs from path-finding search.
  • Read a state-space landscape: global and local maximum, plateau, shoulder, flat local maximum and ridge.
  • Describe and compare simple, steepest-ascent and stochastic hill climbing, and run them in Python.
  • Explain why hill climbing gets stuck and choose a real cure (random restarts, sideways moves, more moves, simulated annealing).
  • ڕوونی بکەیتەوە چییە و چۆن لە گەڕان بۆ جیاوازە.
  • بخوێنیتەوە: ، ، ، ، لووتکەی تەخت و .
  • ، و وەسف و بەراورد بکەیت و بە کاریان پێ بکەیت.
  • ڕوونی بکەیتەوە بۆچی دەچەقێت و چارەسەرێکی ڕاستەقینە هەڵبژێریت ( هەڕەمەکی، جووڵەی لاتەنیشت، جووڵەی زیاتر، ).

Finding the best state, not a pathدۆزینەوەی باشترین دۆخ، نەک ڕێگە

In the search lessons the answer was a path: the list of steps from the start to a goal. Many problems are different. Nobody cares how we got there; we only want the best state. Examples: the shortest round trip for a salesman, the best timetable for a school, or the best seat in a cinema. Problems like these are called .

لە وانەکانی گەڕاندا وەڵامەکە بوو: لیستی ئەو هەنگاوانەی لە سەرەتاوە دەگەنە ئامانج. زۆر کێشە بەم شێوەیە نین. گرنگ نییە چۆن گەیشتینە ئەوێ، تەنیا باشترین دەوێت. بۆ نموونە: کورتترین گەشتی بازنەیی بۆ فرۆشیارێک، باشترین خشتەی وانەکان بۆ قوتابخانەیەک، یان باشترین کورسی لە سینەمادا. بەم جۆرە کێشانە دەوترێت .

Definitionپێناسە

A local search that repeatedly moves to a better neighbouring state and stops when no neighbour is better. It is fast and uses little memory, but it can get stuck on a local maximum, a plateau or a ridge.

کە جار لە دوای جار بۆ دراوسێی باشتر دەچێت و کاتێک هیچ دراوسێیەک باشتر نەبوو دەوەستێت. خێرایە و بیرگەی کەم بەکار دەهێنێت، بەڵام دەکرێت لە ، یان بچەقێت.

The course notes describe it like this: hill climbing is a widely used optimization algorithm in AI that helps to find the best possible solution to a problem. It belongs to the family of algorithms. They are used when the goal is to pick the best solution from a set of possible candidates. A local search algorithm keeps only the current state in memory and moves from it to a neighbour: a state that is one small change away.

تێبینییەکانی کۆرسەکە بەم شێوەیە دەیناسێنن: باشترینکردنە کە لە زۆر بەکار دێت و یارمەتی دەدات بۆ کێشەیەک بدۆزرێتەوە. سەر بە خێزانی ئەلگۆریزمەکانی . ئەم ئەلگۆریزمانە کاتێک بەکار دێن کە ئامانج هەڵبژاردنی چارەسەرە هەرە باشەکەیە لە نێو کۆمەڵێک چارەسەری ئەگەری. تەنیا ئێستا لە بیرگەدا ڕادەگرێت و لێیەوە دەچێتە دراوسێیەک: کە تەنیا بە گۆڕانکارییەکی بچووک لێی جیاوازە.

Climbing a mountainسەرکەوتن بەسەر شاخدا

The algorithm's name says it all. Imagine that you want to reach the top of a mountain. You look around you to see whether there is a higher point near you. If there is, you go there. You keep doing this until you reach the top of the mountain.

ئەم ئەلگۆریزمە ناوەکەی بە خۆیەوەیەتی. بیهێنە بەرچاوت کە دەتەوێت بگەیتە لووتکەی شاخێک. لە چواردەوری خۆت دەڕوانیت تاکو بزانیت هیچ خاڵێکی بەرز لە نزیک خۆتەوە هەیە یان نا. ئەگەر هەبوو، دەچیتە ئەوێ. ئەمە دووبارە دەکەیتەوە تا دەگەیتە لووتکەی شاخەکە.

Where the analogy stops workingسنووری ئەم نموونەیە

A real climber can look far away. Hill climbing sees only the states right next to it, so it can stop on a small top and believe it is the highest one. That is the main weakness you will meet in this lesson.

شاخەوانێکی ڕاستەقینە دەتوانێت سەیری دوور بکات. تەنیا ئەو دەبینێت کە ڕێک لە تەنیشتینەوەن، بۆیە ڕەنگە لەسەر لووتکەیەکی بچووک بوەستێت و وا بزانێت بەرزترینە. ئەمە سەرەکیترین لاوازییە کە لەم وانەیەدا دەیبینیت.

A widely discussed example is the : a salesman must visit every city once and then return home, and we want to minimize the total distance. A state is one complete order of the cities. A neighbour is the same order with two cities swapped. The value of a state is the total distance, and lower is better.

نموونەیەکی ناسراو : فرۆشیارێک دەبێت سەردانی هەر شارێک یەک جار بکات و پاشان بگەڕێتەوە ماڵەوە. ئێمە دەمانەوێت کۆی ماوەی گەشتەکە کەم بکەینەوە. هەر ڕیزبەندییەکی تەواوی شارەکانە. دراوسێکەی هەمان ڕیزبەندییە، بەڵام شوێنی دوو شار گۆڕدراوە. بەهای هەر کۆی ماوەکەیە و کەمتر باشترە.

Quick checkپشکنینی خێراWhat does hill climbing keep in memory while it works? لە کاتی کارکردندا چی لە بیرگەدا ڕادەگرێت؟

Three features of hill climbingسێ تایبەتمەندیی چیاهەڵەگڕی

The notes list three features. Each one explains a strength and a weakness of the algorithm.

تێبینییەکان سێ تایبەتمەندی دەژمێرن. هەریەکەیان لایەنێکی بەهێز و لایەنێکی لاوازی ئەلگۆریزمەکە ڕوون دەکاتەوە.

  1. : hill climbing is a variant of the generate-and-test method. It produces a new state and tests how good it is. This feedback helps it decide which direction to move in the search space.
  2. Greedy approach: it always moves in the direction that improves the value (or lowers the cost) right now. It does not plan ahead. This is the idea of a .
  3. No backtracking: it does not remember the earlier states, so it never goes back to try another way.
  1. : جۆرێکە لە ڕێگەی . نوێ بەرهەم دەهێنێت و دەپشکنێت کە چەند باشە. ئەم وەڵامە یارمەتی دەدات بڕیار بدات بەرەو کام ئاڕاستە لە فەزای گەڕاندا بجووڵێت.
  2. ڕێبازی چاوچنۆکانە: هەمیشە بەو ئاڕاستەیەدا دەجووڵێت کە ئێستا بەهاکە باشتر دەکات (یان کۆستەکە کەم دەکاتەوە). پلان بۆ داهاتوو دانانێت. ئەمە بیرۆکەی .
  3. بێ : پێشوو لە بیر ناگرێت، بۆیە هەرگیز ناگەڕێتەوە دواوە تاکو ڕێگەیەکی تر تاقی بکاتەوە.
Quick checkپشکنینی خێراWhich feature explains why hill climbing can never return to an earlier state?کام تایبەتمەندی ڕوونی دەکاتەوە بۆچی هەرگیز ناتوانێت بگەڕێتەوە بۆ پێشوو؟

The state-space landscapeدیمەنی فەزای دۆخەکان

To understand hill climbing, draw the problem as a landscape. The is a graph of all the states and how good each one is. The x-axis shows the state space (the states side by side). The y-axis shows a function: an (a score, higher is better) or a cost function (lower is better).

بۆ تێگەیشتن لە ، کێشەکە وەک دیمەنێکی سروشتی بکێشە. گرافێکی هەموو و چەندێتیی باشیی هەریەکەیانە. تەوەرەی x پیشان دەدات ( لە تەنیشت یەکەوە). تەوەرەی y کردارێک پیشان دەدات: یان (نمرەیەک، زیاتر باشترە) یان کرداری کۆست (کەمتر باشترە).

If the y-axis is an objective function, the goal is the : the highest point of the whole landscape. If the y-axis is a cost, the goal is the : the lowest point. Hill climbing walks uphill (or downhill for a cost) one neighbour at a time.

ئەگەر تەوەرەی y بێت، ئامانج : بەرزترین خاڵی هەموو دیمەنەکە. ئەگەر تەوەرەی y کۆست بێت، ئامانج : نزمترین خاڵ. بە یەک دراوسێ لە هەر جارێکدا بەرەو سەرەوە دەڕوات (یان بۆ کۆست بەرەو خوارەوە).

A curve over the states 0 to 23. The y-axis is the objective function, the x-axis the state space. State 3 is a local maximum with value 9. States 8 to 10 are a shoulder: flat at value 10, but the curve rises again after state 10. State 13 is the global maximum with value 16. States 17 to 20 are a flat local maximum at value 11 with no way up. A blue dot marks the current state 6, and an arrow shows hill climbing moving uphill. A note says shoulders and flat maxima are plateaus.هێڵێکی چەماوە بەسەر دۆخەکانی 0 تا 23دا. تەوەرەی y کرداری ئامانجە و تەوەرەی x فەزای دۆخەکان. دۆخی 3 لووتکەی ناوخۆییە بە بەهای 9. دۆخەکانی 8 تا 10 شانن: لە بەهای 10دا تەختن، بەڵام دوای 10 هێڵەکە دیسان بەرز دەبێتەوە. دۆخی 13 لووتکەی لووتکەکانە بە بەهای 16. دۆخەکانی 17 تا 20 لووتکەی ناوخۆیی تەختن بە بەهای 11 و ڕێگەی سەرکەوتنیان نییە. خاڵێکی شین دۆخی ئێستا (6) نیشان دەدات و تیرێک پیشان دەدات چیاهەڵەگڕی بەرەو سەرەوە دەڕوات. تێبینییەک دەڵێت شانەکان و لووتکە تەختەکان تەختاییەکانن.
One landscape with every part the notes name. The same 24 values are used in the Python code below.یەک دیمەن بە هەموو ئەو بەشانەی تێبینییەکان ناویان دەبەن. هەمان ⁦24⁩ بەها لەو کۆدەی کە لە خوارەوەیە بەکار هاتوون.CêIT
Harvard CS50’s Artificial Intelligence with Python – Full University CoursefreeCodeCamp.org · Englishئینگلیزی · 5.1M viewsبینین · 134K likesلایک · Partبەشی 5:35:28–5:41:32 (ofلە 11:51:22)

Harvard's CS50 AI lecturer explains each idea with clear pictures and Python code; each placement plays only the chapter that matches its screen.

مامۆستای کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard هەر بیرۆکەیەک بە وێنەی ئاشکرا و کۆدی ڕوون دەکاتەوە؛ لە هەر شوێنێک تەنها ئەو بەشەی لێدەدرێت کە لەگەڵ ئەو شاشەیە دەگونجێت.

Plays 5:35:28–5:41:32 of the full course: local search, the houses-and-hospitals example, and the state-space landscape with objective and cost functions.

لە کۆرسە تەواوەکە، ⁦5:35:28⁩ تا ⁦5:41:32⁩ لێدەدرێت: ، نموونەی خانووەکان و نەخۆشخانەکان، هەروەها لەگەڵ و کۆست.

The state-space landscapeدیمەنی فەزای دۆخەکان

The parts of the landscapeبەشەکانی دیمەنەکە

The pictures in the notes use these labels, but the text explains only some of them. Here they all are, with the states of our figure:

وێنەکانی ناو تێبینییەکان ئەم ناونیشانانە بەکار دەهێنن، بەڵام دەقەکە تەنیا هەندێکیان ڕوون دەکاتەوە. هەموویان لێرەدان، لەگەڵ وێنەکەی ئێمە:

PartبەشMeaningواتاIn the figureلە وێنەکەدا
The best state of all: higher than every other state.باشترین : لە هەموو تر بەرزترە.state 13 (16) ⁦13 (16)⁩
Higher than each of its neighbours, but lower than the global maximum.لە هەموو دراوسێکانی بەرزترە، بەڵام لە نزمترە.state 3 (9) ⁦3 (9)⁩
Flat local maximum تەختA flat top: the neighbours have the same value, and no direction leads up.لووتکەیەکی تەخت: دراوسێکان هەمان بەهایان هەیە و هیچ ئاڕاستەیەک بەرەو سەرەوە نابات.states 17–20 (11) ⁦17–20 (11)⁩
A flat area with an uphill edge: if you walk along it, the land rises again.ناوچەیەکی تەخت کە لێوارێکی سەرەوژووری هەیە: ئەگەر بەسەریدا بڕۆیت، زەوییەکە دیسان بەرز دەبێتەوە.states 8–10 (10) ⁦8–10 (10)⁩
Any flat area where the neighbours have the same value. Shoulders and flat local maxima are both plateaus.هەر ناوچەیەکی تەخت کە دراوسێکان تێیدا هەمان بەهایان هەیە. و لووتکە ناوخۆییە تەختەکان هەردووکیان .8–10 and 17–20⁦8–10⁩ و ⁦17–20⁩
Current state ئێستاThe state the algorithm is at right now.ئەو کە ئەلگۆریزمەکە ئێستا تێیدایە.state 6 (blue) 6 (شین)
Quick checkپشکنینی خێراIn the figure, hill climbing starts at state 6 and moves uphill. Where does it stop?لە وێنەکەدا لە 6ەوە دەست پێدەکات و بەرەو سەرەوە دەڕوات. لە کوێ دەوەستێت؟

Three types of hill climbingسێ جۆری چیاهەڵەگڕی

The notes name three types. They all climb uphill; they differ only in how they choose the next neighbour.

تێبینییەکان ناوی سێ جۆر دەبەن. هەموویان بەرەو سەرەوە دەڕۆن؛ تەنیا لە چۆنیەتیی هەڵبژاردنی دراوسێی داهاتوودا جیاوازن.

Three types of hill climbingسێ جۆری چیاهەڵەگڕی

Simple hill climbingچیاهەڵەگڕیی سادە

is the simplest way to implement the algorithm. It looks at one neighbour at a time. The first neighbour that is better than the current state becomes the new current state.

سادەترین ڕێگەی جێبەجێکردنی ئەلگۆریزمەکەیە. لە هەر جارێکدا سەیری یەک دراوسێ دەکات. یەکەم دراوسێ کە لە ئێستا باشتر بێت، دەبێتە ئێستای نوێ.

  • It takes less time: it often moves before checking all neighbours.
  • Its solution is less optimal, and finding the best solution is not guaranteed.
  • کاتی کەمتر دەبات: زۆر جار پێش پشکنینی هەموو دراوسێکان دەجووڵێت.
  • چارەسەرەکەی کەمتر باشە و دۆزینەوەی گەرەنتی نییە.
Simple hill climbing, step by stepچیاهەڵەگڕیی سادە هەنگاو بە هەنگاو
  1. Step 1هەنگاوی 1

    Evaluate the initial state. If it is the goal state, return success and stop.

    هەڵبسەنگێنە. ئەگەر بوو، سەرکەوتن ڕابگەیەنە و بوەستە.

  2. Step 2هەنگاوی 2

    Loop until a solution is found or there is no new operator (possible move) left to apply.

    ئەم دووبارە بکەرەوە تا چارەسەرێک دەدۆزرێتەوە یان هیچ (جووڵەیەکی ئەگەری) نوێ نامێنێت بۆ بەکارهێنان.

  3. Step 3: pick a moveهەنگاوی 3: جووڵەیەک هەڵبژێرە

    Select an operator and apply it to the current state. This gives a new state.

    هەڵبژێرە و لەسەر ئێستا جێبەجێی بکە. ئەمە نوێ دەدات.

  4. Step 4: check the new stateهەنگاوی 4: دۆخی نوێ بپشکنە

    a) If it is the goal state, return success and quit. b) Else, if it is better than the current state, make it the current state. c) Else (it is not better), go back to Step 2.

    ئا) ئەگەر بوو، سەرکەوتن ڕابگەیەنە و کۆتایی پێ بهێنە. ب) ئەگینا ئەگەر لە ئێستا باشتر بوو، بیکە بە ئێستا. پ) ئەگینا (باشتر نەبوو)، بگەڕێرەوە بۆ هەنگاوی 2.

  5. Step 5هەنگاوی 5

    Exit.

    دەرچوون.

Quick checkپشکنینی خێراSimple hill climbing checks the neighbours one at a time. Which neighbour does it move to? دراوسێکان یەک بە یەک دەپشکنێت. بۆ کام دراوسێ دەچێت؟

Three types of hill climbingسێ جۆری چیاهەڵەگڕی

Steepest-ascent hill climbingچیاهەڵەگڕیی تیژ

is a variation of simple hill climbing. It examines all the neighbours of the current state and selects the one with the best value (the highest value, or the lowest cost). Because it checks many neighbours, each step takes more time.

جۆرێکی گۆڕاوی . هەموو دراوسێکانی ئێستا دەپشکنێت و ئەوەیان هەڵدەبژێرێت کە باشترین بەهای هەیە (بەرزترین بەها، یان کەمترین کۆست). چونکە زۆر دراوسێ دەپشکنێت، هەر هەنگاوێکی کاتی زیاتر دەبات.

Steepest ascent as written in the notesچیاهەڵەگڕیی تیژ وەک لە تێبینییەکاندا نووسراوە
  1. Step 1هەنگاوی 1

    Evaluate the initial state. If it is the goal state, return success and stop; else make the initial state the current state.

    هەڵبسەنگێنە. ئەگەر بوو، سەرکەوتن ڕابگەیەنە و بوەستە؛ ئەگینا بکە بە ئێستا.

  2. Step 2هەنگاوی 2

    Loop until a solution is found or the current state does not change.

    دووبارەی بکەرەوە تا چارەسەرێک دەدۆزرێتەوە یان ئێستا ناگۆڕێت.

  3. Step 2aهەنگاوی 2ئا

    Let SUCC be a state such that any successor of the current state will be better than it.

    با SUCC بێت کە هەر دراوسێیەکی ئێستا لێی باشتر بێت.

  4. Step 2bهەنگاوی 2ب

    For each operator that applies to the current state: apply it and generate a new state; evaluate the new state; if it is the goal state, return it and quit; else compare it to SUCC, and if it is better, set the new state as SUCC. If SUCC is better than the current state, set the current state to SUCC.

    بۆ هەر کە لەسەر ئێستا جێبەجێ دەبێت: جێبەجێی بکە و نوێ دروست بکە؛ نوێ هەڵبسەنگێنە؛ ئەگەر بوو، بیگەڕێنەوە و کۆتایی پێ بهێنە؛ ئەگینا لەگەڵ SUCC بەراوردی بکە و ئەگەر باشتر بوو، نوێ بکە بە SUCC. ئەگەر SUCC لە ئێستا باشتر بوو، ئێستا بکە بە SUCC.

  5. Step 5هەنگاوی 5

    Exit.

    دەرچوون.

Quick checkپشکنینی خێراWhy does steepest ascent take more time per step than simple hill climbing?بۆچی هەر هەنگاوێکی لە کاتی زیاتر دەبات؟

Three types of hill climbingسێ جۆری چیاهەڵەگڕی

Stochastic hill climbingچیاهەڵەگڕیی هەڕەمەکی

does not examine all its neighbours before it moves. Instead, it selects one neighbour at random and decides whether to choose it as the current state or to examine another state.

پێش جووڵین هەموو دراوسێکانی ناپشکنێت. لەبری ئەوە یەک دراوسێ بە هەڕەمەکی هەڵدەبژێرێت و بڕیار دەدات بیکات بە ئێستا یان تر بپشکنێت.

A common rule: pick at random among the uphill neighbours. Because the choice is random, two runs from the same start can end on different tops. It usually climbs more slowly than steepest ascent, but in some landscapes it finds higher tops.

یاسایەکی باو: لە نێو ئەو دراوسێیانەی بەرەو سەرەوەن بە هەڕەمەکی یەکێک هەڵبژێرە. چونکە هەڵبژاردنەکە هەڕەمەکییە، دوو جار کارپێکردن لە هەمان سەرەتاوە دەکرێت لەسەر دوو لووتکەی جیاواز کۆتایی بێت. زۆربەی جار لە خاوتر سەردەکەوێت، بەڵام لە هەندێک دیمەندا دەگاتە لووتکەی بەرزتر.

The three types side by sideسێ جۆرەکە لە تەنیشت یەکەوە
TypeجۆرWhich neighbour does it take?کام دراوسێ وەردەگرێت؟Cost of one stepتێچووی یەک هەنگاو
Simpleسادەthe first better oneیەکەمی باشترlowکەم
Steepest ascentتیژthe best of all neighboursباشترینی هەموو دراوسێکانhigh: checks allزۆر: هەموویان دەپشکنێت
Stochasticهەڕەمەکیa random (uphill) oneیەکێکی هەڕەمەکی (بەرەو سەرەوە)lowکەم

Three types of hill climbingسێ جۆری چیاهەڵەگڕی

Hill climbing in Pythonچیاهەڵەگڕی بە Python

Let us run simple and steepest-ascent hill climbing on the landscape of the figure. The 24 values are in a : VALUES[13] is 16, the global maximum. The neighbours of a state are the states just left and right of it.

با و لەسەر دیمەنەکەی وێنەکە کار پێ بکەین. ⁦24⁩ بەهاکە لە : VALUES[13] بەهای ⁦16⁩ـە، . دراوسێکانی هەر ئەو کە ڕێک لای چەپ و ڕاستیەوەن.

Simple and steepest-ascent hill climbingچیاهەڵەگڕیی سادە و چیاهەڵەگڕیی تیژhill_climbing.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
# A tiny 1-D landscape: state number -> value (higher is better).
VALUES = [3, 5, 7, 9, 7, 5, 6, 8, 10, 10, 10, 12,
          14, 16, 13, 10, 8, 11, 11, 11, 11, 9, 6, 4]


def neighbours(state):
    """The states one step to the left and one step to the right."""
    return [s for s in (state - 1, state + 1) if 0 <= s < len(VALUES)]


def simple_hill_climbing(state):
    while True:
        moved = False
        for n in neighbours(state):          # look at ONE neighbour at a time
            if VALUES[n] > VALUES[state]:    # the first better one is taken
                state = n
                moved = True
                break
        if not moved:                        # no neighbour is better: stop
            return state


def steepest_ascent(state):
    while True:
        best = max(neighbours(state), key=lambda n: VALUES[n])  # look at ALL
        if VALUES[best] <= VALUES[state]:    # even the best one is not higher
            return state
        state = best


for start in [1, 6, 15, 18]:
    a = simple_hill_climbing(start)
    b = steepest_ascent(start)
    print(f"start {start:2} (value {VALUES[start]:2}):",
          f"simple stops at {a:2} (value {VALUES[a]:2}),",
          f"steepest stops at {b:2} (value {VALUES[b]:2})")
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 2-3

The landscape: the value of each state 0 to 23.

دیمەنەکە: بەهای هەر لە 0 تا ⁦23⁩.

Lineدێڕی 6-8

A neighbour must stay inside the list (0 to 23).

دراوسێ دەبێت لە ناو بمێنێتەوە (⁦0⁩ تا ⁦23⁩).

Lineدێڕی 11-20

Simple: the first better neighbour is taken at once (break). If none is better, moved stays False and we stop.

سادە: یەکەم دراوسێی باشتر دەستبەجێ وەردەگیرێت (break). ئەگەر هیچیان باشتر نەبوون، moved بە False دەمێنێتەوە و دەوەستین.

Lineدێڕی 23-28

Steepest ascent: max(..., key=...) finds the neighbour with the highest value. Equal is not better (<=), so it stops.

تیژ: max(..., key=...) ئەو دراوسێیە دەدۆزێتەوە کە بەرزترین بەهای هەیە. یەکسان باشتر نییە (<=)، بۆیە دەوەستێت.

Lineدێڕی 31-36

Run both versions from four start states.

هەردوو جۆرەکە لە چوار سەرەتاوە کار پێ بکە.

  • From state 1 both climb to state 3 and stop: a local maximum (9).
  • From state 6 both stop at state 8, the shoulder (10): the next state has the same value.
  • From state 15 both reach state 13, the global maximum (16), because the start is on its slope.
  • From state 18 neither can move: it is on a flat local maximum (11).
  • لە 1ەوە هەردووکیان بۆ 3 سەردەکەون و دەوەستن: ⁦(9)⁩.
  • لە 6ەوە هەردووکیان لە 8 دەوەستن، لەسەر ⁦(10)⁩: دواتر هەمان بەهای هەیە.
  • لە ⁦15⁩ەوە هەردووکیان دەگەنە ⁦13⁩، ⁦(16)⁩، چونکە سەرەتاکە لەسەر لێژایی ئەو لووتکەیەیە.
  • لە ⁦18⁩ەوە هیچیان ناتوانن بجووڵێن: لەسەر تەختە ⁦(11)⁩.
Quick checkپشکنینی خێراStarted at state 15, steepest ascent reaches the global maximum. Started at state 1, it does not. Why? لە ⁦15⁩ەوە دەگاتە ، بەڵام لە 1ەوە ناگات. بۆچی؟

Where hill climbing gets stuckچیاهەڵەگڕی لە کوێ دەچەقێت

Hill climbing stops as soon as no neighbour is better. That is fast, but it can stop in the wrong place. The notes describe three classic traps: a local maximum, a plateau and a ridge.

هەر کە هیچ دراوسێیەک باشتر نەبوو دەوەستێت. ئەمە خێرایە، بەڵام ڕەنگە لە شوێنی هەڵەدا بوەستێت. تێبینییەکان سێ داوی ناسراو باس دەکەن: ، و .

Where hill climbing gets stuckچیاهەڵەگڕی لە کوێ دەچەقێت

Problem 1: a local maximumکێشەی 1: لووتکەی ناوخۆیی

Definitionپێناسە

A state that is better than all its neighbours but is not the best state overall; hill climbing can get stuck there.

کە لە هەموو دراوسێکانی باشترە، بەڵام بە گشتی باشترین دۆخ نییە؛ دەکرێت لەوێدا بچەقێت.

A is a peak state in the landscape that is better than each of its neighbouring states, but there is another state that is higher. In the figure, state 3 (value 9) is a local maximum: hill climbing from states 0, 1, 2, 4 or 5 stops there.

لووتکەییە لە دیمەنەکەدا کە لە هەموو دراوسێی باشترە، بەڵام تر هەیە کە لێی بەرزترە. لە وێنەکەدا 3 (بەهای ⁦9⁩) : لە 0، 1، 2، 4 یان 5ەوە لەوێ دەوەستێت.

The notes suggest this solution: use backtracking. Make a list of the promising paths, so that the algorithm can go back in the search space and explore other paths as well.

تێبینییەکان ئەم چارەسەرە پێشنیار دەکەن: بەکار بهێنە. لیستێکی ئەو ڕێگایانە دروست بکە کە هیوابەخشن، تاکو ئەلگۆریزمەکە بتوانێت لە فەزای گەڕاندا بگەڕێتەوە دواوە و ڕێگاکانی تریش بپشکنێت.

Quick checkپشکنینی خێراWhich start state does not end at the local maximum 3 (with steepest ascent)?کام سەرەتا لە 3دا کۆتایی نایەت (بە )؟

Hill Climbing Algorithm & Artificial Intelligence - ComputerphileComputerphile · Englishئینگلیزی · 418K viewsبینین · 9.4K likesلایک · Partبەشی 0:00–6:43 (ofلە 7:20)

Rob Miles explains hill climbing as climbing a hill blindfolded, and why it can stop on a small local peak instead of the highest one.

⁦Rob Miles⁩ بە سەرکەوتن بە گردێکدا بە چاوی بەستراو دەچوێنێت، هەروەها ڕوون دەکاتەوە بۆچی دەکرێت لەسەر بوەستێت لە جیاتی .

Plays 0:00–6:43 and stops before the sponsor message. Uses evolution as an example of hill climbing.

لە ⁦0:00⁩ تا ⁦6:43⁩ لێدەدرێت و پێش ڕیکلامی سپۆنسەرەکە دەوەستێت. پەرەسەندنی زیندەوەران وەک نموونەیەکی بەکاردەهێنێت.

Where hill climbing gets stuckچیاهەڵەگڕی لە کوێ دەچەقێت

Problem 2: a plateauکێشەی 2: تەختایی

Definitionپێناسە

A flat area of the landscape where all the neighbours have the same value, so hill climbing finds no direction to move in; a flat local maximum is one kind.

ناوچەیەکی تەختی کە هەموو دراوسێکان هەمان نرخیان هەیە، بۆیە هیچ ئاڕاستەیەک بۆ جووڵان نادۆزێتەوە؛ لووتکەی ناوخۆیی تەخت یەکێکە لە جۆرەکانی.

A is a flat area of the search space: all the neighbours of the current state have the same value. So the algorithm cannot find a best direction to move, and hill climbing may get lost in the plateau. Our code stopped twice on a plateau: on the shoulder (state 8) and on the flat local maximum (state 18).

ناوچەیەکی تەختی فەزای گەڕانە: هەموو دراوسێکانی ئێستا هەمان بەهایان هەیە. بۆیە ئەلگۆریزمەکە ناتوانێت باشترین ئاڕاستە بۆ جووڵین بدۆزێتەوە و ڕەنگە لە ناو ون ببێت. کۆدەکەی ئێمە دوو جار لەسەر وەستا: لەسەر ( ⁦8⁩) و لەسەر تەخت ( ⁦18⁩).

The notes give this solution: take big steps or very small steps while searching, or randomly select a state that is far away from the current state, so that the algorithm may find a non-plateau region.

تێبینییەکان ئەم چارەسەرە دەدەن: لە کاتی گەڕاندا هەنگاوی گەورە یان هەنگاوی زۆر بچووک بنێ، یان بە هەڕەمەکی هەڵبژێرە کە لە ئێستا دوورە، تاکو ئەلگۆریزمەکە بتوانێت ناوچەیەکی ناتەخت بدۆزێتەوە.

Quick checkپشکنینی خێراHill climbing stands on a plateau. Why does it stop? لەسەر وەستاوە. بۆچی دەوەستێت؟

Where hill climbing gets stuckچیاهەڵەگڕی لە کوێ دەچەقێت

Problem 3: a ridgeکێشەی 3: پشتە

Definitionپێناسە

A narrow, high crest that rises gently in one direction; every single move in the allowed directions goes down, so hill climbing gets stuck although the top is higher.

لووتکەیەکی درێژ و تەسکە کە بە نەرمی بەرەو یەک ئاڕاستە بەرز دەبێتەوە؛ هەموو جووڵە تاکەکان لە ئاڕاستە ڕێگەپێدراوەکاندا بەرەو خوارەوە دەچن، بۆیە دەچەقێت هەرچەندە سەرەوە بەرزترە.

A is a special form of local maximum. It is an area that is higher than the land around it and that itself slopes upward, but the slope cannot be followed in a single move. Look at the ridge from above:

شێوەیەکی تایبەتی . ناوچەیەکە لە زەویی دەوروبەری بەرزترە و خۆشی بەرەو سەرەوە لێژە، بەڵام ناتوانرێت بە یەک جووڵە بەدوای ئەو لێژاییەدا بڕۆیت. لە سەرەوە سەیری بکە:

A 5 by 5 grid of heights seen from above. A ridge of green cells runs diagonally from the bottom left (5) to the top right (9): 5, 6, 7, 8, 9. The current state is the centre cell with height 7, drawn in blue. Four orange arrows show the allowed moves up, down, left and right; they lead to 6, 4, 5 and 5, all lower. A dashed green arrow shows the diagonal step to 8, which is higher but is not an allowed move. The text says hill climbing stops at 7 although the ridge still goes up.خشتەیەکی 5 لە 5 لە بەرزییەکان کە لە سەرەوە سەیر کراوە. پشتەیەک لە خانە سەوزەکان بە لاری لە خوارەوەی چەپەوە (5) بۆ سەرەوەی ڕاست (9) دەڕوات: 5، 6، 7، 8، 9. دۆخی ئێستا خانەی ناوەڕاستە بە بەرزیی 7 و بە شین کێشراوە. چوار تیری پرتەقاڵی جووڵە ڕێگەپێدراوەکان پیشان دەدەن (سەرەوە، خوارەوە، چەپ و ڕاست)؛ دەچنە 6، 4، 5 و 5 کە هەموویان نزمترن. تیرێکی سەوزی پچڕپچڕ هەنگاوە لارەکە بۆ 8 پیشان دەدات کە بەرزترە، بەڵام جووڵەیەکی ڕێگەپێدراو نییە. دەقەکە دەڵێت چیاهەڵەگڕی لە 7دا دەوەستێت، ئەگەرچی پشتەکە هێشتا بەرز دەبێتەوە.
On a ridge, every allowed move goes down, but the ridge itself still rises.لەسەر هەموو جووڵە ڕێگەپێدراوەکان بەرەو خوارەوە دەچن، بەڵام خۆی هێشتا بەرز دەبێتەوە.CêIT

The notes give this solution: use bidirectional search, or move in different directions.

تێبینییەکان ئەم چارەسەرە دەدەن: بەکار بهێنە، یان بە ئاڕاستەی جیاواز بجووڵێ.

Quick checkپشکنینی خێراIn the ridge figure, which change would let hill climbing continue from 7 to 8?لە وێنەی کام گۆڕانکاری ڕێگە دەدات لە 7ەوە بۆ 8 بەردەوام بێت؟

Getting unstuck: random restarts and moreڕزگاربوون لە چەقین: دەستپێکردنەوەی هەڕەمەکی و زیاتر

The standard cures do not remember paths. They add randomness. The simplest one is : run hill climbing many times, each time from a random start state, and keep the best top found. Sooner or later one start lies on the slope of the global maximum. So random restarts find the global maximum with a probability that approaches 1 as the number of restarts grows.

چارەسەرە باوەکان ڕێگاکان لە بیر ناگرن. هەڕەمەکی زیاد دەکەن. سادەترینیان : چەند جارێک کار پێ بکە، هەر جارە لە سەرەتای هەڕەمەکییەوە و باشترین لووتکەی دۆزراوە هەڵبگرە. زوو یان درەنگ سەرەتایەک لەسەر لێژایی دەکەوێت. بۆیە بە زیادبوونی ژمارەی دەستپێکردنەوەکان، دۆزینەوەی لە 1 نزیک دەبێتەوە.

Random-restart hill climbingچیاهەڵەگڕی بە دەستپێکردنەوەی هەڕەمەکیrandom_restart.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
import random

VALUES = [3, 5, 7, 9, 7, 5, 6, 8, 10, 10, 10, 12,
          14, 16, 13, 10, 8, 11, 11, 11, 11, 9, 6, 4]


def neighbours(state):
    return [s for s in (state - 1, state + 1) if 0 <= s < len(VALUES)]


def stochastic_hill_climbing(state):
    while True:
        better = [n for n in neighbours(state) if VALUES[n] > VALUES[state]]
        if not better:                  # no uphill neighbour: stop
            return state
        state = random.choice(better)   # pick ONE uphill neighbour at random


def random_restart(tries):
    best = None
    for _ in range(tries):
        start = random.randrange(len(VALUES))   # a new random start state
        top = stochastic_hill_climbing(start)
        print(f"  start {start:2} -> top {top:2} (value {VALUES[top]})")
        if best is None or VALUES[top] > VALUES[best]:
            best = top                          # remember the best top so far
    return best


random.seed(1)          # same random numbers every run (for the lesson)
best = random_restart(5)
print("best state found:", best, "with value", VALUES[best])
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 11-16

Stochastic hill climbing: collect the uphill neighbours and pick one with random.choice.

: دراوسێ سەرەوژوورەکان کۆ بکەرەوە و یەکێکیان بە random.choice هەڵبژێرە.

Lineدێڕی 19-27

Five climbs from random starts (random.randrange(24) gives 0 to 23). Keep the best top.

پێنج جار سەرکەوتن لە سەرەتای هەڕەمەکییەوە (random.randrange(24) ژمارەیەک لە 0 تا ⁦23⁩ دەدات). باشترین لووتکە هەڵبگرە.

Lineدێڕی 30

random.seed(1) makes the random numbers the same on every run, so you get the output shown here.

random.seed(1) لە هەموو کارپێکردنێکدا وەک یەکیان لێ دەکات، بۆیە هەمان وەردەگریت کە لێرە پیشان دراوە.

Two of the five climbs got stuck on the local maximum 3, one on the shoulder 8 and one on the flat top 20. One climb started at 15 and reached 13, so the best answer is the global maximum.

دوو لە پێنج سەرکەوتنەکە لەسەر 3 چەقین، یەکێکیان لەسەر 8 و یەکێکیان لەسەر لووتکە تەختەکەی ⁦20⁩. یەک سەرکەوتن لە ⁦15⁩ەوە دەستی پێکرد و گەیشتە ⁦13⁩، بۆیە باشترین وەڵام .

Quick checkپشکنینی خێراWhy does random-restart hill climbing find the global maximum more often than one climb?بۆچی زیاتر لە یەک جار سەرکەوتن دەدۆزێتەوە؟

Getting unstuck: random restarts and moreڕزگاربوون لە چەقین: دەستپێکردنەوەی هەڕەمەکی و زیاتر

Relatives of hill climbing, and a question from the notesخزمەکانی چیاهەڵەگڕی و پرسیارێک لە تێبینییەکان

Common mistakesهەڵە باوەکان

MistakeهەڵەWhat is trueڕاستییەکە
“Hill climbing always finds the best solution.”« هەمیشە دەدۆزێتەوە.»It finds a top near its start. That may be only a local maximum; the best solution is not guaranteed.لووتکەیەک لە نزیک سەرەتاکەی دەدۆزێتەوە. ڕەنگە تەنیا بێت؛ گەرەنتی نییە.
“The goal is to find local maxima.”«ئامانج دۆزینەوەی .»The goal is the global maximum (or global minimum). Local ones are traps.ئامانج (یان ). ناوخۆییەکان داون.
“A neighbour with the same value is better.”«دراوسێیەک بە هەمان بەها باشترە.»Equal is not better. Plain hill climbing stops on a plateau unless sideways moves are allowed.یەکسان باشتر نییە. سادە لەسەر دەوەستێت، مەگەر جووڵەی لاتەنیشت ڕێگەپێدراو بێت.
“Steepest ascent looks at future steps.”« سەیری هەنگاوەکانی داهاتوو دەکات.»It looks at all neighbours one step away, then takes the best one.سەیری هەموو دراوسێکان دەکات کە یەک هەنگاو دوورن، پاشان باشترینیان وەردەگرێت.
“Backtracking or bidirectional search fixes the traps.”« یان داوەکان چاک دەکات.»Hill climbing keeps no paths. Use random restarts, stochastic or sideways moves, more kinds of moves, or simulated annealing. هیچ ڕێگەیەک هەڵناگرێت. هەڕەمەکی، جووڵەی هەڕەمەکی یان لاتەنیشت، جۆری زیاتری جووڵە، یان بەکار بهێنە.
Using max for a cost function.بەکارهێنانی max بۆ کرداری کۆست.For a cost, lower is better: use min and stop when no neighbour is cheaper (exercise 2).بۆ کۆست، کەمتر باشترە: min بەکار بهێنە و کاتێک بوەستە کە هیچ دراوسێیەک هەرزانتر نەبێت (ڕاهێنانی ⁦2⁩).

Exercisesڕاهێنانەکان

ExerciseڕاهێنانTrace it by handبە دەست بەدوایدا بڕۆ

Use the VALUES list of the lesson. Run steepest-ascent hill climbing in your head from state 21, then from state 16. Where does it stop each time, and what kind of place is it?

VALUESی وانەکە بەکار بهێنە. لە مێشکی خۆتدا لە ⁦21⁩ەوە، پاشان لە ⁦16⁩ەوە کار پێ بکە. هەر جارێک لە کوێ دەوەستێت و ئەو شوێنە چ جۆرە شوێنێکە؟

Hintئاماژە

Write the two neighbours and their values at every step.

لە هەر هەنگاوێکدا دوو دراوسێکە و بەهاکانیان بنووسە.

Show answerوەڵامەکە پیشان بدە
  • From 21 (9): neighbours 20 (11) and 22 (6) → go to 20. At 20 the neighbours are 19 (11) and 21 (9): the best is equal, so it stops at 20, on the flat local maximum.
  • From 16 (8): neighbours 15 (10) and 17 (11) → go to 17. At 17 the neighbours are 16 (8) and 18 (11): it stops at 17, also on the flat local maximum, although the global maximum is only four states away.
  • لە ⁦21⁩ەوە ⁦(9)⁩: دراوسێکان ⁦20 (11)⁩ و ⁦22 (6)⁩ن ← دەچێتە ⁦20⁩. لە ⁦20⁩دا دراوسێکان ⁦19 (11)⁩ و ⁦21 (9)⁩ن: باشترینیان یەکسانە، بۆیە لە ⁦20⁩ دەوەستێت، لەسەر تەخت.
  • لە ⁦16⁩ەوە ⁦(8)⁩: دراوسێکان ⁦15 (10)⁩ و ⁦17 (11)⁩ن ← دەچێتە ⁦17⁩. لە ⁦17⁩دا دراوسێکان ⁦16 (8)⁩ و ⁦18 (11)⁩ن: لە ⁦17⁩ دەوەستێت، ئەمیش لەسەر تەخت، ئەگەرچی تەنیا چوار دوورە.
ExerciseڕاهێنانGo downhill for a costبۆ کۆست بەرەو خوارەوە بڕۆ

Change steepest_ascent so that it finds a minimum of a list of costs (lower is better). Test it on COSTS = [9, 7, 4, 6, 8, 5, 3, 2, 4, 7, 6, 1, 3, 8] from the states 0, 4, 9 and 13.

steepest_ascent بگۆڕە تاکو نزمترین خاڵی لیستێک لە کۆستەکان بدۆزێتەوە (کەمتر باشترە). لەسەر COSTS = [9, 7, 4, 6, 8, 5, 3, 2, 4, 7, 6, 1, 3, 8] لە 0، 4، 9 و ⁦13⁩ەوە تاقیی بکەرەوە.

Hintئاماژە

Two things change: max becomes min, and the stop test compares the other way.

دوو شت دەگۆڕێن: max دەبێتە min و تاقیکردنەوەی وەستان بە پێچەوانەوە بەراورد دەکات.

Show answerوەڵامەکە پیشان بدە
steepest_descent.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
# The same idea for a COST (lower is better): go downhill instead of uphill.
COSTS = [9, 7, 4, 6, 8, 5, 3, 2, 4, 7, 6, 1, 3, 8]


def neighbours(state):
    return [s for s in (state - 1, state + 1) if 0 <= s < len(COSTS)]


def steepest_descent(state):
    while True:
        best = min(neighbours(state), key=lambda n: COSTS[n])   # min, not max
        if COSTS[best] >= COSTS[state]:      # no neighbour is cheaper: stop
            return state
        state = best


for start in [0, 4, 9, 13]:
    end = steepest_descent(start)
    print(f"start {start:2} (cost {COSTS[start]}) -> stops at {end:2} "
          f"(cost {COSTS[end]})")
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 11

min picks the cheapest neighbour.

min هەرزانترین دراوسێ هەڵدەبژێرێت.

Lineدێڕی 12

Stop when the cheapest neighbour is not cheaper (>=).

بوەستە کاتێک هەرزانترین دراوسێ هەرزانتر نییە (>=).

Only the start 13 reaches the global minimum, state 11 (cost 1). The starts 4 and 9 stop in the local minimum 7 (cost 2), and the start 0 stops at state 2 (cost 4).

تەنیا سەرەتای ⁦13⁩ دەگاتە ، واتە ⁦11⁩ (کۆستی ⁦1⁩). سەرەتاکانی 4 و 9 لە 7دا دەوەستن (کۆستی ⁦2⁩) و سەرەتای 0 لە 2دا دەوەستێت (کۆستی ⁦4⁩).

ExerciseڕاهێنانAllow sideways movesڕێگە بە جووڵەی لاتەنیشت بدە

Write climb_with_sideways(state, max_sideways). It works like steepest ascent, but when the best neighbour has the same value it may move there, at most max_sideways times in a row, and never straight back to the state it just left. Compare 0 and 5 sideways moves from states 8 and 18.

climb_with_sideways(state, max_sideways) بنووسە. وەک کار دەکات، بەڵام کاتێک باشترین دراوسێ هەمان بەهای هەبوو دەتوانێت بچێتە ئەوێ، زۆرترین max_sideways جار لە دوای یەک و هەرگیز ڕاستەوخۆ ناگەڕێتەوە بۆ ئەو کە تازە بەجێی هێشتووە. 0 و 5 جووڵەی لاتەنیشت لە 8 و ⁦18⁩ەوە بەراورد بکە.

Hintئاماژە

Remember the previous state in a variable previous, and count the sideways moves.

پێشوو لە بە ناوی previous هەڵبگرە و جووڵە لاتەنیشتەکان بژمێرە.

Show answerوەڵامەکە پیشان بدە
sideways.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
VALUES = [3, 5, 7, 9, 7, 5, 6, 8, 10, 10, 10, 12,
          14, 16, 13, 10, 8, 11, 11, 11, 11, 9, 6, 4]


def neighbours(state):
    return [s for s in (state - 1, state + 1) if 0 <= s < len(VALUES)]


def climb_with_sideways(state, max_sideways):
    previous = None
    sideways = 0
    while True:
        best = max(neighbours(state), key=lambda n: VALUES[n])
        if VALUES[best] > VALUES[state]:            # uphill: always go
            previous, state = state, best
            sideways = 0
        elif VALUES[best] == VALUES[state] and sideways < max_sideways:
            flat = [n for n in neighbours(state)
                    if VALUES[n] == VALUES[state] and n != previous]
            if not flat:                            # only the way back is flat
                return state
            previous, state = state, flat[0]        # a sideways move
            sideways += 1
        else:
            return state


for start in [8, 18]:
    print(f"start {start}: no sideways -> {climb_with_sideways(start, 0)}, "
          f"up to 5 sideways -> {climb_with_sideways(start, 5)}")
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 14-16

Uphill is always taken, and the sideways counter starts again.

جووڵەی سەرەوژوور هەمیشە وەردەگیرێت و لاتەنیشت لە سەرەتاوە دەست پێدەکاتەوە.

Lineدێڕی 17-23

A sideways move: same value, not the state we came from, and still under the limit.

جووڵەی لاتەنیشت: هەمان بەها، نەک ئەو کە لێیەوە هاتین، هێشتا لە ژێر سنوورەکەدا.

From 8 the climber crosses the shoulder (8 → 9 → 10) and then climbs to the global maximum 13. From 18 it walks along the flat top to 17 and stops: a flat local maximum has no way up, so sideways moves cannot help there.

لە 8ەوە شاخەوانەکە دەبڕێت (⁦8⁩ ← 9 ← ⁦10⁩) و پاشان بۆ ⁦13⁩ سەردەکەوێت. لە ⁦18⁩ەوە بەسەر لووتکە تەختەکەدا دەڕوات بۆ ⁦17⁩ و دەوەستێت: تەخت ڕێگەی سەرکەوتنی نییە، بۆیە جووڵەی لاتەنیشت لەوێ یارمەتی نادات.

ExerciseڕاهێنانHill climbing for the salesmanچیاهەڵەگڕی بۆ فرۆشیارەکە

Five towns: Erbil, Duhok, Zakho, Akre and Soran. Describe hill climbing for the traveling salesman problem: what is a state, what is a neighbour, what is the value, and when does the algorithm stop?

پێنج شارۆچکە: هەولێر، دهۆک، زاخۆ، ئاکرێ و سۆران. بۆ وەسف بکە: چییە، دراوسێ چییە، بەها چییە و ئەلگۆریزمەکە کەی دەوەستێت؟

Show answerوەڵامەکە پیشان بدە
  • State: one complete round trip, for example Erbil → Duhok → Zakho → Akre → Soran → Erbil.
  • Neighbour: the same trip with two towns swapped (for example Zakho and Akre).
  • Value: the total distance of the trip. It is a cost, so lower is better (hill climbing goes “downhill”).
  • Stop: when no swap of two towns makes the trip shorter. The trip is then a local minimum, which may or may not be the shortest trip of all.
  • : گەشتێکی بازنەیی تەواو، بۆ نموونە هەولێر ← دهۆک ← زاخۆ ← ئاکرێ ← سۆران ← هەولێر.
  • دراوسێ: هەمان گەشت، بەڵام شوێنی دوو شارۆچکە گۆڕدراوە (بۆ نموونە زاخۆ و ئاکرێ).
  • بەها: کۆی ماوەی گەشتەکە. ئەمە کۆستە، بۆیە کەمتر باشترە ( «بەرەو خوارەوە» دەڕوات).
  • وەستان: کاتێک هیچ گۆڕینەوەیەکی دوو شارۆچکە گەشتەکە کورتتر ناکات. ئەو کاتە گەشتەکە ، کە لەوانەیە کورتترین گەشتی هەموویان بێت یان نەبێت.

Summary and reviewکورتە و پێداچوونەوە

  • Hill climbing is a algorithm for : it keeps one current state and moves to a better neighbour.
  • Features: generate and test, greedy, no backtracking.
  • The landscape: the goal is the global maximum (or minimum); local maxima, plateaus (shoulders, flat maxima) and ridges are traps.
  • Simple: the first better neighbour. Steepest ascent: the best neighbour. Stochastic: a random uphill neighbour.
  • Cures: random restarts, sideways moves, more kinds of moves, and simulated annealing — not backtracking or bidirectional search.
  • ئەلگۆریزمێکی بۆ : یەک ئێستا ڕادەگرێت و دەچێتە دراوسێیەکی باشتر.
  • تایبەتمەندییەکان: ، چاوچنۆکی، بێ .
  • دیمەنەکە: ئامانج (یان )؛ ، ( و لووتکە تەختەکان) و داون.
  • سادە: یەکەم دراوسێی باشتر. تیژ: باشترین دراوسێ. هەڕەمەکی: دراوسێیەکی هەڕەمەکیی سەرەوژوور.
  • چارەسەرەکان: هەڕەمەکی، جووڵەی لاتەنیشت، جۆری زیاتری جووڵە و — نەک یان .
Review questionsپرسیارەکانی پێداچوونەوە
Why is hill climbing called a greedy algorithm?بۆچی بە چیاهەڵەگڕی دەوترێت ئەلگۆریزمی چاوچنۆک؟

Because it always takes the move that looks best right now, without planning ahead.

چونکە هەمیشە ئەو جووڵەیە هەڵدەبژێرێت کە ئێستا باشترین دەردەکەوێت، بەبێ پلاندانان بۆ داهاتوو.

What is the difference between a shoulder and a flat local maximum?جیاوازیی نێوان شان و لووتکەی ناوخۆیی تەخت چییە؟

Both are flat. A shoulder has an uphill edge, so a way up exists; a flat local maximum has none.

هەردووکیان تەختن. لێوارێکی سەرەوژووری هەیە، بۆیە ڕێگەی سەرکەوتن هەیە؛ تەخت هیچی نییە.

Why does a ridge trap hill climbing?بۆچی پشتە چیاهەڵەگڕی دەخاتە داوەوە؟

The ridge rises in a direction that no single allowed move follows, so every allowed move goes down.

بەو ئاڕاستەیەدا بەرز دەبێتەوە کە هیچ جووڵەیەکی ڕێگەپێدراوی تاک بەدوایدا ناڕوات، بۆیە هەموو جووڵە ڕێگەپێدراوەکان بەرەو خوارەوە دەچن.

What is the time-for-quality trade between simple and steepest-ascent hill climbing?چیاهەڵەگڕیی سادە و چیاهەڵەگڕیی تیژ چۆن کات و باشی ئاڵوگۆڕ دەکەن؟

Simple checks fewer neighbours per step (faster steps, less optimal). Steepest checks all of them (slower steps, the best move each time).

سادە لە هەر هەنگاوێکدا دراوسێی کەمتر دەپشکنێت (هەنگاوی خێراتر، کەمتر باش). تیژ هەموویان دەپشکنێت (هەنگاوی خاوتر، هەر جارە باشترین جووڵە).

How can random restarts make hill climbing complete?چۆن دەستپێکردنەوەی هەڕەمەکی چیاهەڵەگڕی تەواو دەکات؟

With enough random starts, one of them will lie on the slope of the global maximum, so the chance of finding it approaches 1.

ئەگەر ژمارەی سەرەتا هەڕەمەکییەکان بەس بێت، یەکێکیان لەسەر لێژایی دەبێت، بۆیە دۆزینەوەی لە 1 نزیک دەبێتەوە.

Further reading given in the course notes: Analytics Vidhya: Hill climbing algorithm in AI.

خوێندنەوەی زیاتر کە لە تێبینییەکانی کۆرسەکەدا دراوە: ⁦Analytics Vidhya: Hill climbing algorithm in AI⁩.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Harvard CS50’s Artificial Intelligence with Python – Full University CoursefreeCodeCamp.org · Englishئینگلیزی · 5.1M viewsبینین · 134K likesلایک · Partبەشی 5:41:32–6:03:51 (ofلە 11:51:22)

Harvard's CS50 AI lecturer explains each idea with clear pictures and Python code; each placement plays only the chapter that matches its screen.

مامۆستای کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard هەر بیرۆکەیەک بە وێنەی ئاشکرا و کۆدی ڕوون دەکاتەوە؛ لە هەر شوێنێک تەنها ئەو بەشەی لێدەدرێت کە لەگەڵ ئەو شاشەیە دەگونجێت.

Plays 5:41:32–6:03:51: hill climbing step by step, local maxima and minima, flat areas, the variants (steepest-ascent, stochastic, first-choice, random-restart, local beam) and a Python demo (hospitals.py).

لە ⁦5:41:32⁩ تا ⁦6:03:51⁩ لێدەدرێت: هەنگاو بە هەنگاو، و ، ، جۆرەکانی (، ، first-choice، ، ) و نموونەیەکی (hospitals.py).

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Simulated Annealingsimulated annealing

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.