Chapterبەش 4 · Lectureوانە 4.4
Depth-Limited, Uniform-Cost, Iterative Deepening and Bidirectional Searchگەڕانی قووڵایی سنووردار، گەڕانی کەمترین کۆست، گەڕانی قووڵکردنەوەی پلەبەپلە و گەڕانی دووئاڕاستە
Four more uninformed strategies: depth-limited search (cutoff and failure), iterative deepening, uniform-cost search with a priority queue and runnable Python code, and bidirectional search — then one table that compares all six uninformed algorithms.
چوار ستراتیژیی تری بێزانیاری: (cutoff و failure)، ، بە و کۆدی کە کار دەکات، هەروەها . پاشان یەک خشتە کە هەموو شەش بێزانیارییەکە بەراورد دەکات.
What you will learnچی فێر دەبیت
- Explain depth-limited search and the difference between cutoff and failure.
- Trace iterative deepening round by round and explain why its repeated work is small.
- Run uniform-cost search with a priority queue and explain why it can prefer more steps for a lower cost.
- Describe bidirectional search, its saving b^(d/2) and its conditions.
- Compare BFS, UCS, DFS, DLS, IDDFS and bidirectional search by completeness, optimality, time and space.
- و جیاوازیی نێوان cutoff و failure ڕوون بکەیتەوە.
- جار بە جار پەیڕەو بکەیت و ڕوونی بکەیتەوە بۆچی کارە دووبارەکەی کەمە.
- بە جێبەجێ بکەیت و ڕوونی بکەیتەوە بۆچی دەکرێت هەنگاوی زیاتر بۆ کۆستی کەمتر هەڵبژێرێت.
- ، قازانجەکەی b^(d/2) و مەرجەکانی وەسف بکەیت.
- BFS، UCS، DFS، DLS، IDDFS و بە ، ، کات و بەراورد بکەیت.
Four more ways to search blindlyچوار ڕێگای تری گەڕانی کوێرانە
Uninformed search algorithms are a kind of problem-solving strategy used in computer science and . They have no extra information about the problem space; they explore the possible solutions blindly and rely only on the structure of the tree or graph.
بێزانیارییەکانی گەڕان جۆرێکن لە ستراتیژیی چارەسەرکردنی کێشەکان کە لە زانستی کۆمپیوتەر و بەکار دێن. هیچ زانیارییەکی زیادەیان دەربارەی فەزای کێشەکە نییە؛ بە کوێرانە چارەسەرە ئەگەرییەکان دەپشکنن و تەنها پشت بە پێکهاتەی یان دەبەستن.
The previous lessons left two problems. Depth-first search uses little memory but can get lost on an endless path. Breadth-first search is complete but needs a lot of memory, and it counts steps, not costs. This lesson adds four strategies: depth-limited search and iterative deepening (DFS that cannot get lost), uniform-cost search (cheapest path first) and bidirectional search (search from both ends). Like the others, they are used in pathfinding, puzzle solving and other decision-making tasks where nothing is known about the solution in advance.
وانەکانی پێشوو دوو کێشەیان بەجێهێشت. کەم بەکار دەهێنێت بەڵام لەوانەیە لە ڕێگەیەکی بێکۆتادا ون بێت. هەیە بەڵام زۆری پێویستە و هەنگاو دەژمێرێت نەک کۆست. ئەم وانەیە چوار ستراتیژی زیاد دەکات: و (DFS کە ون نابێت)، (سەرەتا هەرزانترین ڕێگە) و (گەڕان لە هەردوو سەرەوە). وەک ئەوانی تر، لە دۆزینەوەی ڕێگە، چارەسەرکردنی مەتەڵ و کاری تری بڕیاردان بەکار دێن کە پێشوەختە هیچ شتێک دەربارەی چارەسەرەکە نەزانراوە.
Depth-limited searchگەڕانی قووڵایی سنووردار
Depth-first search with a depth limit ℓ. It cannot get lost on an endless path, but it fails if the shallowest goal is deeper than ℓ; it then reports 'cutoff' rather than 'failure'.
لەگەڵ ℓ. لە ڕێگایەکی بێکۆتادا ون نابێت، بەڵام ئەگەر نزیکترین ئامانج لە ℓ قووڵتر بێت سەرناکەوێت؛ ئەو کاتە «cutoff» ڕادەگەیەنێت نەک «failure».
Depth-limited search (DLS) is depth-first search with a fixed ℓ. Nodes at depth ℓ are treated as if they had no children, so the search can never run down an endless path.
(DLS) کە سنوورێکی جێگیری بۆ قووڵایی هەیە: ℓ. ئەو لە ℓدان وەک ئەوە سەیر دەکرێن کە منداڵیان نییە، بۆیە گەڕانەکە هەرگیز ناتوانێت بە ڕێگەیەکی بێکۆتادا بڕوات.
The lecture says DLS can end with two kinds of failure:
وانەکە دەڵێت DLS دەکرێت بە دوو جۆری سەرنەکەوتن کۆتایی بێت:
- Standard failure: the problem does not have any solution at all.
- Cutoff failure: there is no solution within the given depth limit — but there might be one deeper.
- سەرنەکەوتنی ئاسایی (failure): کێشەکە هیچ چارەسەرێکی نییە.
- سەرنەکەوتنی بڕین (cutoff): هیچ چارەسەرێک لە ناو دیاریکراودا نییە — بەڵام لەوانەیە یەکێک لە قووڵتردا هەبێت.
Example: with the limit ℓ = 2, DLS explores down to level 2 and ignores level 3, so the nodes E, F, G and H are skipped. On the lecture's tree it visits S → A → C → D → B → I → J and finds the goal J.
نموونە: بە سنووری ℓ = 2، DLS تا ئاستی 2 دەپشکنێت و ئاستی 3 فەرامۆش دەکات، بۆیە E، F، G و H جێدەهێڵرێن. لەسەر دارەکەی وانەکە سەردانی S → A → C → D → B → I → J دەکات و ئامانجی J دەدۆزێتەوە.
| Advantageسوود | Disadvantageزیان |
|---|---|
| Memory efficient (like DFS). کەم بەکار دەهێنێت (وەک DFS). | Incomplete: if the shallowest goal is deeper than ℓ, it is never found. نییە: ئەگەر نزیکترین ئامانج لە ℓ قووڵتر بێت، هەرگیز نادۆزرێتەوە. |
| It may not be optimal if the problem has more than one solution.ئەگەر کێشەکە زیاتر لە یەک چارەسەری هەبێت، لەوانەیە باشترین نەبێت. |
In numbers: DLS takes O(b^ℓ) time and only O(b·ℓ) memory. It is complete only when the goal is no deeper than ℓ — and we rarely know the depth of the goal in advance. The next algorithm removes that problem.
بە ژمارە: DLS کاتی O(b^ℓ) دەخایەنێت و تەنها O(b·ℓ)ی پێویستە. تەنها کاتێک هەیە کە ئامانجەکە لە ℓ قووڵتر نەبێت — و ئێمە کەم جار پێشوەختە ئامانج دەزانین. دواتر ئەم کێشەیە لادەبات.
Depth-limited searchگەڕانی قووڵایی سنووردار
Depth-limited search in Pythonگەڕانی قووڵایی سنووردار بە Python
Depth-limited search is easiest to write as a function that calls itself (): each call looks at one node and then calls itself for every child with the limit reduced by one. It reports one of three results: "found", "cutoff" or "failure".
بە ئاسانترین شێوە وەک دەنووسرێت کە خۆی بانگ دەکاتەوە (): هەر بانگکردنێک سەیری یەک دەکات و پاشان بۆ هەر منداڵێک خۆی بانگ دەکاتەوە بە سنوورێکی یەک کەمتر. یەکێک لە سێ ئەنجام ڕادەگەیەنێت: "found"، "cutoff" یان "failure".
# The tree of the lecture's depth-limited example: each node -> its children.
tree = {"S": ["A", "B"], "A": ["C", "D"], "B": ["I", "J"],
"C": ["E", "F"], "D": ["G"], "I": ["H"]}
def depth_limited(tree, node, goal, limit, visited):
"""Depth-first search that never goes deeper than `limit`.
Returns "found", "cutoff" (the limit stopped us) or "failure"."""
visited.append(node)
if node == goal:
return "found"
children = tree.get(node, [])
if limit == 0: # we may not go deeper
return "cutoff" if children else "failure"
cut = False
for child in children:
result = depth_limited(tree, child, goal, limit - 1, visited)
if result == "found":
return "found"
if result == "cutoff":
cut = True
return "cutoff" if cut else "failure"
for goal, limit in [("J", 2), ("G", 2), ("Z", 5)]:
visited = []
result = depth_limited(tree, "S", goal, limit, visited)
print(f"goal {goal}, limit {limit}: {result:7} visited {' '.join(visited)}")goal J, limit 2: found visited S A C D B I J goal G, limit 2: cutoff visited S A C D B I J goal Z, limit 5: failure visited S A C E F D G B I H J
J is found within the limit. G is at depth 3, below the limit: cutoff. Z is not in the tree at all, and a limit of 5 reaches every node: failure.
J لە ناو سنوورەکەدا دەدۆزرێتەوە. G لە 3دایە، لە خوار سنوورەکەوە: cutoff. Z هەر لە دارەکەدا نییە و سنووری 5 دەگاتە هەموو : failure.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 2-3
The lecture's tree: each node and its children.
دارەکەی وانەکە: هەر و منداڵەکانی.
- Lineدێڕی 13-14
At the limit we stop. If the node still has children, a solution might be below: "cutoff". A leaf at the limit is a plain dead end.
لە سنوورەکەدا دەوەستین. ئەگەر هێشتا منداڵی هەبێت، لەوانەیە چارەسەرێک لە خوارەوە هەبێت: "cutoff". لە سنوورەکەدا تەنها ڕێگەیەکی داخراوە.
- Lineدێڕی 17
The recursive call, one level deeper, with one less unit of limit.
بانگکردنەوەی خۆیی، یەک ئاست قووڵتر، بە سنوورێکی یەک کەمتر.
- Lineدێڕی 22
"failure" only if no branch was cut off: the whole tree was searched.
"failure" تەنها ئەگەر هیچ لقێک نەبڕابێت: هەموو دارەکە گەڕاوە.
Iterative deepening depth-first searchگەڕانی قووڵکردنەوەی پلەبەپلە
Depth-limited search run again and again with the limits 0, 1, 2, … until a goal is found. Like DFS it uses little memory, and like BFS it finds the shallowest goal.
کە جار لە دوای جار بە سنووری 0، 1، 2، … جێبەجێ دەکرێت تا ئامانجێک دەدۆزرێتەوە. وەک بیرگەی کەم بەکار دەهێنێت و وەک نزیکترین ئامانج دەدۆزێتەوە.
The report on uninformed search explains: iterative deepening depth-first search (IDDFS) combines the ideas of depth-first and breadth-first search. It repeatedly performs a depth-limited search and raises the depth limit after each iteration. In each step it searches as deep as the current limit allows; if it does not find the goal, it increases the limit and searches again, until the goal is reached.
ڕاپۆرتەکەی دەربارەی ڕوونی دەکاتەوە: (IDDFS) بیرۆکەکانی و پێکەوە کۆ دەکاتەوە. جار لە دوای جار جێبەجێ دەکات و دوای هەر جارێک سنوورەکە بەرز دەکاتەوە. لە هەر هەنگاوێکدا تا ئەو قووڵاییەی سنووری ئێستا ڕێگە دەدات دەگەڕێت؛ ئەگەر ئامانجەکە نەدۆزییەوە، سنوورەکە زیاد دەکات و دووبارە دەگەڕێتەوە، تا دەگاتە ئامانج.
IDDFS is like looking for a book on a library shelf: you check the books on the first shelf; then you go back and check the first two shelves; then the first three, and so on, until you find the book you need.
IDDFS وەک گەڕانە بەدوای کتێبێکدا لە ڕەفەی کتێبخانەدا: سەرەتا کتێبەکانی ڕەفەی یەکەم دەپشکنیت؛ پاشان دەگەڕێیتەوە و دوو ڕەفەی یەکەم دەپشکنیت؛ پاشان سێ ڕەفەی یەکەم و بەم شێوەیە، تا ئەو کتێبەی پێویستتە دەیدۆزیتەوە.
Where the analogy stops workingسنووری ئەم نموونەیە
A person would not re-read the first shelf every time. IDDFS really does repeat the shallow levels in each round — that is its price for using so little memory.
مرۆڤ هەموو جارێک ڕەفەی یەکەم دووبارە ناخوێنێتەوە. IDDFS بەڕاستی ئاستە کەمقووڵەکان لە هەر جارێکدا دووبارە دەکاتەوە — ئەمە نرخی ئەوەیە کە ئەوەندە کەم بەکار دەهێنێت.
Start with a depth limit of 0.
بە 0 دەست پێبکە.
Use depth-first search, but only go as deep as the current limit.
بەکار بهێنە، بەڵام تەنها تا سنووری ئێستا بڕۆ.
If you find the goal, stop and return it.
ئەگەر ئامانجەکەت دۆزییەوە، بوەستە و بیگەڕێنەوە.
If you do not find it and you have not reached the maximum depth, increase the limit by 1 and repeat steps 2–4.
ئەگەر نەتدۆزییەوە و نەگەیشتوویتە ، سنوورەکە 1 زیاد بکە و هەنگاوەکانی 2–4 دووبارە بکەرەوە.
If you do not find it and you have already reached the maximum depth, stop and return failure.
ئەگەر نەتدۆزییەوە و پێشتر گەیشتوویتە ، بوەستە و سەرنەکەوتن بگەڕێنەوە.
It uses little memory like depth-first search, and like breadth-first search it is sure to find the shallowest solution. This makes it useful when the search space is very large and the depth of the solution is unknown.
وەک کەم بەکار دەهێنێت و وەک دڵنیایە کە کەمقووڵترین چارەسەر دەدۆزێتەوە. ئەمە سوودبەخشی دەکات کاتێک فەزای گەڕان زۆر گەورەیە و چارەسەرەکە نەزانراوە.
Iterative deepening depth-first searchگەڕانی قووڵکردنەوەی پلەبەپلە
IDDFS step by stepIDDFS هەنگاو بە هەنگاو
The report's example tree: A at the top; B and C below it; D, E under B and F, G under C; H and I under D and L under F. The goal is I. The iterations are:
نموونە دارەکەی ڕاپۆرتەکە: A لە سەرەوە؛ B و C لە ژێریدا؛ D، E لە ژێر B و F، G لە ژێر C؛ H و I لە ژێر D و L لە ژێر F. ئامانجەکە Iـە. جارەکان ئەمانەن:
- 1st iteration (limit 0): A
- 2nd iteration (limit 1): A, B, C
- 3rd iteration (limit 2): A, B, D, E, C, F, G
- 4th iteration (limit 3): A, B, D, H, I — the goal I is found
- جاری یەکەم (سنوور 0): A
- جاری دووەم (سنوور 1): A، B، C
- جاری سێیەم (سنوور 2): A، B، D، E، C، F، G
- جاری چوارەم (سنوور 3): A، B، D، H، I — ئامانجی I دۆزرایەوە
# The tree of the iterative-deepening example: each node -> its children.
tree = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F", "G"],
"D": ["H", "I"], "F": ["L"]}
def depth_limited(node, goal, limit, visited):
"""Depth-first search that never goes deeper than `limit`.
Returns "found", "cutoff" (stopped by the limit) or "failure"."""
visited.append(node)
if node == goal:
return "found"
children = tree.get(node, [])
if limit == 0:
return "cutoff" if children else "failure" # children exist below the limit
cut = False
for child in children:
result = depth_limited(child, goal, limit - 1, visited)
if result == "found":
return "found"
if result == "cutoff":
cut = True
return "cutoff" if cut else "failure"
def iterative_deepening(start, goal, max_depth=10):
for limit in range(max_depth + 1): # limits 0, 1, 2, ...
visited = []
result = depth_limited(start, goal, limit, visited)
print(f"limit {limit}: {' '.join(visited):16} -> {result}")
if result != "cutoff": # "found" or "failure": stop
return result
return "cutoff"
iterative_deepening("A", "I")
print()
print("Depth-limited search, limit 2, goal I:", depth_limited("A", "I", 2, []))
print("Depth-limited search, limit 5, goal Z:", depth_limited("A", "Z", 5, []))limit 0: A -> cutoff limit 1: A B C -> cutoff limit 2: A B D E C F G -> cutoff limit 3: A B D H I -> found Depth-limited search, limit 2, goal I: cutoff Depth-limited search, limit 5, goal Z: failure
The four printed rounds are exactly the report's four iterations.
چوار جارە چاپکراوەکە ڕێک چوار جارەکەی ڕاپۆرتەکەن.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 6-22
The same depth-limited search as before.
هەمان پێشوو.
- Lineدێڕی 26
Limits 0, 1, 2, … up to a safety maximum.
سنوورەکانی 0، 1، 2، … تا سنوورێکی بەرزی پارێزراو.
- Lineدێڕی 30-31
Stop on "found" or "failure"; on "cutoff" try one level deeper.
لەسەر "found" یان "failure" بوەستە؛ لەسەر "cutoff" یەک ئاست قووڵتر تاقی بکەرەوە.
Iterative deepening depth-first searchگەڕانی قووڵکردنەوەی پلەبەپلە
Strengths and costs of IDDFSخاڵە بەهێزەکان و تێچووی IDDFS
| Advantagesسوودەکان | Disadvantageزیان |
|---|---|
| It combines the good parts of BFS and DFS: fast searches with little memory.خاڵە باشەکانی BFS و DFS کۆ دەکاتەوە: گەڕانی خێرا بە کەم. | It repeats the work done in the earlier iterations.ئەو کارەی لە جارەکانی پێشوودا کراوە دووبارە دەکاتەوە. |
| It is simple to use, because it is built on ordinary depth-first search.بەکارهێنانی سادەیە، چونکە لەسەر ئاسایی دروست کراوە. | |
| It always finds the best solution if all path costs are the same.هەمیشە دەدۆزێتەوە ئەگەر هەموو وەک یەک بن. | |
| It is complete: it always finds a solution if there is one. هەیە: هەمیشە چارەسەرێک دەدۆزێتەوە ئەگەر هەبێت. | |
| It uses less memory than BFS, because it keeps only the current path, not the whole search tree. کەمتر لە BFS بەکار دەهێنێت، چونکە تەنها ڕێگەی ئێستا هەڵدەگرێت، نەک هەموو . |
b, d = 10, 5 # branching factor 10, shallowest goal at depth 5
# BFS generates every level once.
bfs = sum(b ** level for level in range(1, d + 1))
# Iterative deepening generates level 1 d times, level 2 (d - 1) times, ..., level d once.
ids = sum((d + 1 - level) * b ** level for level in range(1, d + 1))
print(f"BFS: {bfs:,} nodes")
print(f"IDS: {ids:,} nodes ({ids / bfs - 1:.0%} more)")BFS: 111,110 nodes IDS: 123,450 nodes (11% more)
Only about 11% more nodes than BFS, with far less memory.
تەنها نزیکەی 11% زیاتر لە BFS، بە زۆر کەمتر.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4
BFS makes each level once: b + b² + … + b^d.
BFS هەر ئاستێک یەک جار دروست دەکات: b + b² + … + b^d.
- Lineدێڕی 6
IDDFS makes level 1 d times, level 2 d − 1 times, …, the deepest level once.
IDDFS ئاستی 1 d جار، ئاستی 2 d − 1 جار، …، قووڵترین ئاست یەک جار دروست دەکات.
Uniform-cost searchگەڕانی کەمترین کۆست
An uninformed search that always expands the frontier node with the lowest path cost g(n), using a priority queue. It finds the cheapest path when every step cost is positive, and it is the same idea as Dijkstra's algorithm.
کە هەمیشە ئەو نۆدەی فراوان دەکات کە کەمترین (g(n))ی هەیە و بۆ ئەمە بەکار دەهێنێت. کاتێک هەموو کۆستێکی هەنگاو لە سفر گەورەتر بێت هەرزانترین ڕێگا دەدۆزێتەوە؛ هەمان بیرۆکەی Dijkstraـیە.
The lecture: uniform-cost search (UCS) is a searching algorithm for a or tree. It comes into play when each edge has a different cost. Its main goal is to find a path to the goal node with the lowest cumulative cost.
وانەکە: (UCS) بۆ یان . کاتێک بەکار دێت کە هەر کۆستێکی جیاوازی هەبێت. ئامانجی سەرەکیی دۆزینەوەی ڕێگەیەکە بۆ ئامانج کە کەمترین کۆستی کۆکراوەی هەبێت.
How it works: UCS keeps its frontier in a ordered by the path cost so far, written g(n). It always removes the cheapest node. Like breadth-first search it spreads out from the start, but in rings of equal cost instead of equal numbers of steps. And it tests for the goal when a node is removed, not when it is added: a cheaper path to the goal may still be waiting in the frontier.
چۆن کار دەکات: UCS لە هەڵدەگرێت کە بەپێی تا ئێستا ڕیز کراوە، کە بە g(n) دەنووسرێت. هەمیشە هەرزانترین دەردەهێنێت. وەک لە سەرەتاوە بڵاو دەبێتەوە، بەڵام بە بازنەی کۆستی یەکسان نەک ژمارەی یەکسانی هەنگاو. هەروەها کاتێک دەردەهێنرێت دەکات، نەک کاتێک زیاد دەکرێت: لەوانەیە ڕێگەیەکی هەرزانتر بۆ ئامانج هێشتا لە چاوەڕێ بکات.
A worked example of uniform-cost search on a weighted graph: always expand the cheapest path found so far, until the cheapest path reaches a goal.
نموونەیەکی هەنگاوبەهەنگاوی لەسەر : هەمیشە هەرزانترین کە تا ئێستا دۆزراوەتەوە فراوان دەکرێت، تا ئەو کاتەی هەرزانترین دەگاتە .
Whole video: the example graph, then uniform-cost search traced by hand from 1:58.
هەموو ڤیدیۆکە: نموونەکە، پاشان لە 1:58 بەدواوە بە دەست هەنگاو بە هەنگاو جێبەجێ دەکرێت.
Uniform-cost searchگەڕانی کەمترین کۆست
Four steps instead of twoچوار هەنگاو لەبری دوو
| Advantageسوود | Disadvantageزیان |
|---|---|
| It is optimal, because at every state the path with the least cost is chosen.باشترینە، چونکە لە هەموو ئەو ڕێگەیە هەڵدەبژێرێت کە کەمترین کۆستی هەیە. | It does not care about the number of steps; it is only concerned about path cost.گرنگی بە ژمارەی هەنگاوەکان نادات؛ تەنها گرنگە بۆی. |
The town map shows exactly this. Home → Bazaar → School takes 2 roads and 10 minutes; Home → Park → Teahouse → Library → School takes 4 roads and only 9 minutes. UCS chooses the 4-road route. The lecture's own example does the same on a weighted tree: UCS returns S → A → D → G with cost 1 + 2 + 3 = 6, not the 2-step path S → B → G with cost 4 + 5 = 9.
نەخشەی شارۆچکەکە ڕێک ئەمە پیشان دەدات. ماڵ ← بازاڕ ← قوتابخانە 2 ڕێگا و 10 خولەک دەخایەنێت؛ ماڵ ← پارک ← چایخانە ← کتێبخانە ← قوتابخانە 4 ڕێگا و تەنها 9 خولەک دەخایەنێت. UCS ڕێگە 4 ڕێگاییەکە هەڵدەبژێرێت. نموونەکەی خودی وانەکە هەمان کار لەسەر کێشدار دەکات: UCS ڕێگەی S → A → D → G بە کۆستی 1 + 2 + 3 = 6 دەگەڕێنێتەوە، نەک ڕێگە دوو هەنگاوییەکەی S → B → G بە کۆستی 4 + 5 = 9.
Uniform-cost searchگەڕانی کەمترین کۆست
Uniform-cost search in Pythonگەڕانی کەمترین کۆست بە Python
Python's heapq module turns a list into a : heappop() always returns the smallest item. We store (g, count, state, path) tuples. The tuples are compared item by item, so the smallest g comes out first; count breaks ties, so Python never has to compare two paths. (Heaps and priority queues are explained in Priority queues and heaps.)
heapqی لیستێک دەکات بە : heappop() هەمیشە بچووکترین دانە دەگەڕێنێتەوە. (g, count, state, path) هەڵدەگرین. دانە بە دانە بەراورد دەکرێن، بۆیە بچووکترین g لە پێشدا دەردەچێت؛ count یەکسانییەکان دەشکێنێت، بۆ ئەوەی هەرگیز ناچار نەبێت دوو ڕێگە بەراورد بکات. ( و لە کیووە پێشینەییەکان و هیپەکان ڕوون کراونەتەوە.)
import heapq
from collections import deque
# The town map: minutes of walking on each road (roads work both ways).
roads = {
"Home": {"Bazaar": 4, "Park": 2},
"Bazaar": {"Home": 4, "School": 6, "Teahouse": 5},
"Park": {"Home": 2, "Teahouse": 3},
"Teahouse": {"Park": 3, "Bazaar": 5, "Library": 2},
"Library": {"Teahouse": 2, "School": 2},
"School": {"Bazaar": 6, "Library": 2},
}
def uniform_cost_search(start, goal):
count = 0 # tie-breaker for equal costs
frontier = [(0, count, start, [start])] # (g, count, state, path)
explored = set()
while frontier:
g, _, state, path = heapq.heappop(frontier) # the CHEAPEST path so far
if state in explored:
continue # a cheaper copy was expanded already
if state == goal: # goal test when the node is REMOVED
print(f"remove {state:8} g = {g} -> goal!")
return g, path
explored.add(state)
for neighbour, minutes in roads[state].items():
if neighbour not in explored:
count += 1
heapq.heappush(frontier, (g + minutes, count, neighbour, path + [neighbour]))
waiting = ", ".join(f"{s} {c}" for c, _, s, _ in sorted(frontier))
print(f"remove {state:8} g = {g} | frontier: {waiting}")
return None
def breadth_first_search(start, goal):
frontier = deque([[start]])
explored = {start}
while frontier:
path = frontier.popleft()
if path[-1] == goal:
return path
for neighbour in roads[path[-1]]:
if neighbour not in explored:
explored.add(neighbour)
frontier.append(path + [neighbour])
cost, path = uniform_cost_search("Home", "School")
print("UCS:", " -> ".join(path), "|", len(path) - 1, "roads,", cost, "minutes")
path = breadth_first_search("Home", "School")
minutes = sum(roads[a][b] for a, b in zip(path, path[1:]))
print("BFS:", " -> ".join(path), "|", len(path) - 1, "roads,", minutes, "minutes")remove Home g = 0 | frontier: Park 2, Bazaar 4 remove Park g = 2 | frontier: Bazaar 4, Teahouse 5 remove Bazaar g = 4 | frontier: Teahouse 5, Teahouse 9, School 10 remove Teahouse g = 5 | frontier: Library 7, Teahouse 9, School 10 remove Library g = 7 | frontier: Teahouse 9, School 9, School 10 remove School g = 9 -> goal! UCS: Home -> Park -> Teahouse -> Library -> School | 4 roads, 9 minutes BFS: Home -> Bazaar -> School | 2 roads, 10 minutes
UCS finds 4 roads / 9 minutes; BFS finds the fewest roads, 2 roads / 10 minutes. The frontier line after Library shows School twice: 9 and 10 minutes.
UCS 4 ڕێگا / 9 خولەک دەدۆزێتەوە؛ BFS کەمترین ڕێگا دەدۆزێتەوە، 2 ڕێگا / 10 خولەک. دێڕی دوای کتێبخانە قوتابخانە دوو جار پیشان دەدات: 9 و 10 خولەک.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-12
The map: each place, its neighbours and the minutes to reach them.
نەخشەکە: هەر شوێنێک، دراوسێکانی و خولەکەکانی گەیشتن پێیان.
- Lineدێڕی 17
The frontier starts with the start state at cost 0.
بە و کۆستی 0 دەست پێدەکات.
- Lineدێڕی 20
heappop()gives the cheapest path so far.heappop()هەرزانترین ڕێگەی تا ئێستا دەدات.- Lineدێڕی 21-22
An old, more expensive copy of a state that was already expanded is skipped.
وێنەیەکی کۆن و گرانتری کە پێشتر فراوان کراوە جێدەهێڵرێت.
- Lineدێڕی 23-25
The goal test happens when a state is removed. School first entered the frontier with 10 minutes (via Bazaar), but the 9-minute path was removed first.
کاتێک ڕوودەدات کە دۆخێک دەردەهێنرێت. قوتابخانە یەکەم جار بە 10 خولەک (لە ڕێگەی بازاڕەوە) چووە ناو ، بەڵام ڕێگە 9 خولەکییەکە لە پێشدا دەرهێنرا.
- Lineدێڕی 27-30
Push every neighbour with its new total cost g + minutes.
هەموو دراوسێیەک بە کۆی کۆستی نوێیەوە g + خولەک دابنێ.
- Lineدێڕی 36-46
BFS on the same map, for comparison: it ignores the minutes.
BFS لەسەر هەمان نەخشە، بۆ بەراورد: خولەکەکان فەرامۆش دەکات.
Uniform-cost searchگەڕانی کەمترین کۆست
One family: BFS, UCS, greedy and A*یەک خێزان: BFS، UCS، چاوچنۆکانە و A*
Breadth-first search, uniform-cost search and the two informed algorithms of the next lessons are one family. They all run the same loop with a priority queue; only the priority of a node changes:
، و دوو زانیاریدارەکەی وانەکانی داهاتوو یەک خێزانن. هەموویان هەمان خول بە جێبەجێ دەکەن؛ تەنها پێشینەیی دەگۆڕێت:
| Algorithm | Takes out first the node with the smallest…سەرەتا ئەو دەردەهێنێت کە بچووکترین… ی هەیە | Kindجۆر |
|---|---|---|
| Breadth-first search | depth (number of steps)قووڵایی (ژمارەی هەنگاو) | uninformedبێزانیاری |
| Uniform-cost search / Dijkstra / Dijkstra | g(n): cost from the startg(n): کۆست لە سەرەتاوە | uninformedبێزانیاری |
| Greedy best-first search | h(n): estimated cost to the goalh(n): کۆستی خەمڵێنراو تا ئامانج | informedزانیاریدار |
| A* search | f(n) = g(n) + h(n)f(n) = g(n) + h(n): کۆی هەردووکیان | informedزانیاریدار |
So UCS is A* with h(n) = 0: it knows the cost already paid but has no guess about the cost ahead. The next lessons, greedy best-first search and A* search, add that guess.
کەواتە UCS بریتییە لە A* بە h(n) = 0: کۆستی پێشتر دراو دەزانێت بەڵام هیچ خەمڵاندنێکی دەربارەی کۆستی پێشەوە نییە. وانەکانی دواتر، گەڕانی چاوچنۆکانە و گەڕانی A*، ئەو خەمڵاندنە زیاد دەکەن.
Bidirectional searchگەڕانی دووئاڕاستە
Two searches run at the same time, one forward from the start and one backward from the goal, and they stop when they meet in the middle. Two searches to depth d/2 cost about 2·b^(d/2) instead of b^d.
دوو گەڕانن کە لە یەک کاتدا کار دەکەن: یەکێکیان لە سەرەتاوە بەرەو پێش دەڕوات و ئەوی تریان لە ئامانجەوە بەرەو دواوە؛ کاتێک لە ناوەڕاستدا بەیەک دەگەن دەوەستن. دوو گەڕان تا قووڵایی d/2 نزیکەی 2·b^(d/2) دەخایەنن نەک b^d.
Bidirectional search runs two searches at the same time. One starts from the starting point and moves forward (the forward search); the other starts from the goal and moves backward (the backward search). The two move toward each other and stop when they meet in the middle. Instead of one large search space, there are two smaller ones, and this makes the search faster — especially in problems with a large number of states. Each half can use BFS, DFS or DLS.
دوو گەڕان لە یەک کاتدا جێبەجێ دەکات. یەکێکیان لە خاڵی سەرەتاوە دەست پێدەکات و بەرەو پێش دەڕوات (گەڕانی بەرەو پێش)؛ ئەوی تریان لە ئامانجەوە دەست پێدەکات و بەرەو دواوە دەڕوات (گەڕانی بەرەو دواوە). هەردووکیان بەرەو یەکتر دەڕۆن و کاتێک لە ناوەڕاستدا بەیەک دەگەن دەوەستن. لەبری یەک فەزای گەڕانی گەورە، دوو فەزای بچووکتر هەن و ئەمە گەڕانەکە خێراتر دەکات — بە تایبەتی لەو کێشانەی ژمارەیەکی زۆر هەیە. هەر نیوەیەک دەتوانێت BFS، DFS یان DLS بەکار بهێنێت.
Two people try to meet in a big maze: one starts at the entrance and the other at the exit. Each searches step by step until they meet somewhere in the middle.
دوو کەس هەوڵ دەدەن لە گەورەدا یەکتر ببینن: یەکێکیان لە دەروازەوە دەست پێدەکات و ئەوی تریان لە دەرچەوە. هەریەکەیان هەنگاو بە هەنگاو دەگەڕێت تا لە شوێنێک لە ناوەڕاستدا بەیەک دەگەن.
Where the analogy stops workingسنووری ئەم نموونەیە
In real life the two people can call each other. In the algorithm, after every step one side must check whether any of its new nodes is already known to the other side — that check is the hard part.
لە ژیانی ڕاستەقینەدا دوو کەسەکە دەتوانن بانگی یەکتر بکەن. لە ، دوای هەر هەنگاوێک لایەک دەبێت بپشکنێت ئایا هیچ کام لە نوێیەکانی لای ئەوی تر ناسراوە — ئەم پشکنینە بەشە قورسەکەیە.
The report says that by cutting the search space in half, this method saves a lot of time. The saving is in fact much bigger than one half. One search to depth d makes about b^d nodes. Two searches that each go only to depth d/2 make about b^(d/2) + b^(d/2). With b = 10 and d = 6: about 1,000,000 nodes for one search, but only about 2,000 for two. The method works best for problems with clear start and goal points, like finding the shortest route on a map; its price is the extra memory needed to track both sides.
ڕاپۆرتەکە دەڵێت ئەم ڕێگایە بە نیوەکردنی فەزای گەڕان کاتێکی زۆر دەگەڕێنێتەوە. لە ڕاستیدا قازانجەکە زۆر لە نیوە گەورەترە. گەڕانێک تا d نزیکەی b^d دروست دەکات. دوو گەڕان کە هەریەکەیان تەنها تا d/2 دەچن نزیکەی b^(d/2) + b^(d/2) دروست دەکەن. بە b = 10 و d = 6: نزیکەی 1,000,000 بۆ یەک گەڕان، بەڵام تەنها نزیکەی 2,000 بۆ دوو گەڕان. ئەم ڕێگایە بۆ ئەو کێشانە باشترینە کە خاڵی سەرەتا و ئامانجی ڕوونیان هەیە، وەک دۆزینەوەی لەسەر نەخشەیەک؛ نرخەکەی ئەو زیادەیەیە کە بۆ چاودێریکردنی هەردوو لا پێویستە.
Bidirectional searchگەڕانی دووئاڕاستە
How it worksچۆن کار دەکات
The forward search begins at the start node and explores the possible paths step by step. At the same time the backward search begins at the goal node and does the same, trying to reach the start. The algorithm keeps track of both searches until they meet; at that point the solution is found. Each search only explores about half of the path, so there is less work to do.
گەڕانی بەرەو پێش لە سەرەتاوە دەست پێدەکات و هەنگاو بە هەنگاو ڕێگا ئەگەرییەکان دەپشکنێت. لە هەمان کاتدا گەڕانی بەرەو دواوە لە ئامانجەوە دەست پێدەکات و هەمان کار دەکات، هەوڵ دەدات بگاتە سەرەتا. چاودێریی هەردوو گەڕانەکە دەکات تا بەیەک دەگەن؛ لەو ساتەدا چارەسەرەکە دۆزراوەتەوە. هەر گەڕانێک تەنها نزیکەی نیوەی ڕێگەکە دەپشکنێت، بۆیە کاری کەمتر دەمێنێت.
Start both searches: one from the start, one from the goal.
هەردوو گەڕانەکە دەست پێبکە: یەکێک لە سەرەتاوە، یەکێک لە ئامانجەوە.
Expand nodes one by one (or level by level) from each side.
یەک بە یەک (یان ئاست بە ئاست) لە هەر لایەکەوە فراوان بکە.
Check whether a node of the forward search matches a node of the backward search.
بپشکنە ئایا گەڕانی بەرەو پێش لەگەڵ گەڕانی بەرەو دواوە یەک دەگرێتەوە.
When they meet, stop and build the path: start → meeting node → goal.
کاتێک بەیەک گەیشتن، بوەستە و ڕێگەکە دروست بکە: سەرەتا ← بەیەکگەیشتن ← ئامانج.
The report's example graph has the nodes 1 to 16. One search starts at node 1 and moves forward; the other starts at the goal node 16 and moves backward. They meet at node 9, and the path is joined there. The small program below does the same on our town map, with breadth-first search on both sides:
نموونە گرافەکەی ڕاپۆرتەکە 1 تا 16ی هەیە. گەڕانێک لە 1ەوە دەست پێدەکات و بەرەو پێش دەڕوات؛ ئەوی تریان لە ئامانجی 16ەوە دەست پێدەکات و بەرەو دواوە دەڕوات. لە 9 بەیەک دەگەن و ڕێگەکە لەوێ بەیەکەوە دەبەسترێت. ئەم بچووکەی خوارەوە هەمان کار لەسەر نەخشەی شارۆچکەکەمان دەکات، بە لە هەردوو لاوە:
# Roads of the town map (both directions). Only the connections matter here.
roads = {
"Home": ["Bazaar", "Park"],
"Bazaar": ["Home", "School", "Teahouse"],
"Park": ["Home", "Teahouse"],
"Teahouse": ["Park", "Bazaar", "Library"],
"Library": ["Teahouse", "School"],
"School": ["Bazaar", "Library"],
}
def expand_one_level(level, parent):
"""Breadth-first: expand every node of the current level once."""
next_level = []
for state in level:
for neighbour in roads[state]:
if neighbour not in parent:
parent[neighbour] = state
next_level.append(neighbour)
return next_level
def bidirectional_search(start, goal):
forward, backward = {start: None}, {goal: None} # node -> where it came from
f_level, b_level = [start], [goal]
while f_level and b_level:
f_level = expand_one_level(f_level, forward) # one step from the start
print("forward reached: ", f_level)
meet = [s for s in f_level if s in backward]
if not meet:
b_level = expand_one_level(b_level, backward) # one step from the goal
print("backward reached:", b_level)
meet = [s for s in b_level if s in forward]
if meet:
m = meet[0]
left, s = [], m
while s is not None: # meeting point back to the start
left.append(s)
s = forward[s]
right, s = [], backward[m]
while s is not None: # meeting point on to the goal
right.append(s)
s = backward[s]
return m, left[::-1] + right
return None, []
meet, path = bidirectional_search("Home", "School")
print("The searches meet at", meet)
print("Path:", " -> ".join(path))forward reached: ['Bazaar', 'Park'] backward reached: ['Bazaar', 'Library'] The searches meet at Bazaar Path: Home -> Bazaar -> School
After one level from each side both searches have reached Bazaar. The path has 2 roads, the same as one-way BFS.
دوای یەک ئاست لە هەر لایەکەوە، هەردوو گەڕانەکە گەیشتوونەتە بازاڕ. ڕێگەکە 2 ڕێگای هەیە، وەک BFSی یەک ئاڕاستە.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 2-9
Only the connections matter here, so the minutes are left out.
لێرەدا تەنها پەیوەندییەکان گرنگن، بۆیە خولەکەکان لابراون.
- Lineدێڕی 12-20
Expand one whole level and remember where each new node came from.
ئاستێکی تەواو فراوان بکە و لە بیری بگرە هەر نوێ لە کوێوە هاتووە.
- Lineدێڕی 24
Two parent dictionaries: one for each direction.
دوو باوک: بۆ هەر ئاڕاستەیەک یەکێک.
- Lineدێڕی 29, 33
The meeting check: is a new node already known to the other side?
پشکنینی بەیەکگەیشتن: ئایا نوێ لای ئەوی تر ناسراوە؟
- Lineدێڕی 35-44
Join the two halves: from the start to the meeting node, then on to the goal.
دوو نیوەکە بەیەکەوە ببەستە: لە سەرەتاوە تا بەیەکگەیشتن، پاشان تا ئامانج.
Bidirectional searchگەڕانی دووئاڕاستە
Advantages and disadvantagesسوود و زیانەکان
| Advantageسوود | Disadvantageزیان |
|---|---|
| It is faster, because it searches from both ends at the same time.خێراترە، چونکە لە یەک کاتدا لە هەردوو سەرەوە دەگەڕێت. | It is hard to set up and implement.ئامادەکردن و جێبەجێکردنی قورسە. |
| It uses less memory compared to other search methods.بە بەراورد لەگەڵ ڕێگاکانی تری گەڕان کەمتر بەکار دەهێنێت. | You need to know the goal state before starting.پێویستە پێش دەستپێکردن بزانیت. |
| It is very useful when the graph is large and cannot be made smaller.زۆر بەسوودە کاتێک گەورەیە و ناتوانرێت بچووک بکرێتەوە. | Checking whether the two searches meet can be difficult, and this may make the search slower.پشکنینی ئەوەی دوو گەڕانەکە بەیەک دەگەن دەکرێت قورس بێت و ئەمە لەوانەیە گەڕانەکە هێواشتر بکات. |
| Expanding many nodes can be costly; bidirectional search reduces the number of nodes to expand. زۆر دەکرێت گران بێت؛ ژمارەی ئەو دەبێت فراوان بکرێن کەم دەکاتەوە. |
Comparing the six uninformed algorithmsبەراوردکردنی شەش ئەلگۆریزمە بێزانیارییەکە
The table puts all the uninformed algorithms of this chapter side by side. Time and space are counted in nodes, not seconds (see Search problems). b = branching factor, d = depth of the shallowest goal, m = maximum depth, ℓ = depth limit, C* = cost of the optimal solution, ε = the smallest step cost.
ئەم خشتەیە هەموو بێزانیارییەکانی ئەم بەشە لە تەنیشت یەک دادەنێت. کات و بە دەژمێردرێن، نەک بە چرکە (بڕوانە کێشەکانی گەڕان). b = ، d = نزیکترین ئامانج، m = ، ℓ = ، C* = کۆستی ، ε = بچووکترین .
| Algorithm | Complete?؟ | Optimal?؟ | Timeکات | Space |
|---|---|---|---|---|
| Breadth-first (BFS) | Yes¹بەڵێ¹ | Yes³بەڵێ³ | O(b^d) | O(b^d) |
| Uniform-cost (UCS) | Yes¹ ²بەڵێ¹ ² | Yesبەڵێ | O(b^(1+⌊C*/ε⌋)) | O(b^(1+⌊C*/ε⌋)) |
| Depth-first (DFS) | Noنەخێر | Noنەخێر | O(b^m) | O(b·m) |
| Depth-limited (DLS) | Noنەخێر | Noنەخێر | O(b^ℓ) | O(b·ℓ) |
| Iterative deepening (IDDFS) | Yes¹بەڵێ¹ | Yes³بەڵێ³ | O(b^d) | O(b·d) |
| Bidirectional | Yes¹ ⁴بەڵێ¹ ⁴ | Yes³ ⁴بەڵێ³ ⁴ | O(b^(d/2)) | O(b^(d/2)) |
How to choose: if memory is the problem and steps cost the same, use iterative deepening. If steps have different costs, use uniform-cost search. If you know the goal and can search backward, bidirectional search saves the most work. And if you can estimate the distance to the goal, informed search (greedy best-first, A*) does better than all of them.
چۆن هەڵبژێریت: ئەگەر کێشەیە و هەنگاوەکان هەمان کۆستیان هەیە، بەکار بهێنە. ئەگەر هەنگاوەکان کۆستی جیاوازیان هەیە، بەکار بهێنە. ئەگەر ئامانجەکە دەزانیت و دەتوانیت بەرەو دواوە بگەڕێیت، زۆرترین کار دەگەڕێنێتەوە. هەروەها ئەگەر بتوانیت دووریی ئامانج بخەمڵێنیت، (، A*) لە هەموویان باشتر کار دەکات.
Common mistakesهەڵە باوەکان
| Mistakeهەڵە | Betterباشتر |
|---|---|
| “Cutoff” and “failure” mean the same.«cutoff» و «failure» هەمان واتایان هەیە. | Cutoff: nothing within the limit, maybe deeper. Failure: nothing anywhere.cutoff: هیچ شتێک لە ناو سنوورەکەدا نییە، لەوانەیە لە قووڵتردا هەبێت. failure: هیچ شتێک لە هیچ شوێنێک نییە. |
| “IDDFS is as fast as BFS.”«IDDFS بە خێرایی BFSە.» | It repeats the shallow levels: a little more work, the same O(b^d), far less memory.ئاستە کەمقووڵەکان دووبارە دەکاتەوە: کەمێک کاری زیاتر، هەمان O(b^d)، زۆر کەمتر. |
| Testing the goal when a node is added in UCS. کاتێک لە UCSدا زیاد دەکرێت. | Test it when the node is removed from the priority queue.کاتێک لە دەردەهێنرێت تاقیی بکەرەوە. |
| “UCS finds the path with the fewest steps.”«UCS ئەو ڕێگەیە دەدۆزێتەوە کە کەمترین هەنگاوی هەیە.» | It finds the cheapest path; it may take four steps instead of two.هەرزانترین ڕێگە دەدۆزێتەوە؛ لەوانەیە لەبری دوو هەنگاو چوار هەنگاو ببڕێت. |
| “Bidirectional search halves the work.”« کارەکە نیوە دەکات.» | It replaces b^d by about 2·b^(d/2): far less than half.b^d دەگۆڕێت بۆ نزیکەی 2·b^(d/2): زۆر کەمتر لە نیوە. |
| “Bidirectional search uses little memory.”« کەم بەکار دەهێنێت.» | Less than BFS, much more than DFS or IDDFS.کەمتر لە BFS، زۆر زیاتر لە DFS یان IDDFS. |
Exercisesڕاهێنانەکان
On the IDDFS example tree (A; B, C; D, E, F, G; H, I under D; L under F), run depth-limited search with ℓ = 1 and the goal I. Which nodes are visited, and what is the result?
لەسەر نموونە دارەکەی IDDFS (A؛ B، C؛ D، E، F، G؛ H، I لە ژێر D؛ L لە ژێر F)، بە ℓ = 1 و ئامانجی I جێبەجێ بکە. سەردانی کام دەکرێت و ئەنجامەکە چییە؟
Show answerوەڵامەکە پیشان بدە
Visited: A, B, C. B and C are at the limit and still have children, so the result is cutoff: I may be deeper (it is, at depth 3).
سەردانکراو: A، B، C. B و C لە سنوورەکەدان و هێشتا منداڵیان هەیە، بۆیە ئەنجامەکە cutoffـە: لەوانەیە I قووڵتر بێت (وایە، لە 3دایە).
The lecture's UCS example tree has these edge costs: S–A 1, S–B 4, A–C 3, A–D 2, B–G 5, C–E 5, D–G 3, E–G 5 (the cost of D–F is not given, so leave F out). In which order does UCS expand the nodes, and which path does it return?
نموونە دارەکەی UCS لە وانەکەدا ئەم کۆستانەی بۆ داناوە: S–A 1، S–B 4، A–C 3، A–D 2، B–G 5، C–E 5، D–G 3، E–G 5 (کۆستی D–F نەدراوە، بۆیە F لاببە). UCS بە چ ڕیزبەندییەک فراوان دەکات و کام ڕێگە دەگەڕێنێتەوە؟
Show answerوەڵامەکە پیشان بدە
import heapq
# The lecture's weighted tree (edge costs). D-F is left out: its cost is not given.
edges = {"S": {"A": 1, "B": 4}, "A": {"C": 3, "D": 2}, "B": {"G": 5},
"C": {"E": 5}, "D": {"G": 3}, "E": {"G": 5}}
frontier = [(0, 0, "S", "S")] # (g, count, node, path)
count, expanded = 0, []
while frontier:
g, _, node, path = heapq.heappop(frontier)
if node == "G":
print("expanded:", ", ".join(expanded))
print("goal G reached by", path, "with cost", g)
break
expanded.append(f"{node}({g})")
for child, cost in edges.get(node, {}).items():
count += 1
heapq.heappush(frontier, (g + cost, count, child, path + "-" + child))expanded: S(0), A(1), D(3), B(4), C(4) goal G reached by S-A-D-G with cost 6
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-5
The lecture's tree as edge costs.
دارەکەی وانەکە وەک کۆستی .
- Lineدێڕی 10-14
Pop the cheapest path; stop when the goal is removed.
هەرزانترین ڕێگە دەربهێنە؛ کاتێک ئامانج دەردەهێنرێت بوەستە.
Order: S, A, D, B, C, then G is removed. B and C both cost 4; B was added first, so the counter puts it first. G enters the frontier twice — with cost 6 via D and with cost 9 via B — and the cheaper copy is removed first, so UCS returns S-A-D-G (cost 6) before it ever expands E.
ڕیزبەندی: S، A، D، B، C، پاشان G دەردەهێنرێت. B و C هەردووکیان کۆستی 4یان هەیە؛ B لە پێشدا زیاد کرا، بۆیە ژمێرەرەکە دەیخاتە پێش. G دوو جار دەچێتە ناو — بە کۆستی 6 لە ڕێگەی D و بە کۆستی 9 لە ڕێگەی B — و وێنە هەرزانترەکە لە پێشدا دەردەهێنرێت، بۆیە UCS پێش ئەوەی هەرگیز E فراوان بکات ڕێگەی S-A-D-G (کۆستی 6) دەگەڕێنێتەوە.
A problem has b = 10 and the goal is 8 steps away. About how many nodes does one breadth-first search make, and about how many do two half-searches make?
کێشەیەک b = 10ی هەیە و ئامانجەکە 8 هەنگاو دوورە. یەک نزیکەی چەند دروست دەکات و دوو نیوە-گەڕان نزیکەی چەند؟
Show answerوەڵامەکە پیشان بدە
One search: about 10^8 = 100,000,000 nodes. Two searches to depth 4: about 2 × 10^4 = 20,000 nodes — five thousand times fewer.
یەک گەڕان: نزیکەی 10^8 = 100,000,000 . دوو گەڕان تا 4: نزیکەی 2 × 10^4 = 20,000 — پێنج هەزار جار کەمتر.
Summaryپوختە
- Depth-limited search is DFS with a limit ℓ; it reports cutoff (maybe deeper) or failure (nowhere).
- Iterative deepening repeats DLS with limits 0, 1, 2, …: complete, optimal for equal costs, O(b·d) memory.
- Uniform-cost search expands the cheapest path g(n) first, tests the goal on removal and may take four steps instead of two.
- Bidirectional search meets in the middle: about 2·b^(d/2) nodes instead of b^d, but it must store a frontier and needs a known goal.
- DFSە لەگەڵ سنووری ℓ؛ cutoff (لەوانەیە لە قووڵتردا) یان failure (لە هیچ شوێنێک) ڕادەگەیەنێت.
- DLS بە سنوورەکانی 0، 1، 2، … دووبارە دەکاتەوە: هەیە، بۆ کۆستی یەکسان باشترینە، O(b·d).
- سەرەتا هەرزانترین ڕێگە g(n) فراوان دەکات، کاتی دەرهێنان دەکات و لەوانەیە لەبری دوو هەنگاو چوار هەنگاو ببڕێت.
- لە ناوەڕاستدا بەیەک دەگات: نزیکەی 2·b^(d/2) لەبری b^d، بەڵام دەبێت هەڵبگرێت و پێویستی بە ئامانجێکی زانراو هەیە.
What are the two failure values of depth-limited search?دوو نرخی سەرنەکەوتنی گەڕانی قووڵایی سنووردار چین؟
Standard failure (no solution at all) and cutoff failure (no solution within the depth limit).
سەرنەکەوتنی ئاسایی (هیچ چارەسەرێک نییە) و سەرنەکەوتنی بڕین (هیچ چارەسەرێک لە ناو نییە).
Give the four IDDFS iterations of the report's example.چوار جارەکەی IDDFS لە نموونەکەی ڕاپۆرتەکەدا بنووسە.
A | A, B, C | A, B, D, E, C, F, G | A, B, D, H, I (goal found).
A | A، B، C | A، B، D، E، C، F، G | A، B، D، H، I (ئامانج دۆزرایەوە).
Which data structure does UCS use for its frontier?UCS بۆ بەرەکەی کام پێکهاتەی دراوە بەکار دەهێنێت؟
A priority queue (a min-heap, heapq in Python) ordered by the path cost g(n).
(، heapq لە ) کە بەپێی g(n) ڕیز کراوە.
Why does bidirectional search need more memory than IDDFS?بۆچی گەڕانی دووئاڕاستە لە IDDFS بیرگەیەکی زیاتری پێویستە؟
To detect the meeting, at least one side must keep all its frontier nodes in memory.
بۆ ناسینەوەی بەیەکگەیشتن، لانیکەم لایەک دەبێت هەموو لە هەڵبگرێت.
Lesson complete!وانەکە تەواو بوو!
Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.
Key termsزاراوە سەرەکییەکان
Heuristics and Greedy Best-First Searchپێوەرەکان و گەڕانی چاوچنۆکانە
Related lecturesوانە پەیوەندیدارەکان
- Search Problems: States, Actions, Goals and Costsکێشەکانی گەڕان: دۆخەکان، کردەوەکان، ئامانج و کۆست
- Solving a Maze with DFS and BFSچارەسەرکردنی لابیرینت بە DFS و BFS
- Priority Queues and Heapsکیووە پێشینەییەکان و هیپەکان
- Heuristics and Greedy Best-First Searchپێوەرەکان و گەڕانی چاوچنۆکانە
- A* Searchگەڕانی A*
References and further readingسەرچاوەکان و خوێندنەوەی زیاتر
- Berkeley CS188 notes: Uninformed search (DFS, BFS, UCS properties)
- AIMA pseudocode: Depth-Limited-Search
- AIMA pseudocode: Iterative-Deepening-Search
- Russell and Norvig, AIMA 4th ed., §3.4 Uninformed search strategies (contents)
- GeeksforGeeks: Bidirectional search
- Python documentation: heapq — heap queue algorithm
- Red Blob Games: Introduction to A* (BFS, Dijkstra, greedy, A*)
This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.