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

Chapterبەش 4 · Lectureوانە 4.5

Heuristics and Greedy Best-First Searchپێوەرەکان و گەڕانی چاوچنۆکانە

How a heuristic h(n) guides a search towards the goal: informed search, the OPEN and CLOSED lists, greedy best-first search with f(n) = h(n), a fully worked example, its complexity and limits, Manhattan distance, and the Lab 3 maze program in Python.

چۆن ⁦h(n)⁩ گەڕان بەرەو ئامانج ڕێنمایی دەکات: ، لیستەکانی OPEN و CLOSED، بە ⁦f(n) = h(n)⁩، نموونەیەکی تەواو شیکراوە، ئاڵۆزی و سنوورەکانی، و تاقیگەی 3 بە .

27 min read27 خولەک خوێندنەوە · 21 stepsهەنگاو

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

  • Explain informed search and the heuristic function h(n), with the rules h(n) ≥ 0 and h(goal) = 0.
  • Run greedy best-first search by hand with the OPEN and CLOSED lists.
  • State its time and space complexity, and explain why it is not optimal and not complete in general.
  • Compute the Manhattan distance between two cells of a grid.
  • Read, run and correct the Lab 3 greedy program in Python.
  • و ⁦h(n)⁩ ڕوون بکەیتەوە، لەگەڵ یاساکانی ⁦h(n) ≥ 0⁩ و ⁦h(goal) = 0⁩.
  • بە دەست جێبەجێ بکەیت بە لیستەکانی OPEN و CLOSED.
  • و بڵێیت و ڕوونی بکەیتەوە بۆچی باشترین نییە و بە گشتی تەواو نییە.
  • لە نێوان دوو خانەی تۆڕێکدا حیساب بکەیت.
  • تاقیگەی 3 بە بخوێنیتەوە، جێبەجێی بکەیت و ڕاستی بکەیتەوە.

Heuristics: a good guessپێوەرەکان: مەزەندەیەکی باش

A heuristic method is a rule of thumb. It often finds a good solution quickly, but it gives no guarantee: sometimes the solution is not the best one, and sometimes it is slow.

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

Definitionپێناسە

The function h(n) that gives, for every node n, the estimated cost of reaching a goal from it.

ئەو کردارەیە کە بە ⁦h(n)⁩ دەنووسرێت و بۆ هەر نۆدێکی n کۆستی خەمڵێنراوی گەیشتن لەو نۆدەوە بۆ ئامانج دەدات.

The heuristic function is written h(n). For a node n, it estimates the cost of the cheapest path from n to a goal. It does not calculate the real cost: if we could calculate the real cost, we would not need to search at all. A small h(n) means "this node looks close to the goal".

بە ⁦h(n)⁩ دەنووسرێت. بۆ n، کۆستی هەرزانترین لە nـەوە تا ئامانج دەخەمڵێنێت. کۆستی ڕاستەقینە حیساب ناکات: ئەگەر بمانتوانیایە کۆستی ڕاستەقینە حیساب بکەین، هیچ پێویستمان بە گەڕان نەدەبوو. ⁦h(n)⁩ـی بچووک واتە «ئەم نزیکی ئامانج دیار دەدات».

  • h(n) is never negative: h(n) ≥ 0.
  • At a goal it is zero: h(goal) = 0.
  • It is an estimate, so it can be wrong. A better estimate makes the search faster.
  • ⁦h(n)⁩ هەرگیز سالب نییە: ⁦h(n) ≥ 0⁩.
  • لە ئامانجدا سفرە: ⁦h(goal) = 0⁩.
  • مەزەندەیە، بۆیە دەشێت هەڵە بێت. مەزەندەی باشتر گەڕانەکە خێراتر دەکات.
Quick checkپشکنینی خێراWhich statement about h(n) is correct?کام ڕستە دەربارەی ⁦h(n)⁩ ڕاستە؟

Heuristics: a good guessپێوەرەکان: مەزەندەیەکی باش

Example: a heuristic for the 8-puzzleنموونە: پێوەرێک بۆ یاریی 8-پارچە

The 8-puzzle is a 3 × 3 board with eight numbered tiles and one empty square. A move slides a tile next to the empty square into it. The goal in the course notes is the arrangement 1 2 3 / 8 _ 4 / 7 6 5. A simple heuristic is h(n) = the number of tiles that are not in their goal square (the empty square is not counted).

یاریی 8-پارچە تەختەیەکی ⁦3 × 3⁩ـە کە هەشت پارچەی ژمارەدار و یەک خانەی بەتاڵی تێدایە. هەر جووڵەیەک پارچەیەکی تەنیشت خانە بەتاڵەکە دەخزێنێتە ناوی. ئامانج لە تێبینییەکانی کۆرسەکەدا ئەم ڕیزبەندییەیە: 1 2 3 / 8 _ 4 / 7 6 5. سادە ئەمەیە: ⁦h(n)⁩ = ژمارەی ئەو پارچانەی لە شوێنی ئامانجی خۆیان نین (خانە بەتاڵەکە ناژمێردرێت).

A search tree for the 8-puzzle. The start board 1 2 3 / 8 6 _ / 7 5 4 has h = 3 (tiles 6, 5 and 4 are misplaced). Its three children are: tile 6 slides right, h = 3; tile 4 slides up, h = 2 (chosen); tile 3 slides down, h = 4. From the h = 2 board: tile 5 slides right, h = 1 (chosen), or tile 4 slides down, which is the start board again, h = 3. From the h = 1 board, tile 6 slides down and gives the goal board 1 2 3 / 8 _ 4 / 7 6 5 with h = 0. Misplaced tiles are drawn in orange.دارێکی گەڕان بۆ یاریی 8-پارچە. تەختەی سەرەتا 1 2 3 / 8 6 _ / 7 5 4 بە h = 3 (پارچەکانی 6، 5 و 4 لە شوێنی خۆیان نین). سێ منداڵی هەیە: پارچەی 6 بۆ ڕاست دەخزێت، h = 3؛ پارچەی 4 بۆ سەرەوە دەخزێت، h = 2 (هەڵبژێردراو)؛ پارچەی 3 بۆ خوارەوە دەخزێت، h = 4. لە تەختەی h = 2ـەوە: پارچەی 5 بۆ ڕاست، h = 1 (هەڵبژێردراو)، یان پارچەی 4 بۆ خوارەوە کە دووبارە تەختەی سەرەتایە، h = 3. لە تەختەی h = 1ـەوە پارچەی 6 بۆ خوارەوە دەخزێت و تەختەی ئامانج 1 2 3 / 8 _ 4 / 7 6 5 بە h = 0 دەدات. پارچە شوێنهەڵەکان بە پرتەقاڵی کێشراون.
Always take the board with the smallest h: 3 → 2 → 1 → 0.هەمیشە ئەو تەختەیە وەربگرە کە بچووکترین hـی هەیە: 3 ← 2 ← 1 ← 0.CêIT

Read the tree from the top. From each board, look at the children and take the one with the smallest h: first 4 ↑ (h = 2), then 5 → (h = 1), then 6 ↓ (h = 0, the goal). Three moves solve this puzzle. Choosing the child that looks closest to the goal is exactly the idea of greedy best-first search.

لە سەرەوە بخوێنەوە. لە هەر تەختەیەکەوە سەیری منداڵەکانی بکە و ئەوەیان وەربگرە کە بچووکترین hـی هەیە: یەکەم 4 ↑ ⁦(h = 2)⁩، پاشان 5 → ⁦(h = 1)⁩، پاشان 6 ↓ (⁦h = 0⁩، ئامانج). سێ جووڵە ئەم یارییە چارەسەر دەکات. هەڵبژاردنی ئەو منداڵەی کە لە ئامانجەوە نزیکتر دیار دەدات ڕێک بیرۆکەی .

Quick checkپشکنینی خێراBoard 1 2 3 / 8 6 4 / 7 _ 5 and the goal 1 2 3 / 8 _ 4 / 7 6 5. How many tiles are misplaced?تەختەی 1 2 3 / 8 6 4 / 7 _ 5 و ئامانجی 1 2 3 / 8 _ 4 / 7 6 5. چەند پارچە لە شوێنی خۆیان نین؟

Greedy best-first search: the ideaگەڕانی چاوچنۆکانە: بیرۆکەکە

Greedy best-first search (the notes also call it best-first search or greedy search) uses the heuristic function to search. At every step it takes the path that looks best at that moment: the most promising node, which means the node with the lowest heuristic value.

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

Its evaluation function is only the heuristic: f(n) = h(n), where h(n) is the estimated cost from node n to the goal (the distance from the current node to the goal). The node closest to the goal, as the heuristic sees it, is expanded first.

تەنیا : ⁦f(n) = h(n)⁩، کە ⁦h(n)⁩ کۆستی خەمڵێنراوە لە nـەوە تا ئامانج (دووریی ئێستا تا ئامانج). ئەو بە بۆچوونی لە ئامانجەوە نزیکترینە، یەکەمجار فراوان دەکرێت.

The OPEN list is kept in a priority queue ordered by h(n), usually a min-heap, so the node with the smallest h comes out first (heaps and priority queues).

لیستی OPEN لە ڕادەگیرێت کە بە پێی ⁦h(n)⁩ ڕیز کراوە، زۆرجار ، بۆ ئەوەی ئەو بچووکترین hـی هەیە یەکەمجار دەربچێت (هیپەکان و کیووە پێشینەییەکان).

Walking to the citadelڕۆیشتن بەرەو قەڵا

In an old city you want to reach the citadel, which you can see above the roofs. At every corner you take the alley that points most directly at the citadel. You never think about how far you have already walked. That is greedy: only "how close does it look now?" counts.

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

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

An alley that points at the citadel can be a dead end. Then you go back to another alley you remember (OPEN). The way you finally take can be longer than necessary.

کۆڵانێک کە ڕووی لە قەڵایە دەشێت بنبەست بێت. ئەوکات دەگەڕێیتەوە بۆ کۆڵانێکی تر کە لە بیرتە ⁦(OPEN)⁩. ئەو ڕێگایەی لە کۆتاییدا دەیگریت دەشێت درێژتر بێت لەوەی پێویستە.

Quick checkپشکنینی خێراWhat does greedy best-first search use to choose the next node? چی بەکار دەهێنێت بۆ هەڵبژاردنی داهاتوو؟

The algorithm step by stepئەلگۆریزمەکە هەنگاو بە هەنگاو

Greedy best-first search (the course's seven steps)گەڕانی چاوچنۆکانە (حەوت هەنگاوەکەی کۆرسەکە)

  1. Put the start node in OPEN.

    سەرەتا بخە ناو OPEN.

  2. If OPEN is empty, stop and return failure: there is no path.

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

  3. Remove the node n with the lowest h(n) from OPEN and put it in CLOSED.

    لە OPEN ئەو دەربهێنە کە کەمترین ⁦h(n)⁩ـی هەیە (با ناوی بنێین n) و بیخە ناو CLOSED.

  4. Expand n: generate its successors.

    n فراوان بکە: منداڵەکانی دروست بکە.

  5. Check each successor: if one of them is a goal, return success and stop. Otherwise go on to step 6.

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

  6. For each successor, compute f(n) = h(n) and check whether it is already in OPEN or CLOSED. If it is in neither list, add it to OPEN.

    بۆ هەر منداڵێک ⁦f(n) = h(n)⁩ حیساب بکە و بپشکنە ئایا پێشتر لە OPEN یان CLOSED هەیە. ئەگەر لە هیچیان نەبوو، زیادی بکە بۆ OPEN.

  7. Go back to step 2.

    بگەڕێوە بۆ هەنگاوی 2.

Quick checkپشکنینی خێراA successor is already in CLOSED. What does step 6 do with it?منداڵێک پێشتر لە CLOSED هەیە. هەنگاوی 6 چی لێ دەکات؟

A worked exampleنموونەیەکی شیکراوە

Let's traverse the graph below with greedy best-first search, from S to the goal G. At every round the node with the smallest f(n) = h(n) is expanded. The h values are in the table; the numbers on the arrows are step costs, which greedy search does not use.

با بە بە ناو ئەم خوارەوەدا بڕۆین، لە Sـەوە بۆ ئامانجی G. لە هەر خولێکدا ئەو بچووکترین ⁦f(n) = h(n)⁩ـی هەیە فراوان دەکرێت. نرخەکانی h لە خشتەکەدان؛ ژمارەکانی سەر تیرەکان کە بەکاریان ناهێنێت.

A tree-shaped graph. S has children A (step cost 3) and B (2). A has children C (4) and D (1). B has children E (3) and F (1). E has child H (5). F has children I (2) and G (3). The h values are S 13, A 12, B 4, C 7, D 3, E 8, F 2, H 4, I 9, G 0. The path S → B → F → G is highlighted.گرافێک بە شێوەی دار. S منداڵەکانی A (کۆستی هەنگاو 3) و B (2)ی هەیە. A منداڵەکانی C (4) و D (1). B منداڵەکانی E (3) و F (1). E منداڵی H (5). F منداڵەکانی I (2) و G (3). نرخەکانی h: S 13، A 12، B 4، C 7، D 3، E 8، F 2، H 4، I 9، G 0. ڕێگای S → B → F → G دیار کراوە.
The graph of the worked example, redrawn from the h table of the notes. نموونە شیکراوەکە، لە خشتەی hـی تێبینییەکانەوە سەرلەنوێ کێشراوەتەوە.CêIT
The heuristic values from the notesنرخەکانی لە تێبینییەکانەوە
NodeSABCDEFHIG
h(n)131247382490

A worked exampleنموونەیەکی شیکراوە

The trace, round by roundشوێنکەوتنی گەڕانەکە، خول بە خول

OPEN is shown smallest h first, as a priority queue keeps it.OPEN بە ڕیزبەندیی بچووکترین h نیشان دراوە، وەک ڕایدەگرێت.
RoundخولNode taken out دەرهێنراوOPEN after the round (h)OPEN دوای خولەکە ⁦(h)⁩CLOSEDلیستی CLOSEDWhyبۆچی
StartسەرەتاSB (4), A (12)SS is expanded first; its children A and B join OPEN.S یەکەمجار فراوان دەکرێت؛ منداڵەکانی A و B دەچنە ناو OPEN.
1BF (2), E (8), A (12)S, Bh(B) = 4 is smaller than h(A) = 12. B's children E and F join OPEN.⁦h(B) = 4⁩ لە ⁦h(A) = 12⁩ بچووکترە. منداڵەکانی B واتە E و F دەچنە ناو OPEN.
2FG (0), E (8), I (9), A (12)S, B, Fh(F) = 2 is the smallest. F's children I and G join OPEN.⁦h(F) = 2⁩ بچووکترینە. منداڵەکانی F واتە I و G دەچنە ناو OPEN.
3GE (8), I (9), A (12)S, B, F, Gh(G) = 0: G is the goal, so the search stops.⁦h(G) = 0: G⁩ ئامانجە، بۆیە گەڕانەکە دەوەستێت.

Following the parents back from G gives the solution: S → B → F → G.

بە شوێنکەوتنی باوکەکان لە Gـەوە بەرەو دواوە چارەسەرەکە دەردەکەوێت: S → B → F → G.

Now add up the step costs of the path: 2 + 1 + 3 = 6. Greedy search never looked at these numbers; it used only h. Here 6 happens to be the cheapest way to G, but greedy could not know that.

ئێستا ڕێگاکە کۆ بکەرەوە: ⁦2 + 1 + 3⁩ = 6. هەرگیز سەیری ئەم ژمارانەی نەکرد؛ تەنیا hـی بەکار هێنا. لێرەدا 6 بە ڕێکەوت هەرزانترین ڕێگایە بۆ G، بەڵام نەیدەتوانی ئەوە بزانێت.

Quick checkپشکنینی خێراIn round 2, why is F taken out of OPEN and not E?لە خولی 2دا بۆچی F لە OPEN دەردەهێنرێت نەک E؟

A worked exampleنموونەیەکی شیکراوە

The same example in Pythonهەمان نموونە بە Python

This short program runs greedy best-first search on the same graph. OPEN is a heap of (h, node) tuples, so heapq.heappop() always returns the node with the smallest h. The parent dictionary remembers every node that was ever put in OPEN, so it also answers "is it in OPEN or CLOSED already?".

ئەم کورتە لەسەر هەمان جێبەجێ دەکات. OPEN لە (h, node)، بۆیە heapq.heappop() هەمیشە ئەو دەگەڕێنێتەوە کە بچووکترین hـی هەیە. parent هەموو ئەو لە بیر دەگرێت کە هەرگیز خراونەتە ناو OPEN، بۆیە وەڵامی «ئایا پێشتر لە OPEN یان CLOSED هەیە؟»ـیش دەداتەوە.

greedy_graph.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
import heapq

# The graph of the worked example: node -> list of (child, step cost)
graph = {
    "S": [("A", 3), ("B", 2)],
    "A": [("C", 4), ("D", 1)],
    "B": [("E", 3), ("F", 1)],
    "E": [("H", 5)],
    "F": [("I", 2), ("G", 3)],
}
# h(n): the estimated distance from each node to the goal G
h = {"S": 13, "A": 12, "B": 4, "C": 7, "D": 3,
     "E": 8, "F": 2, "H": 4, "I": 9, "G": 0}


def greedy_best_first(graph, h, start, goal):
    open_list = [(h[start], start)]   # OPEN = frontier, ordered by h(n) only
    closed = []                       # CLOSED = explored set
    parent = {start: None}            # every node ever put in OPEN
    while open_list:
        _, node = heapq.heappop(open_list)       # smallest h(n) first
        if node == goal:
            path = []
            while node is not None:              # follow the parents back
                path.append(node)
                node = parent[node]
            return path[::-1]
        closed.append(node)
        for child, _ in graph.get(node, []):     # the step cost is ignored
            if child not in parent:              # not in OPEN or CLOSED yet
                parent[child] = node
                heapq.heappush(open_list, (h[child], child))
        print("Expand", node, "-> OPEN:", sorted(open_list), " CLOSED:", closed)
    return None


path = greedy_best_first(graph, h, "S", "G")
print("Path:", " -> ".join(path))
cost = sum(dict(graph[a])[b] for a, b in zip(path, path[1:]))
print("Path cost:", cost)
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 4-10

The graph as a dictionary: each node maps to a list of (child, step cost) pairs. Nodes without children (C, D, G, H, I) are simply missing.

وەک : هەر بۆ لیستێک لە جووتەکانی (منداڵ، ). ئەو منداڵیان نییە (C، D، G، H، I) بە سادەیی نین.

Lineدێڕی 11-13

The h table of the notes.

خشتەی hـی تێبینییەکان.

Lineدێڕی 17-19

OPEN starts with the start node; CLOSED is empty; parent[start] = None marks the start.

OPEN بە سەرەتا دەست پێدەکات؛ CLOSED بەتاڵە؛ parent[start] = None سەرەتا دیاری دەکات.

Lineدێڕی 21-27

The smallest h comes out. If it is the goal, follow the parents back and reverse the list.

بچووکترین h دەردەچێت. ئەگەر ئامانج بوو، بە شوێن باوکەکاندا بگەڕێوە و لیستەکە پێچەوانە بکەرەوە.

Lineدێڕی 29-32

Expand: the step cost is read but ignored (_). A child is added only if it was never seen.

: دەخوێنرێتەوە بەڵام پشتگوێ دەخرێت (_). منداڵ تەنیا زیاد دەکرێت ئەگەر هەرگیز نەبینرابێت.

Lineدێڕی 39-40

Only at the end do we add up the step costs of the path, to see what it costs.

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

How good is greedy best-first search?گەڕانی چاوچنۆکانە چەند باشە؟

PropertyتایبەتمەندیGreedy best-first search
Time complexityO(b^m) in the worst case⁦O(b⁩^m) لە خراپترین حاڵەتدا
Space complexityO(b^m) in the worst case: it keeps every generated node⁦O(b⁩^m) لە خراپترین حاڵەتدا: هەموو هەڵدەگرێت
Complete?تەواوە؟No: it can get lost or loop (see the note below)نەخێر: دەشێت ون بێت یان بسووڕێتەوە (تێبینییەکەی خوارەوە ببینە)
Optimal?باشترینە؟No: the path it finds can be longer than the shortest oneنەخێر: ئەو ڕێگایەی دەیدۆزێتەوە دەشێت لە درێژتر بێت

Here b is the branching factor, the average number of children of a node (in a maze where you can move left, right, up and down, b = 4), and m is the maximum depth, the deepest level of the search space. These letters are explained in search problems. With a good heuristic the real cost is usually far smaller than O(b^m).

لێرەدا b بریتییە لە ، تێکڕای ژمارەی منداڵەکانی (لە کە بتوانیت بۆ چەپ، ڕاست، سەرەوە و خوارەوە بجووڵێیت، ⁦b = 4⁩) و m بریتییە لە ، قووڵترین ئاستی . ئەم پیتانە لە کێشەکانی گەڕان ڕوون کراونەتەوە. بە باش، تێچووی ڕاستەقینە زۆرجار زۆر لە ⁦O(b⁩^m) کەمترە.

How good is greedy best-first search?گەڕانی چاوچنۆکانە چەند باشە؟

Why O(b^m) grows so fastبۆچی ⁦O(b⁩^m) ئەوەندە خێرا گەورە دەبێت

Imagine a search space where every node has b = 3 children and the deepest level is m = 4. In the worst case greedy search generates every level:

یەک بهێنە پێش چاو کە تێیدا هەر ⁦b = 3⁩ منداڵی هەیە و قووڵترین ئاست ⁦m = 4⁩ـە. لە خراپترین حاڵەتدا هەموو ئاستەکان دروست دەکات:

LevelئاستNodesSum so farکۆی تا ئێستا
133
23 × 3 = 912
33 × 3 × 3 = 2739
43 × 3 × 3 × 3 = 81120

That is 120 nodes (121 with the root). Make b or m a little bigger and the number explodes: this is what O(b^m) means. The same example shows the memory problem: greedy search keeps all generated nodes, because it may have to go back to one of them if a path leads nowhere. At depth 4 alone 81 nodes must be stored, together with the ones already explored.

ئەمە ⁦120⁩ (⁦121⁩ لەگەڵ ڕەگەکە). b یان m کەمێک گەورەتر بکە و ژمارەکە دەتەقێتەوە: ئەمە واتای ⁦O(b⁩^m)ـە. هەمان نموونە کێشەی نیشان دەدات: هەموو هەڵدەگرێت، چونکە لەوانەیە ناچار بێت بگەڕێتەوە بۆ یەکێکیان ئەگەر ڕێگایەک بە هیچ شوێنێک نەگات. تەنیا لە قووڵایی 4دا دەبێت ⁦81⁩ هەڵبگیرێن، لەگەڵ ئەوانەی پێشتر پشکنراون.

Why is it not complete? It can be pulled into areas that do not lead to the goal, or go round in loops, when the heuristic misguides it. Why is it not optimal? It chooses paths that look promising at first, and they can end up longer than another path.

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

Quick checkپشکنینی خێراWith b = 4 (a maze with four directions) and m = 3, how many nodes are on levels 1 to 3 in the worst case?بە ⁦b = 4⁩ ( بە چوار ئاڕاستە) و ⁦m = 3⁩، لە خراپترین حاڵەتدا چەند لە ئاستەکانی 1 تا 3دان؟

Manhattan distance: a heuristic for gridsدووریی مانهاتن: پێوەرێک بۆ تۆڕی خانەکان

Imagine a city where the streets form a grid. You can walk only along the streets, up, down, left or right; there are no diagonal shortcuts through the buildings. The walking distance in such a city is called Manhattan distance, after the grid of streets in Manhattan, New York.

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

A street grid with rows 0 to 8 down the side and columns 0 to 5 across the top. The current point is at row 3, column 4; the end point is at row 7, column 1. One route goes 4 rows down and then 3 columns left; another goes 3 columns left and then 4 rows down. Both are 7 blocks long. A dotted diagonal line through the blocks is crossed out. The panel says: Manhattan distance = rows apart + columns apart = |3 − 7| + |4 − 1| = 4 + 3 = 7.تۆڕێکی شەقام بە ڕیزەکانی 0 تا 8 لە لای چەپ و ستوونەکانی 0 تا 5 لە سەرەوە. خاڵی ئێستا لە ڕیزی 3، ستوونی 4ـە؛ خاڵی ئامانج لە ڕیزی 7، ستوونی 1ـە. ڕێگایەک 4 ڕیز بەرەو خوارەوە و پاشان 3 ستوون بەرەو چەپ دەڕوات؛ یەکێکی تر 3 ستوون بەرەو چەپ و پاشان 4 ڕیز بەرەو خوارەوە. هەردووکیان 7 بلۆکن. هێڵێکی لاری خاڵخاڵ بە ناو بلۆکەکاندا خەتی بەسەردا هێنراوە. تابلۆکە دەڵێت: دووریی مانهاتن = جیاوازیی ڕیزەکان + جیاوازیی ستوونەکان = |3 − 7| + |4 − 1| = 4 + 3 = 7.
Every shortest walk along the streets has the same length: 4 + 3 = 7.هەموو کورتترین ڕۆیشتنێک بە شەقامەکاندا هەمان درێژیی هەیە: ⁦4 + 3 = 7⁩.CêIT
How to compute itچۆن حیسابی دەکەیت

  1. Take the difference in rows (how many rows apart the two cells are).

    جیاوازیی ڕیزەکان وەربگرە (دوو خانەکە چەند ڕیز لێک دوورن).

  2. Take the difference in columns.

    جیاوازیی ستوونەکان وەربگرە.

  3. Use the absolute value of each difference (abs()), so that no distance is negative.

    بەهای ڕەهای هەر جیاوازییەک بەکار بهێنە (abs())، بۆ ئەوەی هیچ دوورییەک سالب نەبێت.

  4. Add the two numbers.

    دوو ژمارەکە کۆ بکەرەوە.

manhattan_example.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
class Point:
    def __init__(self, x, y):
        self.x = x  # row
        self.y = y  # column


def manhattan(current, end):
    return abs(current.x - end.x) + abs(current.y - end.y)


current = Point(3, 4)
end = Point(7, 1)
print("rows apart:   ", abs(current.x - end.x))
print("columns apart:", abs(current.y - end.y))
print("Manhattan distance:", manhattan(current, end))
print("from (6, 0) to (0, 11):", manhattan(Point(6, 0), Point(0, 11)))
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 1-4

A point stores its row x and its column y, as in all the labs.

خاڵێک ڕیزەکەی x و ستوونەکەی y هەڵدەگرێت، وەک لە هەموو تاقیگەکاندا.

Lineدێڕی 7-8

The whole heuristic is one line.

هەموو یەک دێڕە.

Why is it useful? In a maze or a grid puzzle you can also move only along the grid, so Manhattan distance is a natural estimate of how far a cell is from the goal. It ignores the walls, so it never says the goal is farther than it really is. Greedy best-first search uses it in Lab 3, and A* uses it in Lab 4.

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

Quick checkپشکنینی خێراWhat is the Manhattan distance from (2, 9) to (0, 11)? لە ⁦(2, 9)⁩ـەوە بۆ ⁦(0, 11)⁩ چەندە؟

Lab 3: greedy best-first search on a mazeتاقیگەی 3: گەڕانی چاوچنۆکانە لەسەر لابیرینتێک

Lab 3 uses a maze of 7 rows and 12 columns. . is an open cell and # is a wall. The start is (6, 0), bottom left, and the end is (0, 11), top right. The heuristic is the Manhattan distance to the end.

تاقیگەی 3 7 ڕیز و ⁦12⁩ ستوون بەکار دەهێنێت. . خانەیەکی کراوەیە و # دیوارە. سەرەتا ⁦(6, 0)⁩ـە، خوارەوەی چەپ و کۆتایی ⁦(0, 11)⁩ـە، سەرەوەی ڕاست. تا کۆتایی.

The program needs three tools from earlier lessons: a priority queue built with heapq (heaps and priority queues), a parent dictionary to rebuild the path, and a grid of True/False values (the maze solver).

پێویستی بە سێ ئامراز هەیە لە وانەکانی پێشووەوە: کە بە heapq دروست کراوە (هیپەکان و کیووە پێشینەییەکان)، بە ناوی parent بۆ دووبارە دروستکردنەوەی ڕێگاکە و تۆڕێک لە نرخەکانی True/False (چارەسەرکەری لابیرینت).

The Lab 3 maze, 7 rows by 12 columns, with walls drawn dark. The 24 cells of the path found by greedy best-first search are highlighted: from A at (6, 0) right to (6, 3), up to (4, 3), right to (4, 4), up to (1, 4), right to (1, 6), down to (2, 6), right to (2, 8), down to (4, 8), right to (4, 11) and up to B at (0, 11). Four more cells, (0, 4), (0, 8), (0, 9) and (1, 8), were expanded but are not on the path.لابیرینتی تاقیگەی 3، 7 ڕیز بە 12 ستوون، دیوارەکان تاریک کێشراون. 24 خانەی ئەو ڕێگەیەی گەڕانی چاوچنۆکانە دۆزیویەتییەوە دیار کراون: لە A لە (6, 0) بۆ ڕاست تا (6, 3)، بۆ سەرەوە تا (4, 3)، بۆ ڕاست تا (4, 4)، بۆ سەرەوە تا (1, 4)، بۆ ڕاست تا (1, 6)، بۆ خوارەوە تا (2, 6)، بۆ ڕاست تا (2, 8)، بۆ خوارەوە تا (4, 8)، بۆ ڕاست تا (4, 11) و بۆ سەرەوە تا B لە (0, 11). چوار خانەی تر، (0, 4)، (0, 8)، (0, 9) و (1, 8)، فراوان کران بەڵام لەسەر ڕێگاکە نین.
The result of the program: 24 cells on the path, and only 4 wasted cells.ئەنجامی : ⁦24⁩ خانە لەسەر ڕێگاکە و تەنیا 4 خانەی بەفیڕۆچوو.CêIT

Lab 3: greedy best-first search on a mazeتاقیگەی 3: گەڕانی چاوچنۆکانە لەسەر لابیرینتێک

The programبەرنامەکە

Here is the Lab 3 program, cleaned and corrected. It keeps the lab's structure: a Point class, manhattan(), solve() and backtrack().

ئەمە تاقیگەی 3ـە، پاککراوە و ڕاستکراوە. هەمان پێکهاتەی تاقیگەکە دەپارێزێت: بە ناوی Point، manhattan()، solve() و backtrack().

greedy_maze.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
import heapq


class Point:
    def __init__(self, x, y):
        self.x = x  # row (down)
        self.y = y  # column (across)

    def __repr__(self):
        return f"({self.x}, {self.y})"  # print (row, column), not a memory address


def manhattan(current, end):
    # rows apart + columns apart; abs() keeps both parts positive
    return abs(current.x - end.x) + abs(current.y - end.y)


def solve(maze, wall, start, end):
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]  # up, left, down, right

    count = 0  # tie-breaker: equal h values come out in the order they went in
    frontier = [(manhattan(start, end), count, start)]  # a min-heap of tuples
    seen = [[False for _ in row] for row in maze]       # True = already expanded
    parent = {start: None}
    explored = []

    while frontier:
        _, _, current = heapq.heappop(frontier)  # the smallest h(n)
        if seen[current.x][current.y]:
            continue                             # an old copy of an expanded cell
        if current.x == end.x and current.y == end.y:
            return backtrack(parent, current), explored

        seen[current.x][current.y] = True
        explored.append(current)

        for dx, dy in directions:
            x, y = current.x + dx, current.y + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) \
                    and maze[x][y] != wall and not seen[x][y]:
                nxt = Point(x, y)
                count += 1
                heapq.heappush(frontier, (manhattan(nxt, end), count, nxt))
                parent[nxt] = current

    return None, explored  # no path


def backtrack(parent, end):
    path = []
    while end is not None:       # stop after the start (its parent is None)
        path.append(end)
        end = parent[end]
    return path[::-1]            # start -> end


maze = [
    ".#.#.###..#.",
    ".#.#...#.##.",
    "...#.#...##.",
    "#.##.#.#.##.",
    "#....#.#....",
    "###.##.#####",
    "....##......",
]

start = Point(6, 0)
end = Point(0, 11)

path, explored = solve(maze, "#", start, end)
if path:
    print("Path found:", path)
    print("Cells on the path:", len(path), "| moves:", len(path) - 1)
    print("Cells expanded:", len(explored))
else:
    print("No path. Cells expanded:", len(explored))
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 4-10

Point stores a row and a column; __repr__ makes it print as (6, 0) instead of a memory address (Python for the AI labs).

Point ڕیزێک و ستوونێک هەڵدەگرێت؛ __repr__ وای لێ دەکات وەک (6, 0) چاپ بێت نەک ناونیشانی (Python بۆ تاقیگەکانی ژیریی دەستکرد).

Lineدێڕی 13-15

The heuristic: rows apart + columns apart.

: جیاوازیی ڕیزەکان + جیاوازیی ستوونەکان.

Lineدێڕی 19

Four moves: up, left, down, right. (dx, dy) is added to the row and the column.

چوار جووڵە: سەرەوە، چەپ، خوارەوە، ڕاست. (dx, dy) بۆ ڕیز و ستوون زیاد دەکرێت.

Lineدێڕی 21-22

The frontier is a min-heap of (h, count, point) tuples: the smallest h is always on top. When two h values are equal, the counter decides, so Python never has to compare two Point objects (why the counter is needed).

لە (h, count, point): بچووکترین h هەمیشە لە سەرەوەیە. کاتێک دوو نرخی h یەکسان بن، ژمێرەرەکە بڕیار دەدات، بۆیە هەرگیز ناچار نابێت دوو Point بەراورد بکات (بۆچی ژمێرەر پێویستە).

Lineدێڕی 23

seen is a grid of False, one per cell. True will mean "already expanded" (the CLOSED list).

seen تۆڕێکە لە False، یەکێک بۆ هەر خانەیەک. True واتای «پێشتر فراوان کراوە» دەبێت (لیستی CLOSED).

Lineدێڕی 24

parent remembers where each point came from.

parent لە بیری دەگرێت هەر خاڵێک لە کوێوە هاتووە.

Lineدێڕی 28-30

Take out the point with the smallest h. A cell can be in the heap twice; the old copy is skipped.

ئەو خاڵەی بچووکترین hـی هەیە دەربهێنە. خانەیەک دەشێت دوو جار لە بێت؛ کۆپییە کۆنەکە تێدەپەڕێنرێت.

Lineدێڕی 31-32

The goal test happens when a point is taken out. Then the path is rebuilt.

کاتێک خاڵێک دەردەهێنرێت ڕوو دەدات. پاشان ڕێگاکە دووبارە دروست دەکرێتەوە.

Lineدێڕی 37-44

For each move: stay inside the maze, avoid walls and expanded cells, push the neighbour with its h, and remember its parent.

بۆ هەر جووڵەیەک: لە ناو بمێنەوە، خۆت لە دیوار و خانە فراوانکراوەکان بپارێزە، دراوسێکە لەگەڵ hـەکەی بخە ناو و باوکەکەی لە بیر بگرە.

Lineدێڕی 42

count += 1 comes before the push, so every entry gets a new number (Python has no ++).

count += 1 پێش خستنە ناوەوە دێت، بۆیە هەر تۆمارێک ژمارەیەکی نوێ وەردەگرێت ( ++ـی نییە).

Lineدێڕی 46

No path: return None, never the explored list.

هیچ ڕێگایەک نییە: None بگەڕێنەوە، هەرگیز لیستی پشکنراوەکان مەگەڕێنەوە.

Lineدێڕی 49-54

Backtracking: follow the parents from the end to the start, then reverse the list.

: لە کۆتاییەوە بە شوێن باوکەکاندا بڕۆ تا سەرەتا، پاشان لیستەکە پێچەوانە بکەرەوە.

Lab 3: greedy best-first search on a mazeتاقیگەی 3: گەڕانی چاوچنۆکانە لەسەر لابیرینتێک

Watching the heapچاودێریکردنی هیپەکە

The lab comments trace the first rounds by hand. Each heap entry is (h, count, point); the rule is simply: the smallest Manhattan value is taken first.

تاقیگەکە یەکەم خولەکان بە دەست شوێن دەکەون. هەر تۆمارێکی (h, count, point)ـە؛ یاساکە سادەیە: بچووکترین نرخی مانهاتن یەکەمجار وەردەگیرێت.

Checked by printing every pop of the program above.بە چاپکردنی هەموو دەرهێنانێکی سەرەوە پشکنراوە.
RoundخولTaken outدەرهێنراوPushedخراوەتە ناوەوەHeap afterwards دواتر
1(17, 0, (6, 0))(16, 1, (6, 1))[(16, 1, (6, 1))]
2(16, 1, (6, 1))(15, 2, (6, 2))[(15, 2, (6, 2))]
3(15, 2, (6, 2))(14, 3, (6, 3))[(14, 3, (6, 3))]
4(14, 3, (6, 3))(13, 4, (5, 3))[(13, 4, (5, 3))]
5(13, 4, (5, 3))(12, 5, (4, 3))[(12, 5, (4, 3))]
6(12, 5, (4, 3))(13, 6, (4, 2)), (11, 7, (4, 4))[(11, 7, (4, 4)), (13, 6, (4, 2))]
7(11, 7, (4, 4))(10, 8, (3, 4))[(10, 8, (3, 4)), (13, 6, (4, 2))]
8(10, 8, (3, 4))(9, 9, (2, 4))[(9, 9, (2, 4)), (13, 6, (4, 2))]

Round 6 is the interesting one: (4, 3) has two open neighbours, (4, 2) with h = 13 and (4, 4) with h = 11. In round 7 the heap gives back (4, 4), because 11 is smaller than 13. (4, 2) stays in the heap for later, and in this maze it is never needed.

خولی 6 سەرنجڕاکێشە: ⁦(4, 3)⁩ دوو دراوسێی کراوەی هەیە، ⁦(4, 2)⁩ بە ⁦h = 13⁩ و ⁦(4, 4)⁩ بە ⁦h = 11⁩. لە خولی 7دا ⁦(4, 4)⁩ دەداتەوە، چونکە ⁦11⁩ لە ⁦13⁩ بچووکترە. ⁦(4, 2)⁩ بۆ دواتر لە دەمێنێتەوە و لەم هەرگیز پێویست نابێت.

Quick checkپشکنینی خێراThe heap holds (13, 6, (4, 2)) and (11, 7, (4, 4)). What does heapq.heappop() return? (13, 6, (4, 2)) و (11, 7, (4, 4))ی تێدایە. heapq.heappop() چی دەگەڕێنێتەوە؟

Fast, but not always shortestخێرا، بەڵام هەمیشە کورتترین نییە

On the Lab 3 maze greedy search is excellent. Its path of 23 moves is also a shortest one (breadth-first search and A* need 23 moves too), and it takes only 28 cells out of the frontier, counting the goal. A* takes 40 and breadth-first search 47.

لەسەر تاقیگەی 3، نایابە. ڕێگا ⁦23⁩ جووڵەییەکەی یەکێکیشە لە ( و ⁦23⁩ جووڵەیان پێویستە) و تەنیا ⁦28⁩ خانە لە دەردەهێنێت، لەگەڵ ئامانجەکە. ⁦40⁩ و ⁦47⁩ دەردەهێنن.

Now run the same greedy program on the Lab 4 maze. Manhattan distance pulls it into the long middle corridor, which points at the goal but leads away from it. It finds a path of 34 cells (33 moves), while A* finds one of 22 cells (21 moves).

ئێستا هەمان لەسەر تاقیگەی 4 جێبەجێ بکە. ڕایدەکێشێتە ناو ڕاڕەوە درێژەکەی ناوەڕاست، کە ڕووی لە ئامانجە بەڵام لێی دوور دەکەوێتەوە. ڕێگایەکی ⁦34⁩ خانەیی (⁦33⁩ جووڵە) دەدۆزێتەوە، لە کاتێکدا یەکێکی ⁦22⁩ خانەیی (⁦21⁩ جووڵە) دەدۆزێتەوە.

The Lab 4 maze, 7 rows by 12 columns, start A at (6, 0) and goal B at (0, 11). The A* route goes from A right to (6, 3), up to (4, 3), left to (4, 1), up to (0, 1) and right along the top row to B: 21 moves. The greedy route goes up column 3 to row 2, right along row 2 to column 9, down to row 4, left to column 5, down to row 6, right along the bottom row to column 11 and up the right edge to B: 33 moves.لابیرینتی تاقیگەی 4، 7 ڕیز بە 12 ستوون، سەرەتای A لە (6, 0) و ئامانجی B لە (0, 11). ڕێگای گەڕانی A* لە Aـەوە بۆ ڕاست تا (6, 3)، بۆ سەرەوە تا (4, 3)، بۆ چەپ تا (4, 1)، بۆ سەرەوە تا (0, 1) و بە درێژایی ڕیزی سەرەوە بۆ ڕاست تا B: 21 جووڵە. ڕێگای گەڕانی چاوچنۆکانە بە ستوونی 3دا بۆ سەرەوە تا ڕیزی 2، بە درێژایی ڕیزی 2 بۆ ڕاست تا ستوونی 9، بۆ خوارەوە تا ڕیزی 4، بۆ چەپ تا ستوونی 5، بۆ خوارەوە تا ڕیزی 6، بە درێژایی ڕیزی خوارەوە بۆ ڕاست تا ستوونی 11 و بە لێواری ڕاستدا بۆ سەرەوە تا B: 33 جووڵە.
Redrawn from a photo of the lab board: greedy follows the "smell" of the goal into a detour.لە وێنەیەکی تەختەی تاقیگەکەوە سەرلەنوێ کێشراوەتەوە: بە دوای «بۆنی» ئامانجدا دەکەوێتە ناو ڕێگایەکی پێچاوپێچەوە.CêIT

This is the proof that greedy best-first search is not optimal. It is often fast, but you cannot trust its path to be the shortest. To get a guaranteed shortest path, the search must also count the steps already taken: that is A* search.

ئەمە بەڵگەیە کە باشترین نییە. زۆرجار خێرایە، بەڵام ناتوانیت متمانە بەوە بکەیت کە ڕێگاکەی کورتترینە. بۆ ئەوەی بە گەرەنتییەوە بدۆزرێتەوە، گەڕانەکە دەبێت ئەو هەنگاوانەش بژمێرێت کە پێشتر نراون: ئەمە گەڕانی A*ـە.

Quick checkپشکنینی خێراWhy does greedy search take the long route on the Lab 4 maze?بۆچی لەسەر تاقیگەی 4 ڕێگا درێژەکە دەگرێت؟

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

MistakeهەڵەWhat happensچی ڕوو دەداتFixچارەسەر
Writing f(n) = g(n) for greedy searchنووسینی ⁦f(n) = g(n)⁩ بۆ It becomes uniform-cost search.دەبێت بە .Use f(n) = h(n).⁦f(n) = h(n)⁩ بەکار بهێنە.
Forgetting one abs() in Manhattan distanceلەبیرچوونی abs()ـێک لە Negative "distances": the order is wrong.«دووریی» سالب: ڕیزبەندییەکە هەڵەیە.abs(dx) + abs(dy)abs(dx) + abs(dy)
Heap entries (h, point) without a counterتۆماری (h, point) بەبێ ژمێرەرTypeError when two h values are equal.TypeError کاتێک دوو نرخی h یەکسانن.Use (h, count, point) (heaps and priority queues).(h, count, point) بەکار بهێنە (هیپەکان و کیووە پێشینەییەکان).
Mixing lists and tuples in one heapتێکەڵکردنی لیست و لە یەک TypeError: '<' not supported between instances of 'list' and 'tuple'TypeError: '<' not supported between instances of 'list' and 'tuple'Tuples everywhere. لە هەموو شوێنێک.
Returning the explored list when there is no pathگەڕاندنەوەی لیستی پشکنراوەکان کاتێک ڕێگا نییە"Path found" is printed with a fake path.«⁦Path found⁩» لەگەڵ ڕێگایەکی ساختە چاپ دەکرێت.Return None.None بگەڕێنەوە.
Calling greedy's path "optimal"پێوتنی «باشترین» بە ڕێگای Wrong on the Lab 4 maze: 33 moves instead of 21.لەسەر تاقیگەی 4 هەڵەیە: ⁦33⁩ جووڵە لەبری ⁦21⁩.Say "the path greedy found"; use A* for a shortest path.بڵێ «ئەو ڕێگایەی دۆزییەوە»؛ بۆ بەکار بهێنە.

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

Mistake: a missing abs()هەڵە: ⁦abs()⁩ـێکی ونبوو

One version of the Lab 3 code wrote the heuristic as abs(current.x - end.x) + (current.y - end.y): the second abs() is missing. Most "distances" then become negative or too small:

وەشانێکی کۆدی تاقیگەی 3 بەم شێوەیە نووسیبوو: abs(current.x - end.x) + (current.y - end.y): abs()ـی دووەم ونە. ئەوکات زۆربەی «دوورییەکان» سالب یان زۆر بچووک دەبن:

missing_abs.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


def wrong(current, end):
    return abs(current.x - end.x) + (current.y - end.y)   # second abs() missing


def right(current, end):
    return abs(current.x - end.x) + abs(current.y - end.y)


end = Point(0, 11)
for cell in [Point(6, 0), Point(6, 3), Point(2, 9)]:
    print((cell.x, cell.y), "wrong:", wrong(cell, end), " right:", right(cell, end))
Explain the codeڕوونکردنەوەی کۆدەکە
Lineدێڕی 8

Without abs(), a goal to the right (bigger column) gives a negative part.

بەبێ abs()، ئامانجێک لە لای ڕاست (ستوونی گەورەتر) بەشێکی سالب دەدات.

On the Lab 3 maze the wrong version found the same path by luck (it was tested with five different goals). On another maze it can choose very bad cells. Always use abs() for both parts.

لەسەر تاقیگەی 3 وەشانە هەڵەکە بە ڕێکەوت هەمان ڕێگای دۆزییەوە (بە پێنج ئامانجی جیاواز تاقی کرایەوە). لەسەر تر دەشێت خانەی زۆر خراپ هەڵبژێرێت. هەمیشە abs() بۆ هەردوو بەشەکە بەکار بهێنە.

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

ExerciseڕاهێنانManhattan distancesدوورییەکانی مانهاتن

In the Lab 3 maze the end is (0, 11). Compute h for the cells (6, 3), (2, 9) and (4, 4).

لە تاقیگەی 3دا کۆتایی ⁦(0, 11)⁩ـە. h بۆ خانەکانی ⁦(6, 3)⁩، ⁦(2, 9)⁩ و ⁦(4, 4)⁩ حیساب بکە.

Show answerوەڵامەکە پیشان بدە

(6, 3): 6 + 8 = 14. (2, 9): 2 + 2 = 4. (4, 4): 4 + 7 = 11. Compare with the heap trace: (4, 4) had h = 11.

⁦(6, 3): 6 + 8⁩ = ⁦14⁩. ⁦(2, 9): 2 + 2⁩ = 4. ⁦(4, 4): 4 + 7⁩ = ⁦11⁩. لەگەڵ شوێنکەوتنی بەراوردی بکە: ⁦(4, 4) h = 11⁩ـی هەبوو.

ExerciseڕاهێنانA different heuristic tableخشتەیەکی جیاوازی پێوەر

Use the worked example again, but now h(A) = 1 (all other values stay the same). In which order are the nodes expanded, and which path is returned? Check your answer by changing one number in greedy_graph.py.

دووبارە نموونە شیکراوەکە بەکار بهێنە، بەڵام ئێستا ⁦h(A) = 1⁩ (هەموو نرخەکانی تر وەک خۆیان دەمێننەوە). بە چ ڕیزبەندییەک فراوان دەکرێن و کام ڕێگا دەگەڕێنرێتەوە؟ بە گۆڕینی یەک ژمارە لە greedy_graph.py وەڵامەکەت بپشکنە.

Hintئاماژە

Start: OPEN holds A (1) and B (4). Which comes out first?

سەرەتا: OPEN، ⁦A (1)⁩ و ⁦B (4)⁩ی تێدایە. کامیان یەکەمجار دەردەچێت؟

Show answerوەڵامەکە پیشان بدە

Order: S, A, D, B, F, then G is taken out. A now looks best, so greedy wastes time in A's branch (A and D) before it goes back to B. The returned path is still S → B → F → G (cost 6), because the parents point that way.

ڕیزبەندی: S، A، D، B، F، پاشان G دەردەهێنرێت. A ئێستا باشترین دیار دەدات، بۆیە لە لقی ⁦A (A⁩ و D) کات بەفیڕۆ دەدات پێش ئەوەی بگەڕێتەوە بۆ B. ڕێگا گەڕێنراوەکە هێشتا S → B → F → Gـە (کۆست ⁦6⁩)، چونکە باوکەکان بەو ئاڕاستەیە ئاماژە دەکەن.

Output with h(A) = 1دەرخستە بە ⁦h(A) = 1⁩
Expand S -> OPEN: [(1, 'A'), (4, 'B')]  CLOSED: ['S']
Expand A -> OPEN: [(3, 'D'), (4, 'B'), (7, 'C')]  CLOSED: ['S', 'A']
Expand D -> OPEN: [(4, 'B'), (7, 'C')]  CLOSED: ['S', 'A', 'D']
Expand B -> OPEN: [(2, 'F'), (7, 'C'), (8, 'E')]  CLOSED: ['S', 'A', 'D', 'B']
Expand F -> OPEN: [(0, 'G'), (7, 'C'), (8, 'E'), (9, 'I')]  CLOSED: ['S', 'A', 'D', 'B', 'F']
Path: S -> B -> F -> G
Path cost: 6
ExerciseڕاهێنانA goal that cannot be reachedئامانجێک کە ناگەیشترێت

In greedy_maze.py, change the end to Point(5, 0), which is a wall. What does the corrected program print? What did the original lab program print?

لە greedy_maze.pyدا کۆتایی بگۆڕە بۆ Point(5, 0) کە دیوارە. چی چاپ دەکات؟ تاقیگەکە چی چاپ دەکرد؟

Show answerوەڵامەکە پیشان بدە
Corrected programبەرنامە ڕاستکراوەکە
No path. Cells expanded: 47

Walls are never pushed, so the goal is never taken out: the search expands all 47 reachable cells and returns None. The original program returned its explored list instead and printed it under "Path found:" with "Path length: 47", which is false. A better program would also check the goal before searching (see search practice).

دیوارەکان هەرگیز ناخرێنە ناوەوە، بۆیە ئامانج هەرگیز دەرناهێنرێت: گەڕانەکە هەموو ⁦47⁩ خانە گەیشتنپێکراوەکە فراوان دەکات و None دەگەڕێنێتەوە. لەبری ئەوە لیستی پشکنراوەکانی دەگەڕاندەوە و لە ژێر «⁦Path found⁩:» لەگەڵ «⁦Path length: 47⁩» چاپی دەکرد، کە ڕاست نییە. پێش گەڕان ئامانجەکەش دەپشکنێت (سەیری ڕاهێنانی گەڕان بکە).

Quick checkپشکنینی خێراWhich statement about greedy best-first search is true?کام ڕستە دەربارەی ڕاستە؟

Summaryپوختە

  • Informed search uses a heuristic h(n), an estimate of the cost from n to the goal; h(n) ≥ 0 and h(goal) = 0.
  • OPEN = frontier (generated, not expanded); CLOSED = explored set (already expanded).
  • Greedy best-first search always expands the node with the smallest f(n) = h(n), using a priority queue.
  • Worst case O(b^m) time and memory; not complete in general (it can loop or get lost); not optimal.
  • Manhattan distance = rows apart + columns apart: a good heuristic for 4-direction grids.
  • On the Lab 4 maze greedy needs 33 moves where 21 are enough: for a guaranteed shortest path, use A*.
  • ⁦h(n)⁩ بەکار دەهێنێت، مەزەندەیەک بۆ کۆست لە nـەوە تا ئامانج؛ ⁦h(n) ≥ 0⁩ و ⁦h(goal) = 0⁩.
  • OPEN = (دروستکراو، فراوان نەکراو)؛ CLOSED = (فراوانکراو).
  • هەمیشە ئەو فراوان دەکات کە بچووکترین ⁦f(n) = h(n)⁩ـی هەیە، بە بەکارهێنانی .
  • لە خراپترین حاڵەتدا ⁦O(b⁩^m) کات و ؛ بە گشتی تەواو نییە (دەشێت بسووڕێتەوە یان ون بێت)؛ باشترین نییە.
  • = جیاوازیی ڕیزەکان + جیاوازیی ستوونەکان: باش بۆ تۆڕی چوار ئاڕاستە.
  • لەسەر تاقیگەی 4، ⁦33⁩ جووڵەی پێویستە لە کاتێکدا ⁦21⁩ بەسە: بۆ ئەوەی بە گەرەنتییەوە بدۆزیتەوە، بەکار بهێنە.
Review questionsپرسیارەکانی پێداچوونەوە
What is the difference between g(n) and h(n)?جیاوازیی نێوان ⁦g(n)⁩ و ⁦h(n)⁩ چییە؟

g(n) is the real cost from the start to n (already walked). h(n) is the estimated cost from n to the goal (still to walk). Greedy uses only h.

⁦g(n)⁩ کۆستی ڕاستەقینەیە لە سەرەتاوە تا n (پێیدا ڕۆیشتووین). ⁦h(n)⁩ کۆستی خەمڵێنراوە لە nـەوە تا ئامانج (هێشتا ماوە). تەنیا h بەکار دەهێنێت.

Why does the heap store (h, count, point) and not (h, point)?بۆچی هیپەکە (h, count, point) هەڵدەگرێت نەک (h, point)؟

When two h values are equal, Python compares the next item. The unique counter decides the tie, so two Point objects are never compared (that would raise TypeError). See heaps and priority queues.

کاتێک دوو نرخی h یەکسان بن، دانەی دواتر بەراورد دەکات. ژمێرەرە تاکەکە یەکسانییەکە یەکلا دەکاتەوە، بۆیە هەرگیز دوو Point بەراورد ناکرێن (ئەوە TypeError دروست دەکات). سەیری هیپەکان و کیووە پێشینەییەکان بکە.

Is greedy best-first search complete?ئایا گەڕانی چاوچنۆکانە تەواوە؟

Not in general: without a CLOSED list it can loop, and in an infinite space it can run forever. With a CLOSED list in a finite space it does find a goal if one exists.

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

Why is Manhattan distance a safe estimate in a 4-direction maze?بۆچی دووریی مانهاتن مەزەندەیەکی بێمەترسییە لە لابیرینتێکی چوار ئاڕاستەدا؟

It is the length of the walk if there were no walls. Walls can only make the real walk longer, never shorter.

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

Videoڤیدیۆ

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

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

Search - Lecture 0 - CS50's Introduction to Artificial Intelligence with Python 2020CS50 · Englishئینگلیزی · 190K viewsبینین · 3.8K likesلایک · Partبەشی 53:18–1:05:15 (ofلە 1:49:29)

Harvard's CS50 AI lecture on search: the parts of a search problem, the frontier loop, DFS and BFS on mazes, and greedy best-first search.

وانەی گەڕان لە کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard: بەشەکانی ، ، و لەسەر ، هەروەها .

Watch 53:18-1:05:15: uninformed and informed search, heuristics, Manhattan distance, and greedy best-first search on a maze, where its path can be longer than the best one.

لە ⁦53:18⁩ تا ⁦1:05:15⁩ سەیر بکە: و ، ، ، هەروەها لەسەر ، کە تێیدا دەشێت لە درێژتر بێت.

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

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

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

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

A* Searchگەڕانی A*

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 ن.