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

A* Searchگەڕانی A*

A* expands the node with the smallest f(n) = g(n) + h(n). Learn the algorithm, follow the course's worked example (and fix its heuristic), see why admissible and consistent heuristics give the optimal path, solve the Lab 4 maze by hand and in Python, and find the cheapest route on a road map.

ئەو فراوان دەکات کە بچووکترین ⁦f(n) = g(n) + h(n)⁩ـی هەیە. فێر بە، بە دوای نموونە شیکراوەکەی کۆرسەکەدا بڕۆ (و چاک بکەرەوە)، ببینە بۆچی و باشترین ڕێگا دەدەن، تاقیگەی 4 بە دەست و بە چارەسەر بکە و هەرزانترین ڕێگا لەسەر نەخشەیەکی ڕێگاکان بدۆزەرەوە.

31 min read30 خولەک خوێندنەوە · 20 stepsهەنگاو

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

Compute f(n) = g(n) + h(n) and run A* by hand with OPEN and CLOSED lists.
Explain why A* stops when the goal is taken out of OPEN, and when it is complete.
Check whether a heuristic is admissible and consistent, using h(n) ≤ c(n, n′) + h(n′).
Compare heuristics: a better-informed admissible heuristic expands fewer nodes.
Read, run and correct A* programs for a grid maze and for a weighted road map.

⁦f(n) = g(n) + h(n)⁩ حیساب بکەیت و بە دەست بە لیستەکانی OPEN و CLOSED جێبەجێ بکەیت.
ڕوونی بکەیتەوە بۆچی کاتێک ئامانج لە OPEN دەردەهێنرێت دەوەستێت و کەی تەواوە.
بپشکنیت ئایا پەسەندکراو و هاوئاهەنگە، بە بەکارهێنانی ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′).
بەراورد بکەیت: کە زانیاریی زیاترە کەمتر فراوان دەکات.
بۆ خانەدار و بۆ نەخشەیەکی ڕێگای کێشدار بخوێنیتەوە، جێبەجێیان بکەیت و ڕاستیان بکەیتەوە.

A: the cost so far plus a guessگەڕانی A: کۆستی تا ئێستا لەگەڵ مەزەندەیەک

A* search (say "A star") is the best-known kind of best-first search. It uses two numbers for every node n: g(n), the cost to reach n from the start state, and h(n), the heuristic estimate of the cost from n to the goal.

(دەخوێنرێتەوە «ئەی ستار») بەناوبانگترین جۆری . بۆ هەر n دوو ژمارە بەکار دەهێنێت: ⁦g(n)⁩، کۆستی گەیشتن بە n لە و ⁦h(n)⁩، مەزەندەی بۆ کۆست لە nـەوە تا ئامانج.

So A* joins the two searches you already know: uniform-cost search, which looks back at g(n), and greedy best-first search, which looks forward at h(n). With a good heuristic it finds the shortest path and expands much less of the search tree than uniform-cost search.

کەواتە دوو گەڕانی ناسراو پێکەوە دەبەستێتەوە: ، کە سەیری دواوە دەکات بۆ ⁦g(n)⁩ و ، کە سەیری پێشەوە دەکات بۆ ⁦h(n)⁩. بە باش دەدۆزێتەوە و بەشێکی زۆر کەمتری فراوان دەکات لە .

Correctionڕاستکردنەوە

The notes say that A* "finds the shortest path" and "provides the optimal result faster", without any condition. Both are true only when the heuristic is admissible: it never overestimates the real cost. With a heuristic that overestimates, A* can return a longer path. You will see an example below.

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

A taxi from Slemani to Halabjaتاکسییەک لە سلێمانییەوە بۆ هەڵەبجە

Soran drives a taxi from Slemani to Halabja. At every junction he adds two numbers for each road: the kilometres he would have driven so far on that road (g) and the straight-line distance still left to Halabja (h). He takes the road with the smallest total. A greedy driver would look only at the straight-line distance and might choose a mountain road that looks short but is long.

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

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

A real driver also thinks about traffic and road quality. A* needs every one of these things turned into one cost number per road.

شۆفێرێکی ڕاستەقینە بیر لە قەرەباڵغی و باشیی ڕێگاش دەکاتەوە. پێویستی بەوەیە هەموو ئەمانە بۆ هەر ڕێگایەک بکرێنە یەک ژمارەی کۆست.

The evaluation function f(n) = g(n) + h(n)کرداری هەڵسەنگاندن ⁦f(n) = g(n) + h(n)⁩

A* orders its OPEN list (the frontier) by f(n) = g(n) + h(n) and always expands the node with the smallest f.

لیستی OPEN () بە پێی ⁦f(n) = g(n) + h(n)⁩ ڕیز دەکات و هەمیشە ئەو فراوان دەکات کە بچووکترین fـی هەیە.

g is known, h is a guess, f is the estimated total.g زانراوە، h مەزەندەیە، f کۆی خەمڵێنراوە.CêIT

f(n): the estimated cost of the cheapest solution that goes through n.
g(n): the cost to reach n from the start state (known).
h(n): the estimated cost from n to the goal node (the heuristic).

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

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

A* search (the course's six steps, corrected)گەڕانی A* (شەش هەنگاوەکەی کۆرسەکە، ڕاستکراوە)

Put the start node in OPEN, with g = 0 and f = h(start).
سەرەتا بخە ناو OPEN، بە ⁦g = 0⁩ و ⁦f = h(start)⁩.
If OPEN is empty, return failure and stop.
ئەگەر OPEN بەتاڵ بوو، سەرنەکەوتن بگەڕێنەوە و بوەستە.
Take the node n with the smallest f = g + h out of OPEN. If n is the goal, return success and stop.
ئەو لە OPEN دەربهێنە کە بچووکترین ⁦f = g + h⁩ـی هەیە (با ناوی بنێین n). ئەگەر n ئامانج بوو، سەرکەوتن بگەڕێنەوە و بوەستە.
Otherwise expand n: put n in CLOSED and generate its successors. For each successor n′ that is in neither OPEN nor CLOSED, compute g(n′), h(n′) and f(n′), remember that it came from n, and put it in OPEN.
ئەگەر نا، n فراوان بکە: n بخە ناو CLOSED و منداڵەکانی دروست بکە. بۆ هەر منداڵێکی n′ کە نە لە OPEN و نە لە CLOSEDـە، ⁦g(n⁩′)، ⁦h(n⁩′) و ⁦f(n⁩′) حیساب بکە، لە بیری بگرە کە لە nـەوە هاتووە و بیخە ناو OPEN.
If n′ is already in OPEN or CLOSED but the new path to it is cheaper (a smaller g), update its g and f, point its back pointer (parent) to n, and put it back in OPEN.
ئەگەر n′ پێشتر لە OPEN یان CLOSEDـە بەڵام ڕێگا نوێیەکە بۆی هەرزانترە (gـی بچووکتر)، g و fـەکەی نوێ بکەرەوە، ئاماژەی دواوەی () بۆ n ئاڕاستە بکە و بیخەرەوە ناو OPEN.
Go back to step 2.
بگەڕێوە بۆ هەنگاوی 2.

Correctionڕاستکردنەوە

Small slips in the PDF: it writes "successor n" where it means n′ (the child), "already in OPEN and CLOSED" where it means OPEN or CLOSED, and it does not say what happens when a cheaper path is found. The steps above say it: update g, the parent and f, and put the node back in OPEN.

هەڵە بچووکەکانی PDFـەکە: دەنووسێت «منداڵی n» لە کاتێکدا مەبەستی n′ـە (منداڵەکە)، «پێشتر لە OPEN و CLOSEDـە» لە کاتێکدا مەبەستی OPEN یان CLOSEDـە و نالێت چی ڕوو دەدات کاتێک ڕێگایەکی هەرزانتر دەدۆزرێتەوە. هەنگاوەکانی سەرەوە دەیڵێن: g، باوک و f نوێ بکەرەوە و بخەرەوە ناو OPEN.

Quick checkپشکنینی خێراWhen does A* stop with success? کەی بە سەرکەوتن دەوەستێت؟After every node has been expandedدوای ئەوەی هەموو نۆدەکان فراوان کرانWhen a goal node is taken out of OPENکاتێک نۆدێکی ئامانج لە OPEN دەردەهێنرێتWhen OPEN is emptyکاتێک OPEN بەتاڵەAs soon as a goal node is generatedهەر کە نۆدێکی ئامانج دروست دەکرێت

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

Let's traverse the graph below with A*, from S to G. The table gives the heuristic value of every state; for each path in OPEN we compute f(n) = g(n) + h(n), where g(n) is the cost from S to n. As before we use the OPEN and CLOSED lists.

با بە بە ناو ئەم خوارەوەدا بڕۆین، لە Sـەوە بۆ G. خشتەکە نرخی هەموو دەدات؛ بۆ هەر ڕێگایەکی ناو OPEN، ⁦f(n) = g(n) + h(n)⁩ حیساب دەکەین، کە ⁦g(n)⁩ کۆستە لە Sـەوە تا n. وەک پێشوو لیستەکانی OPEN و CLOSED بەکار دەهێنین.

The graph of the notes' example, redrawn. The highlighted path is the optimal one. نموونەکەی تێبینییەکان، سەرلەنوێ کێشراوە. ڕێگا دیارکراوەکە باشترینە.CêIT

The heuristic table of the notesخشتەی تێبینییەکان
State	S	A	B	C	D	G
h(n)	5	3	4	2	6	0

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

The trace: OPEN after every roundشوێنکەوتن: OPEN دوای هەر خولێک

Each entry is a path with its f value. g is the sum of the step costs on the path; h is the table value of its last node.

هەر تۆمارێک لەگەڵ نرخی fـەکەی. g کۆی سەر ڕێگاکەیە؛ h نرخی خشتەکەیە بۆ دوایین ڕێگاکە.

Roundخول	OPEN (path, f)OPEN (ڕێگا، f)	How f is computedf چۆن حیساب کراوە
Startسەرەتا	`(S, 5)`	0 + 5 = 5
1	`(S→A, 4), (S→G, 10)`	S→A: 1 + 3 = 4 · S→G: 10 + 0 = 10
2	`(S→A→C, 4), (S→A→B, 7), (S→G, 10)`	S→A→C: 2 + 2 = 4 · S→A→B: 3 + 4 = 7
3	`(S→A→C→G, 6), (S→A→C→D, 11), (S→A→B, 7), (S→G, 10)`	S→A→C→G: 6 + 0 = 6 · S→A→C→D: 5 + 6 = 11
4	$S \to A \to C \to G$ (f = 6) is taken out: it is the goal. $S \to A \to C \to G$ ⁦(f = 6)⁩ دەردەهێنرێت: ئامانجە.	Stop. Cost 6.وەستان. کۆست 6.

Look at round 1: the direct road S→G is already in OPEN, but its f = 10 is large, so A* keeps it waiting. In round 4 the path S→A→C→G with f = 6 comes out first: the optimal path, cost 6. A* does not look at the remaining paths; it returns the first goal it takes out.

سەیری خولی 1 بکە: ڕێگای ڕاستەوخۆی S→G پێشتر لە OPENـە، بەڵام ⁦f = 10⁩ـەکەی گەورەیە، بۆیە چاوەڕێی پێ دەکات. لە خولی 4دا ڕێگای S→A→C→G بە ⁦f = 6⁩ یەکەمجار دەردەچێت: باشترین ڕێگا، کۆست 6. سەیری ڕێگاکانی تر ناکات؛ یەکەم ئامانج کە دەریدەهێنێت دەیگەڕێنێتەوە.

A* SearchJohn Levine · Englishئینگلیزی · 567K viewsبینین · 11K likesلایک
A* traced by hand on a small graph: every path gets f = g + h, and the smallest f is expanded next.
بە دەست لەسەر بچووک جێبەجێ دەکرێت: هەر `f = g + h` وەردەگرێت و دواتر ئەو فراوان دەکرێت کە `f`ـەکەی لە هەمووان بچووکترە.
Whole video: A* traced by hand on a small graph; every path in the OPEN list gets f = g + h. Careful: at 6:00 the score written for the path S-A-B-A is wrong; it should be 17, not 20 (the video's description gives this correction).
هەموو ڤیدیۆکە: بە دەست لەسەر بچووک؛ هەر لە OPEN list بەهای `f = g + h` وەردەگرێت. ئاگادار بە: لە ⁦6:00⁩ ئەو بەهایەی بۆ ⁦S-A-B-A⁩ نووسراوە هەڵەیە؛ دەبێت ⁦17⁩ بێت نەک ⁦20⁩ (لە وەسفی ڤیدیۆکەدا ئەم ڕاستکردنەوەیە هاتووە).

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

Is this heuristic admissible?ئایا ئەم پێوەرە پەسەندکراوە؟

Compare every h with the real cheapest cost to G (h*). For example, from D the only road to G costs 2, so h*(D) = 2.

هەر hـێک لەگەڵ هەرزانترین کۆستی ڕاستەقینە تا ⁦G (h*)⁩ بەراورد بکە. بۆ نموونە، لە Dـەوە تاکە ڕێگا بۆ G کۆستی 2یە، بۆیە ⁦h*(D) = 2⁩.

Node	S	A	B	C	D	G
h from the notesh لە تێبینییەکانەوە	5	3	4	2	6	0
real cheapest cost hهەرزانترین کۆستی ڕاستەقینە h	6	5	7	4	2	0
h ≤ h?⁦h ≤ h⁩؟	✓	✓	✓	✓	✗	✓

Correctionڕاستکردنەوە

In the notes' example h(D) = 6 but the real cost from D to G is only 2: this heuristic overestimates, so it is not admissible. A* still happens to return the optimal path here, but only by luck. A correct table uses, for example, h(D) = 2. Then the third round shows ( $S \to A \to C \to D$ , 7) instead of 11, and A* still returns $S \to A \to C \to G$ with cost 6.

لە نموونەکەی تێبینییەکاندا ⁦h(D) = 6⁩ـە بەڵام کۆستی ڕاستەقینە لە Dـەوە تا G تەنیا 2یە: ئەم زیاد دەخەمڵێنێت، بۆیە پەسەندکراو نییە. لێرەدا بە ڕێکەوت هێشتا باشترین ڕێگا دەگەڕێنێتەوە، بەڵام تەنیا بە بەخت. خشتەیەکی دروست بۆ نموونە ⁦h(D) = 2⁩ بەکار دەهێنێت. ئەوکات خولی سێیەم ( $S \to A \to C \to D$ , ⁦7⁩) نیشان دەدات لەبری ⁦11⁩ و هێشتا $S \to A \to C \to G$ بە کۆستی 6 دەگەڕێنێتەوە.

Why does it matter? Change one more number: make h(C) = 10, far above its real cost 4. Now C looks terrible, A* never opens it in time, and it takes out the expensive direct road S→G with cost 10. The program below shows all three tables. Its OPEN list is a heap: heapq.heappop() always returns the entry with the smallest f (heaps and priority queues).

بۆچی گرنگە؟ ژمارەیەکی تر بگۆڕە: ⁦h(C) = 10⁩ دابنێ، زۆر سەرووی کۆستی ڕاستەقینەی 4. ئێستا C زۆر خراپ دیار دەدات، لە کاتی خۆیدا نایکاتەوە و ڕێگا ڕاستەوخۆ گرانەکەی S→G بە کۆستی ⁦10⁩ دەردەهێنێت. خوارەوە هەر سێ خشتەکە نیشان دەدات. لیستی OPENـەکەی : heapq.heappop() هەمیشە ئەو تۆمارە دەگەڕێنێتەوە کە بچووکترین fـی هەیە (هیپەکان و کیووە پێشینەییەکان).

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

import heapq

# The worked example of the notes: node -> {child: step cost}
graph = {
    "S": {"A": 1, "G": 10},
    "A": {"B": 2, "C": 1},
    "B": {"D": 5},
    "C": {"D": 3, "G": 4},
    "D": {"G": 2},
    "G": {},
}


def a_star(graph, h, start, goal, show=False):
    frontier = [(h[start], [start])]    # entries: (f, path)
    best_g = {start: 0}
    closed = set()
    while frontier:
        if show:
            print("  OPEN:", ", ".join(f"({'-'.join(p)}, {f})" for f, p in sorted(frontier)))
        f, path = heapq.heappop(frontier)
        node = path[-1]
        if node == goal:                     # stop when the goal is SELECTED
            return path, best_g[node]
        if node in closed:
            continue
        closed.add(node)
        for child, cost in graph[node].items():
            g = best_g[node] + cost
            if g < best_g.get(child, float("inf")):
                best_g[child] = g
                heapq.heappush(frontier, (g + h[child], path + [child]))
    return None, None


h_notes = {"S": 5, "A": 3, "B": 4, "C": 2, "D": 6, "G": 0}   # h(D) = 6 is too high
h_fixed = {"S": 5, "A": 3, "B": 4, "C": 2, "D": 2, "G": 0}   # admissible
h_bad   = {"S": 5, "A": 3, "B": 4, "C": 10, "D": 2, "G": 0}  # h(C) = 10 is too high

for name, h in [("notes", h_notes), ("fixed", h_fixed), ("bad", h_bad)]:
    print(f"h = {name}:")
    path, cost = a_star(graph, h, "S", "G", show=True)
    print("  Result:", " -> ".join(path), "| cost", cost)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 4-11

The graph of the notes, as a dictionary of dictionaries: node → {child: step cost}.

تێبینییەکان، وەک لە : ← {منداڵ: }.

Lineدێڕی 15

Every OPEN entry keeps the whole path, like the notes' lists.

هەر تۆمارێکی OPEN هەموو ڕێگاکە هەڵدەگرێت، وەک لیستەکانی تێبینییەکان.

Lineدێڕی 23-24

The goal test when a path is taken out.

کاتێک ڕێگایەک دەردەهێنرێت.

Lineدێڕی 29-32

g = g(parent) + step cost; a child is pushed only if this path to it is cheaper than any found before.

⁦g = g⁩(باوک) + ؛ منداڵ تەنیا دەخرێتە ناوەوە ئەگەر ئەم ڕێگایە بۆی لە هەموو ئەوانەی پێشتر هەرزانتر بێت.

Lineدێڕی 36-38

Three heuristic tables: the notes' one, a corrected one, and one with a very bad h(C).

سێ خشتەی : هی تێبینییەکان، یەکێکی ڕاستکراوە و یەکێک بە ⁦h(C)⁩ـی زۆر خراپ.

Quick checkپشکنینی خێراWhich h value in the notes' table breaks admissibility?کام نرخی h لە خشتەکەی تێبینییەکاندا وا دەکات پەسەندکراو نەبێت؟h(S) = 5, because S is the start⁦h(S) = 5⁩، چونکە S سەرەتایەh(G) = 0h(G) = 0h(D) = 6, because the real cost from D is 2⁦h(D) = 6⁩، چونکە کۆستی ڕاستەقینە لە Dـەوە 2یەh(B) = 4, because B is not on the best path⁦h(B) = 4⁩، چونکە B لەسەر باشترین ڕێگا نییە

Points to rememberخاڵە گرنگەکان

A* returns the first goal it takes out of OPEN and does not search the remaining paths. Because it waits until the goal has the smallest f, that first goal comes with the cheapest path (when h is admissible).
The efficiency of A* depends on the quality of the heuristic: the closer h is to the real cost (without going over it), the fewer nodes A* expands.
If C* is the cost of the optimal solution, A* with a consistent heuristic expands every node with f(n) < C*, may expand some nodes with f(n) = C*, and never expands a node with f(n) > C*.
Complete: A* always finds a solution if one exists, as long as (1) the branching factor is finite and (2) every action costs at least some small positive amount ε > 0.

یەکەم ئامانج کە لە OPEN دەریدەهێنێت دەگەڕێنێتەوە و ڕێگاکانی تر ناگەڕێت. چونکە چاوەڕێ دەکات تا ئامانج بچووکترین fـی دەبێت، ئەو یەکەم ئامانجە لەگەڵ هەرزانترین ڕێگا دێت (کاتێک h پەسەندکراوە).
کارایی بەستراوەتەوە بە باشیی : هەتا h نزیکتر بێت لە کۆستی ڕاستەقینە (بەبێ ئەوەی لێی تێپەڕێت)، کەمتر فراوان دەکات.
ئەگەر C* کۆستی بێت، بە هەموو ئەو فراوان دەکات کە ⁦f(n) < C⁩*، لەوانەیە هەندێک لەوانەش فراوان بکات کە ⁦f(n) = C⁩* و هەرگیز فراوان ناکات کە ⁦f(n) > C⁩*.
تەواوە: هەمیشە چارەسەرێک دەدۆزێتەوە ئەگەر هەبێت، بە مەرجێک ⁦(1)⁩ سنووردار بێت و ⁦(2)⁩ هەموو لانیکەم بڕێکی موجەبی بچووکی ε > 0 بکات.

What was correctedچی ڕاست کرایەوە

Point 3 is unreadable in the PDF ("satisfy the condition f(n)<="" li=…"): web code was copied by mistake. The intended rule is the C* rule above.
Point 4 says "the cost at every action is fixed". The real condition is that every action cost is positive (at least ε > 0); costs may be different from each other.

خاڵی 3 لە PDFـەکەدا ناخوێنرێتەوە («⁦satisfy the condition f(n)<="" li⁩=…»): کۆدی وێب بە هەڵە کۆپی کراوە. یاسای مەبەست یاسای C*ـی سەرەوەیە.
خاڵی 4 دەڵێت «کۆستی هەموو جێگیرە». مەرجی ڕاستەقینە ئەوەیە کە کۆستی هەموو موجەب بێت (لانیکەم ε > ⁦0⁩)؛ کۆستەکان دەتوانن جیاواز بن.

The notes also point to an article for further reading: A* search algorithm (Medium).

تێبینییەکان ئاماژە بە وتارێکیش دەکەن بۆ خوێندنەوەی زیاتر: ⁦A* search algorithm (Medium)⁩.

Quick checkپشکنینی خێراWhich condition does A* need to be complete? پێویستی بە کام مەرجە بۆ ئەوەی تەواو بێت؟Every step must cost exactly the sameهەموو هەنگاوێک دەبێت ڕێک هەمان کۆستی هەبێتThe graph must be a treeگرافەکە دەبێت دارێک بێتh(n) = 0 for every node⁦h(n) = 0⁩ بۆ هەموو نۆدێکA finite branching factor and every step cost at least some ε > 0ڕێژەی لقبوونەوە سنووردار و هەموو کۆستێکی هەنگاو لانیکەم ε > 0

Admissible and consistent heuristicsپێوەرە پەسەندکراوەکان و پێوەرە هاوئاهەنگەکان

Definitionپێناسە

A heuristic that never overestimates: h(n) is never more than the true cheapest cost from n to a goal. A* with an admissible heuristic finds an optimal path. For A* graph search that never reopens an explored node, the heuristic must also be .

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

Definitionپێناسە

A heuristic that never drops by more than the step cost along an edge: h(n) ≤ c(n, n′) + h(n′) for every successor n′. Every consistent heuristic is also admissible.

کە لە درێژایی لێوارێکدا هەرگیز زیاتر لە کۆستی هەنگاوەکە کەم نابێتەوە: بۆ هەموو منداڵێکی n′، ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′). هەموو .

Consistency is a triangle rule; admissibility compares h with the real cost.هاوئاهەنگی یاسایەکی سێگۆشەییە؛ پەسەندکراوبوون h لەگەڵ کۆستی ڕاستەقینە بەراورد دەکات.CêIT

Non-negative: h(n) ≥ 0, and h(goal) = 0.
Admissible: h(n) ≤ h*(n), the real cheapest cost from n to a goal. It never overestimates.
Consistent: for every successor n′ of n with step cost c(n, n′): h(n) ≤ c(n, n′) + h(n′). One step can lower h by at most the cost of that step. Every consistent heuristic is also admissible.
Manhattan distance on a 4-direction grid is consistent: one step costs 1 and changes the distance by exactly 1.

ناسالب: ⁦h(n) ≥ 0⁩ و ⁦h(goal) = 0⁩.
پەسەندکراو: ⁦h(n) ≤ h*(n)⁩، هەرزانترین کۆستی ڕاستەقینە لە nـەوە تا ئامانج. هەرگیز زیاد ناخەمڵێنێت.
هاوئاهەنگ: بۆ هەر منداڵێکی n′ـی n بە ⁦c(n, n⁩′): ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′). یەک هەنگاو دەتوانێت h لانیزۆر بە ئەندازەی کۆستی ئەو هەنگاوە کەم بکاتەوە. هەموو هەروەها .
لەسەر تۆڕێکی چوار ئاڕاستە هاوئاهەنگە: یەک هەنگاو کۆستی 1ـە و دوورییەکە ڕێک 1 دەگۆڕێت.

The rules written under the lab photoئەو یاسایانەی لە ژێر وێنەی تاقیگەکەدا نووسراون

"1. It should be positive." A heuristic must be non-negative: zero is allowed, and at the goal h = 0.
"2. h(n) >= h(n′) + g", with the Kurdish note «the current step must be equal to or larger than the next step». This is backwards. The correct consistency rule is h(n) ≤ c(n, n′) + h(n′): the estimate at the current node may be at most the step cost plus the estimate at the next node.

«1. دەبێت موجەب بێت.» دەبێت ناسالب بێت: سفر ڕێگەپێدراوە و لە ئامانجدا ⁦h = 0⁩.
«⁦2. h(n) >= h(n⁩′) + g»، لەگەڵ تێبینییە کوردییەکەی «هەنگاوی ئێستا پێویستە یەکسان یان گەورەتر بێت لە هەنگاوی دواتر». ئەمە پێچەوانەیە. یاسای دروستی هاوئاهەنگی ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′)ـە: مەزەندەی ئێستا لانیزۆر دەتوانێت یەکسان بێت بە لەگەڵ مەزەندەی دواتر.

A* Search: Heuristic Admissibility and Consistency: Are my estimates any good?Jacob Schrum · Englishئینگلیزی · 84K viewsبینین · 1.4K likesلایک · Partبەشی 0:00–8:45 (ofلە 16:55)
What admissible and consistent heuristics mean, how the triangle rule defines consistency, and how the two conditions are related.
و واتایان چییە، یاسای سێگۆشە چۆن هاوئاهەنگی پێناسە دەکات و ئەم دوو مەرجە چ پەیوەندییەکیان بە یەکەوە هەیە.
Watch 0:00-8:45: admissible and consistent heuristics, the triangle rule, and how the two are related. The sound is quiet: turn the volume up.
لە ⁦0:00⁩ تا ⁦8:45⁩ سەیر بکە: و ، یاسای سێگۆشە و پەیوەندیی نێوان ئەم دووانە. دەنگەکەی نزمە، بۆیە دەنگی ئامێرەکەت بەرز بکەرەوە.

Admissible and consistent heuristicsپێوەرە پەسەندکراوەکان و پێوەرە هاوئاهەنگەکان

Why an admissible heuristic gives the optimal pathبۆچی پێوەرێکی پەسەندکراو باشترین ڕێگا دەدات

Here is the idea in four short steps. Let C* be the cost of the optimal path.

بیرۆکەکە لە چوار هەنگاوی کورتدا ئەمەیە. با C* کۆستی باشترین ڕێگا بێت.

Before the optimal goal is found, some node n of the optimal path is always waiting in OPEN.
For that node, f(n) = g(n) + h(n) ≤ g(n) + (real cost from n) = C*, because h never overestimates.
A worse goal G2 has h(G2) = 0, so its f is its real cost, which is more than C*.
A* always takes the smallest f, so it takes n (f ≤ C*) before G2. Repeating this, it reaches the optimal goal first.

پێش ئەوەی ئامانجی باشترین بدۆزرێتەوە، هەمیشە n لەسەر باشترین ڕێگا لە OPEN چاوەڕێ دەکات.
بۆ ئەو ، ⁦f(n) = g(n) + h(n) ≤ g(n) +⁩ (کۆستی ڕاستەقینە لە nـەوە) = C*، چونکە h هەرگیز زیاد ناخەمڵێنێت.
ئامانجێکی خراپتر ⁦G2 h(G2) = 0⁩ـی هەیە، بۆیە fـەکەی کۆستە ڕاستەقینەکەیەتی، کە لە C* زیاترە.
هەمیشە بچووکترین f وەردەگرێت، بۆیە ⁦n (f ≤ C*)⁩ پێش ⁦G2⁩ وەردەگرێت. بەم دووبارەبوونەوەیە، یەکەمجار دەگاتە ئامانجی باشترین.

Going furtherزانیاری زیاتر

With a CLOSED list (graph search) one more thing is needed: either the heuristic is consistent, or A* must reopen a closed node (put it back in OPEN) when it finds a cheaper path to it. The grid, 8-puzzle and town-map programs in this lesson skip closed nodes, so they rely on consistent heuristics: Manhattan distance on the 4-direction grid, misplaced tiles and Manhattan distance on the 8-puzzle, and the straight-line distances of the town map are all consistent. (The original Lab 4 code had no CLOSED check, so it did reopen cells.)

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

Admissible and consistent heuristicsپێوەرە پەسەندکراوەکان و پێوەرە هاوئاهەنگەکان

Where good heuristics come fromپێوەرە باشەکان لە کوێوە دێن

A good heuristic is often the exact cost of a relaxed problem: the same puzzle with a rule removed. Removing a rule can only make the problem easier, so its cost can never be more than the real cost. That is why such heuristics are admissible.

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

h1 = misplaced tiles (from the greedy lesson): the cost if a tile could jump straight to its square.
h2 = Manhattan distance of every tile: the cost if a tile could slide over the others. Since every tile that is out of place needs at least one move, h2 ≥ h1: we say h2 dominates h1.
h = 0 is admissible too, but it gives no help: A* with h = 0 is exactly uniform-cost search.

⁦h1⁩ = پارچە شوێنهەڵەکان (لە وانەی گەڕانی چاوچنۆکانە): کۆستەکە ئەگەر پارچەیەک بیتوانیایە ڕاستەوخۆ باز بدات بۆ خانەکەی.
⁦h2⁩ = هەموو پارچەیەک: کۆستەکە ئەگەر پارچەیەک بیتوانیایە بەسەر پارچەکانی تردا بخزێت. چونکە هەر پارچەیەکی شوێنهەڵە لانیکەم یەک جووڵەی پێویستە، ⁦h2 ≥ h1⁩: دەڵێین ⁦h2⁩ زاڵە بەسەر ⁦h1⁩دا.
⁦h = 0⁩ـیش پەسەندکراوە، بەڵام هیچ یارمەتییەک نادات: بە ⁦h = 0⁩ ڕێک .

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

import heapq

GOAL = (1, 2, 3,
        8, 0, 4,
        7, 6, 5)       # 0 = the empty square (the goal of the notes' 8-puzzle)


def misplaced(state):
    """h1: how many tiles are not in their goal square."""
    return sum(1 for i in range(9) if state[i] != 0 and state[i] != GOAL[i])


def manhattan(state):
    """h2: for every tile, rows + columns away from its goal square."""
    total = 0
    for i, tile in enumerate(state):
        if tile != 0:
            j = GOAL.index(tile)
            total += abs(i // 3 - j // 3) + abs(i % 3 - j % 3)
    return total


def no_heuristic(state):
    return 0           # h = 0: A* becomes uniform-cost search


def neighbours(state):
    e = state.index(0)
    r, c = divmod(e, 3)
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            s = list(state)
            n = nr * 3 + nc
            s[e], s[n] = s[n], s[e]   # slide a tile into the empty square
            yield tuple(s)


def a_star(start, h):
    frontier = [(h(start), 0, start)]
    g = {start: 0}
    closed = set()
    while frontier:
        f, cost, state = heapq.heappop(frontier)
        if state in closed:
            continue
        if state == GOAL:
            return cost, len(closed)        # moves, nodes expanded
        closed.add(state)
        for nxt in neighbours(state):
            if cost + 1 < g.get(nxt, float("inf")):
                g[nxt] = cost + 1
                heapq.heappush(frontier, (cost + 1 + h(nxt), cost + 1, nxt))


starts = {
    "notes' start": (1, 2, 3, 8, 6, 0, 7, 5, 4),
    "start B": (8, 3, 5, 4, 1, 6, 2, 7, 0),
    "start C": (2, 1, 6, 4, 0, 8, 7, 5, 3),
}
for name, s in starts.items():
    print(name, "| h1 =", misplaced(s), "| h2 =", manhattan(s))
    for h in (no_heuristic, misplaced, manhattan):
        moves, expanded = a_star(s, h)
        print(f"   {h.__name__:12} moves: {moves:2}   nodes expanded: {expanded}")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 3-5

The goal of the notes' 8-puzzle, as a tuple of 9 numbers (0 = the empty square).

ئامانجی یاریی 8-پارچەی تێبینییەکان، وەک لە 9 ژمارە (⁦0⁩ = خانە بەتاڵەکە).

Lineدێڕی 8-10

h1: count the tiles that are not on their goal square.

⁦h1⁩: ئەو پارچانە بژمێرە کە لەسەر خانەی ئامانجی خۆیان نین.

Lineدێڕی 13-20

h2: for every tile add rows apart + columns apart from its goal square. i // 3 is the row and i % 3 the column of position i.

⁦h2⁩: بۆ هەر پارچەیەک جیاوازیی ڕیز + جیاوازیی ستوون لە خانەی ئامانجی کۆ بکەرەوە. i // 3 ڕیزە و i % 3 ستوونی شوێنی iـیە.

Lineدێڕی 23-24

h = 0: A* turns into uniform-cost search.

⁦h = 0⁩: دەبێت بە .

Lineدێڕی 27-36

The moves: slide a tile next to the empty square into it.

جووڵەکان: پارچەیەکی تەنیشت خانە بەتاڵەکە بخزێنە ناوی.

Lineدێڕی 39-53

A* exactly as before; it returns the number of moves and how many nodes it expanded.

ڕێک وەک پێشوو؛ ژمارەی جووڵەکان و ژمارەی ئەو فراوانی کردوون دەگەڕێنێتەوە.

Quick checkپشکنینی خێراHeuristic h2 is admissible and h2(n) ≥ h1(n) for every node. Which one should A* use? ⁦h2⁩ پەسەندکراوە و بۆ هەموو ⁦h2(n) ≥ h1(n)⁩. کامیان بەکار بهێنێت؟h1: smaller numbers are always safer⁦h1⁩: ژمارەی بچووکتر هەمیشە بێمەترسیترەh = 0: it is the most honest⁦h = 0⁩: ڕاستگۆترینەIt makes no differenceهیچ جیاوازییەک ناکاتh2: it is closer to the real cost, so A* expands fewer nodes⁦h2⁩: لە کۆستی ڕاستەقینە نزیکترە، بۆیە گەڕانی A* نۆدی کەمتر فراوان دەکات

A* by hand on the Lab 4 mazeگەڕانی A* بە دەست لەسەر لابیرینتی تاقیگەی 4

In Lab 4 the class first solved the maze on paper. Every cell gets f = h + g: g is the number of steps from the start A ("the letter G stands for the number of steps", as the lab note says in Kurdish), and h is the Manhattan distance to the goal B, counted vertically and horizontally. The start has g = 0 ("Initial Node = 0").

لە تاقیگەی 4دا پۆلەکە یەکەمجار لەسەر کاغەز چارەسەر کرد. هەر خانەیەک ⁦f = h + g⁩ وەردەگرێت: g ژمارەی هەنگاوەکانە لە سەرەتای Aـەوە («پیتی جی ئاماژەیە بۆ ژمارەی هەنگاوەکان»، وەک تێبینیی تاقیگەکە دەڵێت) و h تا ئامانجی B، بە ستوونی و ئاسۆیی ژمێردراو. سەرەتا ⁦g = 0⁩ـی هەیە («⁦Initial Node = 0⁩»).

The lab's table of h + g, redrawn from the photo and checked with the program.خشتەی ⁦h + g⁩ـی تاقیگەکە، لە وێنەکەوە سەرلەنوێ کێشراوە و بە پشکنراوە.CêIT

The lab's table, corrected (see the fixes on the next screen): h + g in every cell that A* reached, only h in the others. A = start (6, 0), B = goal (0, 11).خشتەکەی تاقیگەکە، ڕاستکراوە (ڕاستکردنەوەکان لە شاشەی داهاتوودان): ⁦h + g⁩ لە هەر خانەیەکدا کە پێی گەیشت، تەنیا h لەوانی تر. A = سەرەتا ⁦(6, 0)⁩، B = ئامانج ⁦(0, 11)⁩.
Rowڕیز	0	1	2	3	4	5	6	7	8	9	10	11
0	#	10+11	9+12	8+13	7+14	6+15	5+16	4+17	3+18	2+19	1+20	B
1	#	11+10	#	#	#	#	#	#	#	#	#	1
2	#	12+9	#	10+7	9+8	8+9	7+10	6+11	5+12	4+13	#	2
3	#	13+8	#	11+6	#	#	#	#	#	5+14	#	3
4	#	14+7	13+6	12+5	#	10	9	8	7+16	6+15	#	4
5	#	#	#	13+4	#	11	#	#	#	#	#	5
6	A	16+1	15+2	14+3	#	12	11	10	9	8	7	6

A* by hand on the Lab 4 mazeگەڕانی A* بە دەست لەسەر لابیرینتی تاقیگەی 4

Following the numbersبە دوای ژمارەکاندا

Phaseقۆناغ	Cells (h + g = f)خانەکان ⁦(h + g = f)⁩	What A* does چی دەکات
1	`(6,1) 16+1, (6,2) 15+2, (6,3) 14+3, (5,3) 13+4, (4,3) 12+5`	All f = 17: walk up from the start.هەموو ⁦f = 17⁩: لە سەرەتاوە بەرەو سەرەوە دەڕوات.
2	`(4,2) 13+6 = 19 · (3,3) 11+6 = 17`	Two choices. 17 < 19, so (3,3) goes first; (4,2) waits in OPEN (the lab calls it "forgotten").دوو هەڵبژاردە. ⁦17 < 19⁩، بۆیە ⁦(3,3)⁩ یەکەمجار دەچێت؛ ⁦(4,2)⁩ لە OPEN چاوەڕێ دەکات (تاقیگەکە پێی دەڵێت «لەبیرکراو»).
3	`(2,3) 10+7 … (2,9) 4+13`	Still f = 17, along row 2.هێشتا ⁦f = 17⁩، بە درێژایی ڕیزی 2.
4	`(3,9) 5+14 = 19`	The corridor turns away: f grows to 19. Now the smallest f in OPEN is 19, and the waiting (4,2) can be taken too.ڕاڕەوەکە لا دەدات: f بەرز دەبێتەوە بۆ ⁦19⁩. ئێستا بچووکترین f لە ⁦OPEN 19⁩ـە و ⁦(4,2)⁩ـی چاوەڕوانیش دەتوانرێت وەربگیرێت.
5	`(4,9) 6+15 = 21 · (4,8) 7+16 = 23`	"Task 1": the right-hand corridor gets worse; 23 is never expanded.«ئەرکی 1»: ڕاڕەوی لای ڕاست خراپتر دەبێت؛ ⁦23⁩ هەرگیز فراوان ناکرێت.
6	`(4,1) 14+7 … (0,10) 1+20`	"Task 2": all f = 21, up column 1 and along row 0, to the goal B.«ئەرکی 2»: هەموو ⁦f = 21⁩، بە ستوونی 1دا بۆ سەرەوە و بە درێژایی ڕیزی 0، تا ئامانجی B.

Fixes to the lab's hand traceڕاستکردنەوەی شوێنکەوتنە دەستییەکەی تاقیگەکە

The lab writes "(4, 1): 14 + 7 = 19". The sum is 21. The real program expands (4, 1) with f = 21, after both 19s.
"The path with heuristic 17 is chosen": 17 and 19 are f values (g + h), not heuristic values. And the text says the 17 path is "forgotten" where it means the 19 path.
The first trace lines are labelled Table[6, 0], [6, 1], [6, 2], but their numbers belong to the cells (6, 1), (6, 2), (6, 3). The start itself has h = 6 + 11 = 17 and f = 17, not 16.
"Both tasks will be done concurrently": A* never runs two paths at the same time. It always expands the one node with the smallest f, so it jumps back and forth between the two routes.
The sticker "H = heuristic = 16, G = 1" belongs to the cell (6, 1), not to the start.
The lab's table draws (3, 9) and (5, 5) as walls and shows only h at (4, 8) and (4, 9). In the maze both cells are open, and A* does reach (3, 9), (4, 9) and (4, 8) (5 + 14, 6 + 15 and 7 + 16), as the lab's own trace says. The table on the previous screen is corrected.

تاقیگەکە دەنووسێت «⁦(4, 1): 14 + 7 = 19⁩». کۆکەی ⁦21⁩ـە. ⁦(4, 1)⁩ بە ⁦f = 21⁩ فراوان دەکات، دوای هەردوو ⁦19⁩ـەکە.
«ڕێگای ⁦17⁩ هەڵدەبژێردرێت»: ⁦17⁩ و ⁦19⁩ نرخەکانی fن ⁦(g + h)⁩، نەک نرخی . هەروەها دەقەکە دەڵێت ڕێگای ⁦17⁩ «لەبیر دەکرێت» لە کاتێکدا مەبەستی ڕێگای ⁦19⁩ـە.
یەکەم دێڕەکانی شوێنکەوتنەکە بە ⁦Table[6, 0]⁩، ⁦[6, 1]⁩، ⁦[6, 2]⁩ ناونراون، بەڵام ژمارەکانیان هی خانەکانی ⁦(6, 1)⁩، ⁦(6, 2)⁩، ⁦(6, 3)⁩ن. خودی سەرەتا ⁦h = 6 + 11 = 17⁩ و ⁦f = 17⁩ـی هەیە، نەک ⁦16⁩.
«هەردوو ئەرکەکە پێکەوە ئەنجام دەدرێن»: هەرگیز دوو ڕێگا لە یەک کاتدا جێبەجێ ناکات. هەمیشە یەک فراوان دەکات کە بچووکترین fـی هەیە، بۆیە لە نێوان دوو ڕێگاکەدا دێت و دەچێت.
لکێنەری «⁦H = heuristic = 16⁩، ⁦G = 1⁩» هی خانەی ⁦(6, 1)⁩ـە، نەک هی سەرەتا.
خشتەکەی تاقیگەکە ⁦(3, 9)⁩ و ⁦(5, 5)⁩ وەک دیوار نیشان دەدات و لە ⁦(4, 8)⁩ و ⁦(4, 9)⁩دا تەنیا h نیشان دەدات. لە هەردوو خانەکە کراوەن و دەگاتە ⁦(3, 9)⁩، ⁦(4, 9)⁩ و (⁦4, 8) (5 + 14⁩، ⁦6 + 15⁩ و ⁦7 + 16⁩)، وەک شوێنکەوتنەکەی خودی تاقیگەکە دەڵێت. خشتەکەی شاشەی پێشوو ڕاست کراوەتەوە.

G, H and F on a grid with diagonal movesG، H و F لەسەر تۆڕێک بە جووڵەی لار

Many A* demos let you move diagonally too. Then a straight step usually costs 10 and a diagonal step 14 (about 10 × √2, kept as whole numbers). Each open cell shows three numbers: G, the cost from the start, H, the estimated cost to the end, and F = G + H. Explored (closed) cells and open cells are coloured differently.

زۆرێک لە نموونەکانی ڕێگەی جووڵەی لاریش دەدەن. ئەوکات هەنگاوێکی ڕاست زۆرجار کۆستی ⁦10⁩ـە و هەنگاوێکی لار ⁦14⁩ (نزیکەی ⁦10⁩ × √2، بۆ ئەوەی ژمارەکان تەواو بن). هەر خانەیەکی کراوە سێ ژمارە نیشان دەدات: G، کۆست لە سەرەتاوە، H، کۆستی خەمڵێنراو تا کۆتایی و ⁦F = G + H⁩. خانە پشکنراوەکان (داخراو) و خانە کراوەکان بە ڕەنگی جیاواز نیشان دەدرێن.

An original example of the G/H/F idea from the course's two screenshots.نموونەیەکی ڕەسەنی بیرۆکەی ⁦G/H/F⁩ لە دوو کۆرسەکەوە.CêIT

Two cells have F = 44 here. Many programs then prefer the one with the smaller H (30), because it is probably closer to the end. Note that with diagonal moves, plain Manhattan distance would overestimate; the H here counts diagonal steps as 14.

لێرەدا دوو خانە ⁦F = 44⁩یان هەیە. زۆرێک لە ئەوکات ئەوەیان پێ باشترە کە Hـی بچووکترە ⁦(30)⁩، چونکە لەوانەیە نزیکتر بێت لە کۆتایی. ئاگاداربە کە بە جووڵەی لار، ئاسایی زیاد دەخەمڵێنێت؛ H لێرەدا هەنگاوی لار بە ⁦14⁩ دەژمێرێت.

Lab 4: A* on the maze in Pythonتاقیگەی 4: گەڕانی A* لەسەر لابیرینتەکە بە Python

The Lab 4 program is the Lab 3 greedy program with three changes: it keeps g for every cell, it orders the heap by f = g + h, and it pushes a cell again when it finds a shorter route to it. Below is the lab program, cleaned and corrected. The maze uses a space for an open cell.

تاقیگەی 4 هەمان تاقیگەی 3ـە بە سێ گۆڕانکاری: g بۆ هەر خانەیەک هەڵدەگرێت، بە پێی ⁦f = g + h⁩ ڕیز دەکات و کاتێک ڕێگایەکی کورتتر بۆ خانەیەک دەدۆزێتەوە دووبارە دەیخاتە ناوەوە. لە خوارەوە تاقیگەکە پاککراوە و ڕاستکراوەیە. بۆشایی بۆ خانەی کراوە بەکار دەهێنێت.

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

import heapq


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

    def __repr__(self):
        return f"({self.x}, {self.y})"


def manhattan(current, end):
    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
    frontier = [(manhattan(start, end), count, start)]  # f(start) = 0 + h(start)
    parent = {start: None}
    g_score = [[float('inf') for _ in row] for row in maze]  # steps from the start
    g_score[start.x][start.y] = 0
    closed = [[False for _ in row] for row in maze]          # already expanded?
    explored = []

    while frontier:
        _, _, current = heapq.heappop(frontier)   # the smallest f = g + h
        if closed[current.x][current.y]:
            continue                              # an out-of-date copy
        if current.x == end.x and current.y == end.y:
            return backtrack(parent, current), explored  # goal SELECTED: stop

        closed[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:
                new_g = g_score[current.x][current.y] + 1   # one more step
                if new_g < g_score[x][y]:                   # a better route to (x, y)
                    g_score[x][y] = new_g
                    nxt = Point(x, y)
                    f = new_g + manhattan(nxt, end)         # f = g + h
                    count += 1
                    heapq.heappush(frontier, (f, count, nxt))
                    parent[nxt] = current                   # remember where we came from

    return None, explored


def backtrack(parent, end):
    path = []
    while end is not None:
        path.append(end)
        end = parent[end]
    return path[::-1]


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("Path not found. Cells expanded:", len(explored))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1-14

Point and manhattan() are the same as in Lab 3.

Point و manhattan() وەک تاقیگەی 3ن.

Lineدێڕی 21

The start enters with f = 0 + h(start) = 17.

سەرەتا بە ⁦f = 0 + h(start) = 17⁩ دەچێتە ناوەوە.

Lineدێڕی 23-24

g_score is a grid of infinity: "not reached yet". float('inf') is larger than every number, so the first real route always wins (infinity in Python). The start gets g = 0. (The lab calls this grid seen.)

g_score تۆڕێکە لە : «هێشتا نەگەیشتراوە». float('inf') لە هەموو ژمارەیەک گەورەترە، بۆیە یەکەم ڕێگای ڕاستەقینە هەمیشە دەباتەوە (بێسنوور لە Pythonـدا). سەرەتا ⁦g = 0⁩ وەردەگرێت. (تاقیگەکە ئەم تۆڕە بە seen ناو دەبات.)

Lineدێڕی 25

closed is the CLOSED list, added so that an out-of-date copy is skipped.

closed لیستی CLOSEDـە، زیاد کراوە بۆ ئەوەی کۆپییەکی کۆن تێپەڕێنرێت.

Lineدێڕی 29-33

Take out the smallest f. The goal test is here, when the goal is selected.

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

Lineدێڕی 41

seen[current.x][current.y] in the lab: how far you have walked to the current cell; one more step costs 1.

seen[current.x][current.y] لە تاقیگەکەدا: تا خانەی ئێستا چەندت ڕۆیشتووە؛ هەنگاوێکی تر کۆستی 1ـە.

Lineدێڕی 42-43

"We found a better route": only then is the neighbour updated.

«ڕێگایەکی باشترمان دۆزییەوە»: تەنیا ئەوکات دراوسێکە نوێ دەکرێتەوە.

Lineدێڕی 45-47

f = steps so far + a simple guess of the distance left; push it with a new count.

f = هەنگاوەکانی تا ئێستا + مەزەندەیەکی سادەی دووریی ماوە؛ لەگەڵ ژمارەیەکی نوێ بیخە ناوەوە.

Lineدێڕی 48

"Think of parent as a notebook": it writes down where you came from, so the path can be traced back.

«parent وەک دەفتەرێک بیر لێ بکەرەوە»: دەنووسێت لە کوێوە هاتوویت، بۆ ئەوەی ڕێگاکە بەرەو دواوە شوێن بکەوێت.

What was fixed in the lab codeچی لە کۆدی تاقیگەکەدا ڕاست کرایەوە

The lab code has no CLOSED check: a cell pushed twice is also expanded twice. With Manhattan distance on this grid that is harmless, but the usual "skip if already expanded" test is added.
Comment slips: "# x = 1 + 1 = 2" is about y; "StarPoint" means the start point; the start's f is 17, not 16.
"Path length" printed the number of cells (22), not moves (21). The program now prints both.
The grid that stores g was called seen, which sounds like True/False. It is renamed g_score.

کۆدی تاقیگەکە پشکنینی CLOSEDـی نییە: خانەیەک کە دوو جار خراوەتە ناوەوە دوو جاریش فراوان دەکرێت. بە لەسەر ئەم تۆڕە زیانی نییە، بەڵام تاقیکردنەوە ئاساییەکەی «ئەگەر پێشتر فراوان کراوە تێیپەڕێنە» زیاد کرا.
هەڵەی : «⁦# x = 1 + 1 = 2⁩» دەربارەی yـە؛ «StarPoint» واتە خاڵی سەرەتا؛ fـی سەرەتا ⁦17⁩ـە، نەک ⁦16⁩.
«⁦Path length⁩» ژمارەی خانەکان ⁦(22)⁩ی چاپ دەکرد، نەک جووڵەکان ⁦(21)⁩. ئێستا هەردووکیان چاپ دەکات.
ئەو تۆڕەی g هەڵدەگرێت ناوی seen بوو، کە وەک ⁦True/False⁩ دەنگ دەداتەوە. ناوەکەی گۆڕدرا بۆ g_score.

Measured on this maze, counting the goal: A* takes 32 cells out of the frontier, breadth-first search 38 and greedy search 34, but greedy's path is 12 moves longer. On the Lab 3 maze A* finds the same 24-cell path as greedy search.

پێوانەکراو لەسەر ئەم ، لەگەڵ ئامانجەکە: ⁦32⁩ خانە لە دەردەهێنێت، ⁦38⁩ و ⁦34⁩، بەڵام ڕێگای ⁦12⁩ جووڵە درێژترە. لەسەر تاقیگەی 3، هەمان ڕێگای ⁦24⁩ خانەیی دەدۆزێتەوە.

The two routes drawn in the lab: A* (21 moves) and greedy best-first search (33 moves).دوو ڕێگاکەی لە تاقیگەکەدا کێشران: (⁦21⁩ جووڵە) و (⁦33⁩ جووڵە).CêIT

Quick checkپشکنینی خێراIn the code, when is a neighbour pushed into the heap?لە کۆدەکەدا، دراوسێیەک کەی دەخرێتە ناو ؟When the new g is smaller than the g stored for that cellکاتێک gـی نوێ لەو gـە بچووکترە کە بۆ ئەو خانەیە هەڵگیراوەOnly if its h is smaller than the current hتەنیا ئەگەر hـەکەی لە hـی ئێستا بچووکتر بێتEvery time it is seenهەموو جارێک کە دەبینرێتOnly if it is the goalتەنیا ئەگەر ئامانج بێت

A* on a road map: cost and pathگەڕانی A* لەسەر نەخشەی ڕێگاکان: کۆست و ڕێگا

In a maze every step costs 1. On a road map every road has its own length, so the graph is a weighted graph. The map below uses real town names, but it is a simplified practice map: it is not to scale, and all its distances are made up. They are not the real road or straight-line distances. The program below returns both the cost and the path. The heuristic is the straight-line distance to Halabja: a straight line is never longer than a road, so it never overestimates (the made-up numbers were checked to keep this true).

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

Real town names on a simplified practice map: not to scale, and all distances are made up (they are not the real road distances).ناوی ڕاستەقینەی شارەکان لەسەر نەخشەیەکی سادەکراوی ڕاهێنان: بە ڕێژەی ڕاستەقینە نەکێشراوە و هەموو دوورییەکان دەستکردن (دووریی ڕاستەقینەی ڕێگاکان نین).CêIT

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

import heapq

# A practice map (not to scale; made-up distances in km). Each road works both ways.
ROADS = [
    ("Slemani", "Arbat", 24), ("Arbat", "Said Sadiq", 26),
    ("Said Sadiq", "Halabja", 22), ("Said Sadiq", "Khurmal", 23),
    ("Khurmal", "Halabja", 18), ("Slemani", "Penjwen", 62),
    ("Penjwen", "Khurmal", 34), ("Slemani", "Darbandikhan", 60),
    ("Darbandikhan", "Halabja", 40), ("Slemani", "Qaradagh", 32),
    ("Qaradagh", "Darbandikhan", 34), ("Arbat", "Darbandikhan", 36),
]

# h(n): straight-line distance from each town to Halabja (never more than the road)
STRAIGHT_LINE = {
    "Slemani": 68, "Arbat": 45, "Said Sadiq": 21, "Khurmal": 17,
    "Penjwen": 46, "Darbandikhan": 32, "Qaradagh": 60, "Halabja": 0,
}


def roads_to_graph(roads):
    graph = {}
    for a, b, km in roads:
        graph.setdefault(a, {})[b] = km   # a -> b
        graph.setdefault(b, {})[a] = km   # b -> a
    return graph


def a_star(graph, h, start, goal):
    """Return (cost, path, expanded) for the cheapest path from start to goal."""
    frontier = [(h[start], 0, start)]   # (f, g, town); the smallest f comes out first
    g = {start: 0}                      # best known cost from the start
    parent = {start: None}
    closed = set()                      # towns already expanded
    expanded = []
    while frontier:
        f, cost, town = heapq.heappop(frontier)
        if town in closed:
            continue                    # an older, more expensive copy
        if town == goal:                # stop when the goal is SELECTED
            path = []
            while town is not None:
                path.append(town)
                town = parent[town]
            return cost, path[::-1], expanded
        closed.add(town)
        expanded.append(town)
        for nxt, km in graph[town].items():
            new_g = cost + km
            if nxt not in closed and new_g < g.get(nxt, float("inf")):
                g[nxt] = new_g          # a cheaper way to reach nxt
                parent[nxt] = town
                heapq.heappush(frontier, (new_g + h[nxt], new_g, nxt))
    return None, [], expanded           # no path


if __name__ == "__main__":
    graph = roads_to_graph(ROADS)
    cost, path, expanded = a_star(graph, STRAIGHT_LINE, "Slemani", "Halabja")
    print("Expanded:", ", ".join(expanded))
    print("Path:", " -> ".join(path))
    print("Cost:", cost, "km")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 4-11

Each road is a tuple (town, town, km). Every road works both ways.

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

Lineدێڕی 14-17

h(n): never more than the real road distance, and 0 at the goal.

⁦h(n)⁩: هەرگیز لە دووریی ڕاستەقینەی ڕێگا زیاتر نییە و لە ئامانجدا 0ـە.

Lineدێڕی 20-25

Build a dictionary of dictionaries: graph[a][b] = km, in both directions.

لە دروست بکە: ⁦graph[a][b] = km⁩، بە هەردوو ئاڕاستەدا.

Lineدێڕی 30

Heap entries are (f, g, town). Keeping g in the entry means we know the cost when the goal comes out.

تۆمارەکانی بریتین لە ⁦(f, g, town)⁩. هەڵگرتنی g لە تۆمارەکەدا واتە کاتێک ئامانج دەردەچێت کۆستەکەی دەزانین.

Lineدێڕی 37-38

A town can be in the heap more than once; a closed town's older copy is skipped.

شارێک دەشێت زیاتر لە جارێک لە بێت؛ کۆپیی کۆنی شارێکی داخراو تێدەپەڕێنرێت.

Lineدێڕی 39-44

Goal selected: rebuild the path from the parents and return (cost, path, expanded).

ئامانج هەڵبژێردرا: ڕێگاکە لە باوکەکانەوە دووبارە دروست بکەرەوە و ⁦(cost, path, expanded)⁩ بگەڕێنەوە.

Lineدێڕی 48-52

g(next) = g(town) + km. Only a cheaper way updates g and the parent, and pushes f = g + h.

⁦g(next) = g(town) + km⁩. تەنیا ڕێگایەکی هەرزانتر g و باوک نوێ دەکاتەوە و ⁦f = g + h⁩ دەخاتە ناوەوە.

Lineدێڕی 56

if __name__ == "__main__": runs the demo only when this file is run directly, so other files can import a_star.

if __name__ == "__main__": نموونەکە تەنیا کاتێک جێبەجێ دەکات کە ئەم فایلە ڕاستەوخۆ جێبەجێ بکرێت، بۆ ئەوەی فایلەکانی تر بتوانن a_star هاوردە بکەن.

About the course's graph programدەربارەی بەرنامەی گرافی کۆرسەکە

The course's example graph and its two pictures were copied from a website, so CêIT uses its own map instead. Its heuristic was also a bad example: it overestimated at H (h = 7, but the cheapest way from H costs 6) and was not consistent on the roads D→F and H→I.
Its comment says "the goal node must be admissible". It is the heuristic that must be admissible, with h(goal) = 0.
The .pages copy has a curly quote in print(f”Total path cost…, which is a SyntaxError; a stale comment "subtract the heuristic value" no longer matched the code.
Its type hint tuple[int, list[str]] needs Python 3.9 or newer.

نموونەی کۆرسەکە و دوو وێنەکەی لە ماڵپەڕێکەوە کۆپی کرابوون، بۆیە CêIT نەخشەی خۆی بەکار دەهێنێت. ئەویش نموونەیەکی خراپ بوو: لە H زیادی دەخەمڵاند (⁦h = 7⁩، بەڵام هەرزانترین ڕێگا لە Hـەوە 6ـە) و لەسەر ڕێگاکانی D→F و H→I هاوئاهەنگ نەبوو.
دەڵێت « ئامانج دەبێت پەسەندکراو بێت». ئەوە کە دەبێت پەسەندکراو بێت، بە ⁦h(goal) = 0⁩.
کۆپیی .pages لە print(f”Total path cost…دا نیشانەی وتەی چەماوە (”) هەیە، کە SyntaxErrorـە؛ کۆن «نرخی دەربکە» چیتر لەگەڵ کۆدەکە ناگونجا.
ئاماژەی جۆرەکەی tuple[int, list[str]] پێویستی بە ⁦3.9⁩ یان نوێترە.

One family: BFS, uniform-cost, greedy and Aیەک خێزان: BFS، کەمترین کۆست، چاوچنۆک و A

These searches share one loop: take the best node out of the frontier, stop if it is the goal, otherwise expand it. They differ only in how the frontier is ordered.

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

Searchگەڕان	Frontier ordered by بە پێی چی ڕیز دەکرێت	Finds the cheapest path?هەرزانترین ڕێگا دەدۆزێتەوە؟	On the town mapلەسەر نەخشەی شارەکان
Breadth-first search	first in, first out (a queue)یەکەم هاتوو، یەکەم دەرچوو ()	Only if every step costs the sameتەنیا ئەگەر هەموو هەنگاوێک هەمان کۆستی هەبێت	fewest roads: 2 roads, 100 kmکەمترین ڕێگا: 2 ڕێگا، ⁦100⁩ کم
Uniform-cost search (Dijkstra) ⁦(Dijkstra)⁩	g(n)	Yesبەڵێ	72 km, expands 6 towns⁦72⁩ کم، 6 شار فراوان دەکات
Greedy best-first search	h(n)	Noنەخێر	100 km, expands 2 towns⁦100⁩ کم، 2 شار فراوان دەکات
A* search	g(n) + h(n)	Yes, with an admissible hبەڵێ، بە hـی پەسەندکراو	72 km, expands 3 towns⁦72⁩ کم، 3 شار فراوان دەکات

Uniform-cost search is explained, with its own code, in more uninformed search; breadth-first search is in depth-first and breadth-first search. In the next lesson, search practice, the town map is solved with breadth-first search too.

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

The course's lab plan also recommends a video that animates A*, Dijkstra (uniform-cost search), breadth-first search and depth-first search, so you can compare how each one searches: Path-finding Visualization Comparison (YouTube).

پلانی تاقیگەکانی کۆرسەکە ڤیدیۆیەکیش پێشنیار دەکات کە ، Dijkstra ()، و بە وێنەی جووڵاو نیشان دەدات، بۆ ئەوەی بەراورد بکەیت هەریەکەیان چۆن دەگەڕێت: ⁦Path-finding Visualization Comparison (YouTube)⁩.

Quick checkپشکنینی خێراWhich search orders its frontier by g(n) + h(n)?کام گەڕان بە ⁦g(n) + h(n)⁩ ڕیز دەکات؟Greedy best-first searchگەڕانی چاوچنۆکانەA* searchگەڕانی A*Uniform-cost searchگەڕانی کەمترین کۆستBreadth-first searchگەڕانی پانایی

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

Mistakeهەڵە	What happensچی ڕوو دەدات	Fixچارەسەر
Testing for the goal when it is generated کاتێک ئامانج دروست دەکرێت	A* can return an expensive path that was found early. دەشێت ڕێگایەکی گران بگەڕێنێتەوە کە زوو دۆزرایەوە.	Test when the goal is taken out of OPEN.کاتێک ئامانج لە OPEN دەردەهێنرێت بیپشکنە.
A heuristic that overestimates کە زیاد دەخەمڵێنێت	A* can return a longer path (S → G, cost 10 instead of 6). دەشێت ڕێگایەکی درێژتر بگەڕێنێتەوە (S → G، کۆستی ⁦10⁩ لەبری ⁦6⁩).	Check h(n) ≤ real cost for every node.بۆ هەموو ⁦h(n)⁩ ≤ کۆستی ڕاستەقینە بپشکنە.
Writing the consistency rule backwardsنووسینی یاسای هاوئاهەنگی بە پێچەوانەوە	You test the wrong thing.شتێکی هەڵە تاقی دەکەیتەوە.	`h(n) ≤ c(n, n′) + h(n′)`
Never updating a node when a cheaper path is foundهەرگیز نوێنەکردنەوەی کاتێک ڕێگایەکی هەرزانتر دەدۆزرێتەوە	The parent keeps the worse path.باوکەکە ڕێگا خراپترەکە دەهێڵێتەوە.	If the new g is smaller: update g, f and the parent, push again.ئەگەر gـی نوێ بچووکتر بوو: g، f و باوک نوێ بکەرەوە و دووبارە بیخە ناوەوە.
Using Manhattan distance with diagonal movesبەکارهێنانی لەگەڵ جووڵەی لار	h overestimates, so A* may not be optimal.h زیاد دەخەمڵێنێت، بۆیە لەوانەیە باشترین نەبێت.	Use a distance that counts diagonal steps (10/14).دوورییەک بەکار بهێنە کە هەنگاوی لار دەژمێرێت ⁦(10/14)⁩.
Counting cells as stepsژماردنی خانەکان وەک هەنگاو	"Path length 22" for a 21-move path.«⁦Path length 22⁩» بۆ ڕێگایەکی ⁦21⁩ جووڵەیی.	Moves = cells − 1.جووڵەکان = خانەکان − 1.

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

ExerciseڕاهێنانIs the corrected table consistent?ئایا خشتە ڕاستکراوەکە هاوئاهەنگە؟

Take the worked example with the corrected value h(D) = 2 (S 5, A 3, B 4, C 2, D 2, G 0). Check the rule h(n) ≤ c(n, n′) + h(n′) on every edge. Which edge breaks it, and does it matter?

نموونە شیکراوەکە بە نرخە ڕاستکراوەکەی ⁦h(D) = 2⁩ وەربگرە (⁦S 5⁩، ⁦A 3⁩، ⁦B 4⁩، ⁦C 2⁩، ⁦D 2⁩، ⁦G 0⁩). یاسای ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′) لەسەر هەموو بپشکنە. کام تێکی دەدات و ئایا گرنگە؟

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

$S \to A$ : 5 ≤ 1 + 3 = 4 is false. All other edges pass: $S \to G$ 5 ≤ 10, $A \to B$ 3 ≤ 6, $A \to C$ 3 ≤ 3, $B \to D$ 4 ≤ 7, $C \to D$ 2 ≤ 5, $C \to G$ 2 ≤ 4, $D \to G$ 2 ≤ 2. So the table is admissible but not consistent. It does no harm here, because S is the start and no path ever comes back to it; with h(S) = 4 the table would be consistent too.

$S \to A$ : ⁦5 ≤ 1 + 3 = 4⁩ هەڵەیە. هەموو تر سەردەکەون: $S \to G$ ⁦5 ≤ 10⁩، $A \to B$ ⁦3 ≤ 6⁩، $A \to C$ ⁦3 ≤ 3⁩، $B \to D$ ⁦4 ≤ 7⁩، $C \to D$ ⁦2 ≤ 5⁩، $C \to G$ ⁦2 ≤ 4⁩، $D \to G$ ⁦2 ≤ 2⁩. کەواتە خشتەکە پەسەندکراوە بەڵام هاوئاهەنگ نییە. لێرەدا زیانی نییە، چونکە S سەرەتایە و هیچ ڕێگایەک ناگەڕێتەوە بۆی؛ بە ⁦h(S) = 4⁩ خشتەکە هاوئاهەنگیش دەبوو.

ExerciseڕاهێنانOne line, three algorithmsیەک دێڕ، سێ ئەلگۆریزم

In town_astar.py, line 52 pushes (new_g + h[nxt], new_g, nxt). Change the first number to h[nxt] (greedy best-first search), then to new_g (uniform-cost search). Run each version. What path and cost do you get, and how many towns are expanded?

لە town_astar.pyدا دێڕی ⁦52⁩ (new_g + h[nxt], new_g, nxt) دەخاتە ناوەوە. ژمارەی یەکەم بگۆڕە بۆ h[nxt] ()، پاشان بۆ new_g (). هەر وەشانێک جێبەجێ بکە. چ ڕێگا و کۆستێک وەردەگریت و چەند شار فراوان دەکرێن؟

Hintئاماژە

Only the priority changes; the rest of the loop stays the same.

تەنیا پێشینەکە دەگۆڕێت؛ باقیی وەک خۆی دەمێنێتەوە.

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

With h[nxt] (greedy)بە ⁦h[nxt]⁩ (چاوچنۆک)

Expanded: Slemani, Darbandikhan
Path: Slemani -> Darbandikhan -> Halabja
Cost: 100 km

With new_g (uniform-cost)بە ⁦new_g⁩ (کەمترین کۆست)

Expanded: Slemani, Arbat, Qaradagh, Said Sadiq, Darbandikhan, Penjwen
Path: Slemani -> Arbat -> Said Sadiq -> Halabja
Cost: 72 km

Greedy rushes to Darbandikhan (h = 32 looks best) and pays 100 km. Uniform-cost search finds the 72 km route but expands six towns. A* finds the same 72 km route after expanding only three.

بە پەلە دەچێت بۆ دەربەندیخان (⁦h = 32⁩ باشترین دیار دەدات) و ⁦100⁩ کم دەدات. ڕێگا ⁦72⁩ کمییەکە دەدۆزێتەوە بەڵام شەش شار فراوان دەکات. هەمان ڕێگای ⁦72⁩ کم دەدۆزێتەوە دوای تەنیا سێ شار.

ExerciseڕاهێنانRead the hand tableخشتە دەستییەکە بخوێنەوە

In the Lab 4 hand table, cell (2, 6) shows 7 + 10. What are h, g and f? Why is (4, 8) never expanded?

لە خشتە دەستییەکەی تاقیگەی 4دا، خانەی ⁦(2, 6) 7 + 10⁩ نیشان دەدات. h، g و f چەندن؟ بۆچی ⁦(4, 8)⁩ هەرگیز فراوان ناکرێت؟

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

h = 7 (2 rows + 5 columns from (0, 11)), g = 10 steps from A, f = 17. Cell (4, 8) has f = 7 + 16 = 23, but the goal is taken out of OPEN with f = 21 first, so A* stops before it reaches 23.

⁦h = 7 (2⁩ ڕیز + 5 ستوون لە ⁦(0, 11)⁩ـەوە)، ⁦g = 10⁩ هەنگاو لە Aـەوە، ⁦f = 17⁩. خانەی ⁦(4, 8) f = 7 + 16 = 23⁩ـی هەیە، بەڵام ئامانج یەکەمجار بە ⁦f = 21⁩ لە OPEN دەردەهێنرێت، بۆیە پێش ئەوەی بگاتە ⁦23⁩ دەوەستێت.

Quick checkپشکنینی خێراWhich statement about A* is true?کام ڕستە دەربارەی ڕاستە؟It is optimal with any heuristic.بە هەر پێوەرێک باشترینە.It ignores the step costs.کۆستەکانی هەنگاو پشتگوێ دەخات.With an admissible heuristic it returns an optimal path.بە پێوەرێکی پەسەندکراو باشترین ڕێگا دەگەڕێنێتەوە.It never needs more memory than depth-first search.هەرگیز بیرگەی زیاتری لە گەڕانی قووڵایی پێویست نییە.

Summaryپوختە

A* expands the node with the smallest f(n) = g(n) + h(n): the cost so far plus the estimated cost to the goal.
It stops when a goal is taken out of OPEN; a cheaper path to a node updates its g, f and parent.
Admissible: h(n) ≤ real cost. Consistent: h(n) ≤ c(n, n′) + h(n′). With such a heuristic A* is optimal; it is complete with a finite branching factor and step costs ≥ ε > 0.
The notes' example has h(D) = 6, which overestimates; h(D) = 2 fixes it.
Better (bigger, still admissible) heuristics expand fewer nodes: Manhattan distance beats misplaced tiles on the 8-puzzle.
On the Lab 4 maze A* finds 21 moves where greedy needs 33; on the town map it finds 72 km after expanding three towns.

ئەو فراوان دەکات کە بچووکترین ⁦f(n) = g(n) + h(n)⁩ـی هەیە: کۆستی تا ئێستا لەگەڵ کۆستی خەمڵێنراو تا ئامانج.
کاتێک ئامانج لە OPEN دەردەهێنرێت دەوەستێت؛ ڕێگایەکی هەرزانتر بۆ g، f و باوکەکەی نوێ دەکاتەوە.
پەسەندکراو: ⁦h(n)⁩ ≤ کۆستی ڕاستەقینە. هاوئاهەنگ: ⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′). بە وەها باشترینە؛ بە سنووردار و ≥ ε > 0 تەواوە.
نموونەکەی تێبینییەکان ⁦h(D) = 6⁩ـی هەیە کە زیاد دەخەمڵێنێت؛ ⁦h(D) = 2⁩ چاکی دەکاتەوە.
(گەورەتر، بەڵام هێشتا پەسەندکراو) کەمتر فراوان دەکەن: لە یاریی 8-پارچەدا لە پارچە شوێنهەڵەکان باشترە.
لەسەر تاقیگەی 4، ⁦21⁩ جووڵە دەدۆزێتەوە لە کاتێکدا ⁦33⁩ی پێویستە؛ لەسەر نەخشەی شارەکان دوای سێ شار ⁦72⁩ کم دەدۆزێتەوە.

Review questionsپرسیارەکانی پێداچوونەوە

What do g(n), h(n) and f(n) mean?⁦g(n)⁩، ⁦h(n)⁩ و ⁦f(n)⁩ واتای چییە؟

g: the cost from the start to n. h: the estimated cost from n to the goal. f = g + h: the estimated cost of the cheapest solution through n.

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

Why must A* wait until the goal is taken out of OPEN?بۆچی گەڕانی A* دەبێت چاوەڕێ بکات تا ئامانج لە OPEN دەردەهێنرێت؟

The goal may first be generated through an expensive path (S → G with cost 10 in the example). Only when it has the smallest f is that path guaranteed to be the cheapest.

دەشێت ئامانج یەکەمجار لە ڕێگایەکی گرانەوە دروست بکرێت (S → G بە کۆستی ⁦10⁩ لە نموونەکەدا). تەنیا کاتێک بچووکترین fـی هەیە، گەرەنتی هەیە کە ئەو ڕێگایە هەرزانترینە.

Write the consistency rule correctly.یاسای هاوئاهەنگی بە دروستی بنووسە.

h(n) ≤ c(n, n′) + h(n′) for every successor n′ of n.

⁦h(n) ≤ c(n, n⁩′) + ⁦h(n⁩′) بۆ هەموو منداڵێکی n′ـی n.

What does A* become with h(n) = 0?گەڕانی A* بە ⁦h(n) = 0⁩ دەبێت بە چی؟

Uniform-cost search (Dijkstra's algorithm): it orders the frontier by g(n) only.

( Dijkstra): تەنیا بە ⁦g(n)⁩ ڕیز دەکات.

Videoڤیدیۆ

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

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

A* Search: How Your Map Applications Find Shortest RoutesReducible · Englishئینگلیزی · 101K viewsبینین · 4.2K likesلایک · Partبەشی 0:00–14:45 (ofلە 16:16)
How A* joins uniform-cost search (cost so far) and greedy search (guess to the goal), and why an admissible heuristic gives the shortest route.
چۆن دوو شت تێکەڵ دەکات: (کۆستی تا ئێستا) و (مەزەندە تا ئامانج)، هەروەها بۆچی بە دەدۆزرێتەوە.
Watch 0:00-14:45: greedy search, uniform-cost search, A* as a mix of both, and why an admissible heuristic gives the shortest route. With a closed list A* also needs a consistent heuristic (see 'Why an admissible heuristic gives the optimal path').
لە ⁦0:00⁩ تا ⁦14:45⁩ سەیر بکە: ، ، وەک تێکەڵەیەک لە هەردووکیان، هەروەها بۆچی بە دەدۆزرێتەوە. ئەگەر closed list بەکاربهێنێت، پێویستیشی بە دەبێت (بڕوانە «بۆچی باشترین ڕێگا دەدات»).

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

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

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

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

Search Practice: Midterm-Style Tasksڕاهێنانی گەڕان: ئەرکی وەک تاقیکردنەوەی نیوەی وەرز

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

A* Searchگەڕانی A*

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

A*: the cost so far plus a guessگەڕانی A*: کۆستی تا ئێستا لەگەڵ مەزەندەیەک

The evaluation function f(n) = g(n) + h(n)کرداری هەڵسەنگاندن ⁦f(n) = g(n) + h(n)⁩

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

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

The trace: OPEN after every roundشوێنکەوتن: OPEN دوای هەر خولێک

Is this heuristic admissible?ئایا ئەم پێوەرە پەسەندکراوە؟

Points to rememberخاڵە گرنگەکان

Admissible and consistent heuristicsپێوەرە پەسەندکراوەکان و پێوەرە هاوئاهەنگەکان

Why an admissible heuristic gives the optimal pathبۆچی پێوەرێکی پەسەندکراو باشترین ڕێگا دەدات

Where good heuristics come fromپێوەرە باشەکان لە کوێوە دێن

A* by hand on the Lab 4 mazeگەڕانی A* بە دەست لەسەر لابیرینتی تاقیگەی 4

Following the numbersبە دوای ژمارەکاندا

G, H and F on a grid with diagonal movesG، H و F لەسەر تۆڕێک بە جووڵەی لار

Lab 4: A* on the maze in Pythonتاقیگەی 4: گەڕانی A* لەسەر لابیرینتەکە بە Python

A* on a road map: cost and pathگەڕانی A* لەسەر نەخشەی ڕێگاکان: کۆست و ڕێگا

One family: BFS, uniform-cost, greedy and A*یەک خێزان: BFS، کەمترین کۆست، چاوچنۆک و A*

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

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

Summaryپوختە

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

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

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

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

A: the cost so far plus a guessگەڕانی A: کۆستی تا ئێستا لەگەڵ مەزەندەیەک

One family: BFS, uniform-cost, greedy and Aیەک خێزان: BFS، کەمترین کۆست، چاوچنۆک و A