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

Search Problems: States, Actions, Goals and Costsکێشەکانی گەڕان: دۆخەکان، کردەوەکان، ئامانج و کۆست

How an agent turns a goal into a search problem: the state space, the initial state, actions, the transition model, the goal test and path costs; solutions and optimal solutions; the state-space graph and the search tree; the frontier and the explored set; blind versus informed search; and how algorithms are compared.

چۆن ئامانجێک دەکات بە : ، ، ، ، و ؛ چارەسەر و ؛ و ؛ و ؛ گەڕانی کوێرانە و ؛ و چۆنیەتیی بەراوردکردنی .

18 min read18 خولەک خوێندنەوە · 16 stepsهەنگاو

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

Describe a problem as a search problem: states, initial state, actions, transition model, goal test and path cost.
Tell a solution from an optimal solution, and a state-space graph from a search tree.
Explain nodes, expansion, the frontier and the explored set, and follow the general search loop.
Explain what makes a search uninformed (blind) or informed.
Compare algorithms by completeness, optimality, time and space complexity using b, d and m.

کێشەیەک وەک وەسف بکەیت: ، ، ، ، و .
چارەسەر لە و لە جیا بکەیتەوە.
، ، و ڕوون بکەیتەوە و خولی گشتیی گەڕان پەیڕەو بکەیت.
ڕوونی بکەیتەوە چی گەڕانێک دەکات بە بێزانیاری (کوێرانە) یان زانیاریدار.
بە ، ، و بە بەکارهێنانی b، d و m بەراورد بکەیت.

Why do agents search?بۆچی ئەیجێنتەکان دەگەڕێن؟

Search algorithms are one of the most important areas of . Search techniques are universal problem-solving methods: the same few ideas solve route planning, puzzles, games and many other problems.

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

A that solves problems often cannot reach its goal with one single move. It needs a sequence of . So it first searches for that sequence and only then carries it out. This is why problem-solving agents use search algorithms so often: to find a solution and, when possible, the best one.

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

Such an agent is a Goal-based agent: it knows what it wants (the goal) and asks “which actions take me there?”. This chapter answers that question.

ئەم جۆرە ئەیجێنتی ئامانجخوازە: دەزانێت چی دەوێت (ئامانجەکە) و دەپرسێت «کام دەمگەیەننە ئەوێ؟». ئەم بەشە وەڵامی ئەو پرسیارە دەداتەوە.

Planning a walkپلاندانان بۆ ڕێکردن

Before you walk to a place you have never visited, you plan in your head: “From home I can go to the bazaar or to the park. From the park I can reach the teahouse…”. You try routes in your mind before you take one real step. A search algorithm does the same thing inside the computer.

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

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

You also use common sense, such as “the school is to the east”. A blind (uninformed) search algorithm has no such hints: it only knows which places are next to which.

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

Quick checkپشکنینی خێراWhy does a problem-solving agent search before it acts?بۆچی کە کێشە چارەسەر دەکات پێش کارکردن دەگەڕێت؟To switch on its sensorsبۆ هەڵکردنی هەستەوەرەکانیTo find a sequence of actions that leads to its goalبۆ دۆزینەوەی زنجیرەیەک کردەوە کە دەیگەیەنێتە ئامانجەکەیBecause searching is always faster than actingچونکە گەڕان هەمیشە لە کارکردن خێراترە

What is a search problem?کێشەی گەڕان چییە؟

In the lecture, search is a step-by-step procedure for solving a in a given search space. A search problem has three main factors:

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

Search space (): all the situations the agent could be in.
Start state (): the state where the agent begins the search.
: a function that looks at the current state and answers “is this the goal?” (true or false).

فەزای گەڕان (): هەموو ئەو بارانەی کە دەکرێت تێیاندا بێت.
دۆخی دەستپێک (): ئەو کە گەڕانەکەی لێوە دەست پێدەکات.
: کە سەیری ئێستا دەکات و وەڵامی «ئایا ئەمە ئامانجە؟» دەداتەوە (ڕاست یان هەڵە).

Definitionپێناسە

The set of all states that can be reached from the initial state by any sequence of actions.

کۆمەڵەی هەموو ئەو کە دەکرێت لە بە هەر زنجیرەیەکی کار پێیان بگەیت.

Search space = all states, not all solutionsفەزای گەڕان = هەموو دۆخەکان، نەک هەموو چارەسەرەکان

The lecture defines the search space as “a set of possible solutions”. More exactly, it is the set of all possible states: every situation the agent can reach from the initial state. A solution is not one state. It is a path through several states, from the start to a goal. Example: in a maze, the states are the open cells; a solution is a route of cells from the entrance to the exit.

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

Search - Lecture 0 - CS50's Introduction to Artificial Intelligence with Python 2020CS50 · Englishئینگلیزی · 190K viewsبینین · 3.8K likesلایک · Partبەشی 3:14–14:17 (ofلە 1:49:29)
Harvard's CS50 AI lecture on search: the parts of a search problem, the frontier loop, DFS and BFS on mazes, and greedy best-first search.
وانەی گەڕان لە کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard: بەشەکانی ، ، و لەسەر ، هەروەها .
Watch 3:14-14:17: the parts of a search problem: initial state, actions, transition model, state space, goal test and path cost.
لە ⁦3:14⁩ تا ⁦14:17⁩ سەیر بکە: بەشەکانی ، واتە ، ، ، ، و .

What is a search problem?کێشەی گەڕان چییە؟

Actions, transitions and costsکردەوەکان، گواستنەوە و کۆست

The lecture then adds the other parts. Together they describe a search problem completely:

پاشان وانەکە بەشەکانی تر زیاد دەکات. هەموویان پێکەوە بە تەواوی وەسف دەکەن:

The components of a search problemبەشەکانی
Componentبەش	What it tells usچیمان پێ دەڵێت
	All the states the agent can be in.هەموو ئەو دەکرێت تێیاندا بێت.
	Where the search begins.گەڕان لە کوێوە دەست پێدەکات.
	A description of all the actions available to the agent in a state.وەسفی هەموو ئەو لە بۆ بەردەستن.
	What each action does: the state you reach when you do action a in state s.هەر چی دەکات: ئەو پێی دەگەیت کاتێک لە sدا a دەکەیت.
	Is this state a goal state?ئایا ئەم ؟
	A function that gives each path a number (a cost). Usually it is the sum of the step costs: the cost of each single action. کە ژمارەیەک (کۆستێک) دەدات بە هەر . زۆرجار کۆی : کۆستی هەر تاک.

Definitionپێناسە

A description of what each action does: given a state and an action, it gives the resulting state. Model-based agents and search algorithms both need one.

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

Example: walking to schoolنموونە: ڕێکردن بۆ قوتابخانە

Let us describe a real problem with these words. Aram wants to walk from home to school. The map below shows six places and the roads between them. Each number is the time in minutes to walk along that road.

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

Aram's town: each place is a state, each road is an action, each number is a step cost.شارۆچکەکەی ئارام: هەر شوێنێک ، هەر ڕێگایەک و هەر ژمارەیەک .CêIT

The walk to school as a search problemڕێکردن بۆ قوتابخانە وەک
Componentبەش	Aram's walkڕێکردنەکەی ئارام
	The six places: Home, Bazaar, Park, Teahouse, Library, School.شەش شوێنەکە: ماڵ، بازاڕ، پارک، چایخانە، کتێبخانە، قوتابخانە.
	Home.ماڵ.
	Walk along one road to a neighbouring place. In Park: “go to Home” or “go to Teahouse”.ڕێکردن لەسەر یەک ڕێگا بۆ شوێنێکی دراوسێ. لە پارک: «بڕۆ بۆ ماڵ» یان «بڕۆ بۆ چایخانە».
	Result(Park, go to Teahouse) = Teahouse.Result(پارک، بڕۆ بۆ چایخانە) = چایخانە.
	Is the place School?ئایا شوێنەکە قوتابخانەیە؟
/ /	Minutes on one road / the sum of the minutes along a route.خولەکەکانی یەک ڕێگا / کۆی خولەکەکان بە درێژایی ڕێگەیەک.

The same problem written in Pythonهەمان کێشە بە Pythonproblem.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# A search problem written as data: walking from home to school.
# Roads and the minutes each road takes (a road works in both directions).
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},
}

initial_state = "Home"


def actions(state):
    """The actions possible in a state: walk to a neighbouring place."""
    return ["go to " + place for place in roads[state]]


def result(state, action):
    """Transition model: the state an action leads to."""
    return action.replace("go to ", "")


def goal_test(state):
    return state == "School"


def path_cost(path):
    """Add up the step costs (minutes) along a path of states."""
    return sum(roads[a][b] for a, b in zip(path, path[1:]))


print("States:", list(roads))
print("Actions in Park:", actions("Park"))
print("Result(Park, 'go to Teahouse'):", result("Park", "go to Teahouse"))
print("Is Library a goal?", goal_test("Library"))
print("Cost of Home-Bazaar-School:", path_cost(["Home", "Bazaar", "School"]))
print("Cost of Home-Park-Teahouse-Library-School:",
      path_cost(["Home", "Park", "Teahouse", "Library", "School"]))

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

Lineدێڕی 3-10

The roads as a : each place maps to its neighbours and the minutes to reach them.

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

Lineدێڕی 15-17

actions() lists what Aram can do in a state.

actions() ئەوە ڕیز دەکات کە ئارام دەتوانێت لە بیکات.

Lineدێڕی 20-22

result() is the transition model.

result() .

Lineدێڕی 25-26

goal_test() answers True or False.

goal_test() وەڵامی True یان False دەداتەوە.

Lineدێڕی 29-31

path_cost() adds the step costs of a route. zip(path, path[1:]) gives the pairs of neighbouring places on the route.

path_cost() ڕێگەیەک کۆ دەکاتەوە. zip(path, path[1:]) جووتی شوێنە یەک لە دوای یەکەکانی سەر ڕێگەکە دەدات.

The program does not search yet. It only describes the problem. The search algorithms in the next lessons use exactly these four functions: actions, result, goal test and cost.

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

Example: walking to schoolنموونە: ڕێکردن بۆ قوتابخانە

The lab maze is a search problem tooلابیرینتەکەی تاقیگە کێشەیەکی گەڕانە

The maze of Lab 2 (taught in Solving a maze with DFS and BFS) fits the same pattern:

تاقیگەی 2 (کە لە چارەسەرکردنی لابیرینت بە DFS و BFS دەیخوێنیت) هەمان شێوەی هەیە:

States: the open cells, written (row, column).
Initial state: (0, 0). Goal test: is the cell (4, 8)?
Actions: up, left, down, right (or 8 moves with the diagonals).
Transition model: add the move to the cell, for example (2, 3) + up = (1, 3), unless the new cell is a wall or outside the maze.
Step cost: 1 for every move, so the path cost is the number of moves.

: خانە کراوەکان، بە شێوەی (ڕیز، ستوون) دەنووسرێن.
: ⁦(0, 0)⁩. : ئایا خانەکە ⁦(4, 8)⁩ە؟
: سەرەوە، چەپ، خوارەوە، ڕاست (یان 8 جووڵە لەگەڵ لارەکان).
: جووڵەکە بخەرە سەر خانەکە، بۆ نموونە ⁦(2, 3) +⁩ سەرەوە = ⁦(1, 3)⁩، مەگەر خانە نوێیەکە دیوار بێت یان لە دەرەوەی بێت.
: هەر جووڵەیەک 1، بۆیە ژمارەی جووڵەکانە.

Both examples leave out details that do not matter for the question, such as the weather or the colour of the walls. Choosing what to keep in the states and actions is called : a good formulation keeps only what the search needs.

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

Solutions and the optimal solutionچارەسەر و باشترین چارەسەر

A solution is an action sequence that leads from the start node to a goal node.
An (the best solution) is the solution with the lowest path cost among all solutions.

چارەسەر زنجیرەیەک کە لە دەستپێکەوە دەگاتە ئامانج.
ئەو چارەسەرەیە کە لە ناو هەموو چارەسەرەکاندا کەمترین هەیە.

Three solutions on the town mapسێ چارەسەر لەسەر نەخشەی شارۆچکەکە
Route from Home to Schoolڕێگە لە ماڵەوە بۆ قوتابخانە	Roadsڕێگاکان	Minutesخولەک
Home → Bazaar → Schoolماڵ ← بازاڕ ← قوتابخانە	2	4 + 6 = 10
Home → Park → Teahouse → Library → Schoolماڵ ← پارک ← چایخانە ← کتێبخانە ← قوتابخانە	4	2 + 3 + 2 + 2 = 9
Home → Bazaar → Teahouse → Library → Schoolماڵ ← بازاڕ ← چایخانە ← کتێبخانە ← قوتابخانە	4	4 + 5 + 2 + 2 = 13

All three routes are solutions, because each one reaches School. The optimal solution is the 9-minute route. Notice that it uses more roads (4) than the 10-minute route (2). “Optimal” means lowest cost, not fewest steps. When every step costs the same, the two ideas agree.

هەر سێ ڕێگاکە چارەسەرن، چونکە هەریەکەیان دەگاتە قوتابخانە. ڕێگە 9 خولەکییەکەیە. سەرنج بدە کە ڕێگای زیاتر بەکار دەهێنێت ⁦(4)⁩ لە ڕێگە ⁦10⁩ خولەکییەکە ⁦(2)⁩. «باشترین» واتە کەمترین کۆست، نەک کەمترین هەنگاو. کاتێک هەموو هەنگاوێک هەمان کۆستی هەبێت، ئەم دوو بیرۆکەیە یەک دەگرنەوە.

Quick checkپشکنینی خێراWhich route is the optimal solution on the town map?کام ڕێگە نەخشەی شارۆچکەکەیە؟Any route that reaches Schoolهەر ڕێگەیەک کە بگاتە قوتابخانەHome → Bazaar → School, because it has the fewest roadsماڵ ← بازاڕ ← قوتابخانە، چونکە کەمترین ڕێگای هەیەHome → Park → Teahouse → Library → School, because it costs the fewest minutesماڵ ← پارک ← چایخانە ← کتێبخانە ← قوتابخانە، چونکە کەمترین خولەک دەخایەنێت

State-space graph and search treeگرافی فەزای دۆخەکان و داری گەڕان

The lecture: a is a tree representation of a search problem. Its root is the , and it corresponds to the initial state.

وانەکە: نواندنێکی دارئاسای . ڕەگەکەی و بەرامبەر دەوەستێت.

Do not mix it up with the . In the graph, each state appears once: the town map itself is one. The search tree is built while searching. Each node in it stands for a whole path from the root, so the same state can appear many times. On the town map, Home → Bazaar → Home is a path, so Home appears again under Bazaar. Because of such loops the tree can even be infinite, while the map has only six places.

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

A search tree repeats states; the explored set stops the repeats. دووبارە دەکاتەوە؛ ڕێگری لە دووبارەبوونەوە دەکات.CêIT

Quick checkپشکنینی خێراHow many times can the state “Home” appear in the search tree of the town map? «ماڵ» چەند جار دەکرێت لە نەخشەکەدا دەربکەوێت؟Many times, once for every path that reaches itچەند جار، یەک جار بۆ هەر ڕێگەیەک کە پێی دەگاتNever, the root is not a stateهەرگیز، ڕەگ دۆخ نییەExactly once, like in the mapتەنها یەک جار، وەک لە نەخشەکەدا

State-space graph and search treeگرافی فەزای دۆخەکان و داری گەڕان

Nodes, the frontier and the explored setنۆدەکان، بەرە و کۆمەڵەی پشکنراو

Four words describe what happens inside every search algorithm:

چوار وشە ئەوە وەسف دەکەن کە لە ناو هەموو ڕوودەدات:

A holds a state plus how we got there: its parent node, the action and the path cost so far.
: take a node and make all its children, one for each possible action.
The (also called the OPEN list): nodes that were made but not yet expanded. They wait their turn.
The (also called the CLOSED list): states that were already expanded, so we do not expand them again. A search that keeps an explored set is called graph search; without one, tree search can expand the same state many times.

هەڵدەگرێت لەگەڵ ئەوەی چۆن گەیشتینە ئەوێ: ، و تا ئێستا.
: وەرگرە و هەموو منداڵەکانی دروست بکە، بۆ هەر ئەگەری یەک منداڵ.
(کە پێی دەوترێت لیستی OPENـیش): ئەو دروست کراون بەڵام هێشتا فراوان نەکراون. چاوەڕێی نۆرەی خۆیان دەکەن.
(کە پێی دەوترێت لیستی CLOSEDـیش): ئەو پێشتر فراوان کراون، بۆ ئەوەی دووبارە فراوانیان نەکەینەوە. گەڕانێک کە هەڵدەگرێت پێی دەوترێت graph search؛ بەبێ ئەو، tree search دەکرێت هەمان چەند جار فراوان بکات.

The general search loopخولی گشتیی گەڕان

Empty?بەتاڵە؟
If the frontier is empty, stop: there is no solution.
ئەگەر بەتاڵ بوو، بوەستە: هیچ چارەسەرێک نییە.
Removeدەرهێنان
Remove one node from the frontier. Which one depends on the algorithm.
لە دەربهێنە. کامیان بەندە بە .
Goal?ئامانجە؟
If its state is a goal, stop and return the path to it.
ئەگەر ئامانج بوو، بوەستە و ڕێگەکەی بگەڕێنەوە.
Recordتۆمارکردن
Add its state to the explored set.
بخەرە ناو .
Expandفراوانکردن
Expand it: add each child whose state is not explored and not already in the frontier. Go back to step 1.
فراوانی بکە: هەر منداڵێک کە نەپشکنراوە و لە نییە زیادی بکە. بگەڕێوە بۆ هەنگاوی 1.

Breadth-first, depth-first and uniform-cost search all run this loop, and the main difference is step 2: breadth-first search removes the oldest node (a ), depth-first search the newest (a ) and uniform-cost search the cheapest (a ). The other uninformed algorithms change the loop a little: depth-limited search adds a depth limit, and bidirectional search runs two loops at once.

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

Uninformed (blind) searchگەڕانی بێزانیاری

has no domain knowledge such as how close the goal is or where it is.
It works in a brute-force way: it only knows how to move through the tree and how to recognise leaf nodes and goal nodes.
It searches the tree with nothing more than the problem definition (the initial state, the actions — also called operators — and the goal test). That is why it is also called blind search.

هیچ زانیارییەکی تایبەت بە بوارەکەی نییە، وەک ئەوەی ئامانج چەند نزیکە یان لە کوێیە.
بە شێوەی هێزی ڕووت (brute force) کار دەکات: تەنها دەزانێت چۆن بە ناو بڕوات و چۆن و ئامانج بناسێتەوە.
تەنها بە پێناسەی کێشەکە دەپشکنێت (، — کە پێیان دەوترێت operatorsـیش — و ). بۆیە پێی دەوترێت گەڕانی کوێرانەش.

The report on uninformed search explains it like this: it is a way to solve a problem when you have no extra information about the solution. It looks at all the options step by step until it finds the answer. It is like exploring a maze without knowing which direction is right: you keep trying paths until you reach the goal, with no clue about how close you are.

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

Its main idea is to explore systematically. It assumes nothing about the distance or the cost to the goal. It goes through the possibilities in an organised way — one step at a time, or level by level — until it reaches the goal. This makes it simple to understand, but sometimes slow: with no hints it may explore many useless paths, so time and memory must be watched carefully.

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

Quick checkپشکنینی خێراHow does uninformed search go through the possibilities? چۆن بە ناو ئەگەرەکاندا دەڕوات؟It tries random actions until it is luckyکردەوەی هەڕەمەکی تاقی دەکاتەوە تا بەختی دەبێتIt jumps straight to the state that is closest to the goalڕاستەوخۆ باز دەداتە ئەو دۆخەی کە لە ئامانجەوە نزیکترەSystematically, step by step or level by level, with no hint about where the goal isبە شێوەیەکی ڕێکخراو، هەنگاو بە هەنگاو یان ئاست بە ئاست، بەبێ هیچ نیشانەیەک کە ئامانج لە کوێیە

Uninformed (blind) searchگەڕانی بێزانیاری

Searching in the darkگەڕان لە تاریکیدا

Uninformed search is like searching in the dark. You can feel the walls and the doors — the structure of the problem, its tree or graph — but you have no light to show which way is best or shortest.

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

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

In a real dark room you still remember things, for example where you usually leave your keys. Blind search has no such memory of the goal; that kind of hint is exactly what informed search adds.

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

Not every uninformed search is completeهەموو گەڕانێکی بێزانیاری تەواو نییە

The report says uninformed searches “guarantee a solution if one exists”. That is true for breadth-first search, uniform-cost search (with positive step costs) and iterative deepening, but not for all of them: depth-first search can follow an endless path or a loop, and depth-limited search fails when the goal is deeper than its limit.

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

The opposite is (heuristic search). It also uses knowledge about the problem — usually an estimate of how far each state is from the goal, called a . The lecture names best-first search and A* as examples; they come later in this chapter: greedy best-first search and A* search.

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

Quick checkپشکنینی خێراWhat does an uninformed search algorithm know? بێزانیاری چی دەزانێت؟The optimal solution before it startsباشترین چارەسەر پێش ئەوەی دەست پێبکاتOnly the problem definition: start, actions and goal testتەنها پێناسەی کێشەکە: دەستپێک، کردەوەکان و پشکنینی ئامانجAn estimate of the distance to the goalخەمڵاندنی دووریی ئامانج

Uninformed (blind) searchگەڕانی بێزانیاری

The idea and the algorithmsبیرۆکەکە و ئەلگۆریزمەکان

The report separates two expressions that sound alike:

ڕاپۆرتەکە دوو دەربڕین لێک جیا دەکاتەوە کە وەک یەک دەنگ دەدەن:

Aspectلایەن	“Uninformed search”دەستەواژەی «»	“An uninformed search algorithm”دەستەواژەی « بێزانیاری»
What it isچییە	The general approach: explore the possible solutions without any extra knowledge about the problem.ڕێبازی گشتی: پشکنینی چارەسەرە ئەگەرییەکان بەبێ هیچ زانیارییەکی زیادە دەربارەی کێشەکە.	A specific step-by-step method that follows this approach.ڕێگایەکی دیاریکراوی هەنگاو بە هەنگاو کە پەیڕەوی ئەم ڕێبازە دەکات.
Exampleنموونە	The idea of searching in the dark.بیرۆکەی گەڕان لە تاریکیدا.	Breadth-first search, depth-first search, iterative deepening, bidirectional search (and uniform-cost and depth-limited search).، ، ، (و و ).

The algorithms differ in how they explore the search space, and each one suits different needs, such as low memory use or speed. But none of them uses extra information about the solution: they are tools inside the larger idea of uninformed search.

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

Noteتێبینی

The report says these algorithms do not know “how far away the goal is or how costly it is to take a particular path”. Be careful with the second part: uniform-cost search does add up the cost of the path it has already walked. What no uninformed algorithm has is an estimate of the cost that is still ahead, to the goal.

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

How do we compare search algorithms?چۆن ئەلگۆریزمەکانی گەڕان بەراورد دەکەین؟

We judge every search algorithm with four questions:

هەموو بە چوار پرسیار هەڵدەسەنگێنین:

: if a solution exists, is it sure to find one?
: is the solution it finds always an optimal (lowest-cost) solution?
: how many nodes does it make (or expand) in the worst case?
: how many nodes must it keep in memory at the same time?

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

To answer the last two questions we use three letters:

بۆ وەڵامدانەوەی دوو پرسیارەکەی کۆتایی سێ پیت بەکار دەهێنین:

b — the : how many children a node has (at most, or on average).
d — the of the shallowest goal: the fewest steps from the root to a goal. (Some notes, such as Berkeley's CS188, write s for it.)
m — the of the tree; it can be infinite.

b — : چەند منداڵی هەیە (زۆرترین، یان بە تێکڕا).
d — نزیکترین ئامانج: کەمترین هەنگاو لە ڕەگەوە تا ئامانجێک. (هەندێک سەرچاوە، وەک ⁦CS188⁩ی بێرکلی، sی بۆ دەنووسن.)
m — دارەکە؛ دەکرێت بێسنوور بێت.

A node has b children, each child has b children, and so on. So depth k holds about b^k nodes. The table shows how fast this grows when b = 10:

b منداڵی هەیە، هەر منداڵێک b منداڵی هەیە و بەم شێوەیە. بۆیە k نزیکەی b^k لەخۆ دەگرێت. ئەم خشتەیە پیشانی دەدات کاتێک b = ⁦10⁩ بێت چەند خێرا گەورە دەبێت:

Exponential growth: b = 10: ⁦b = 10⁩
Depth dقووڵایی d	Nodes at that depth (10^d)ژمارەی لەو قووڵاییەدا (⁦10⁩^d)
2	100
4	10,000
6	1,000,000
8	100,000,000
10	10,000,000,000

Nodes, not secondsنۆدەکان، نەک چرکە

Complexity is counted in nodes (or steps), not in seconds or bytes. Seconds depend on the computer; the number of nodes depends only on the algorithm and the problem. We write it with (see Big-O in one screen): breadth-first search takes O(b^d) time, which means “it grows like b^d”.

ئاڵۆزی بە (یان هەنگاو) دەژمێردرێت، نەک بە چرکە یان بایت. چرکە بەندە بە کۆمپیوتەرەکە؛ ژمارەی تەنها بەندە بە و کێشەکە. بە دەینووسین (بڕوانە ⁦Big-O⁩ لە یەک شاشەدا): کاتی ⁦O(b⁩^d) دەخایەنێت، واتە «وەک b^d گەورە دەبێت».

The family of search algorithmsخێزانی ئەلگۆریزمەکانی گەڕان

The lecture ends with a map of the algorithms. It is the plan of this whole chapter:

وانەکە بە نەخشەیەکی کۆتایی دێت. ئەمە پلانی هەموو ئەم بەشەیە:

Six uninformed and two informed algorithms: the plan of this chapter.شەش بێزانیاری و دوو زانیاریدار: پلانی ئەم بەشە.CêIT

Breadth-first and depth-first search: Depth-first and breadth-first search, then the lab Solving a maze.
Uniform-cost, depth-limited, iterative deepening and bidirectional search: More uninformed search.
Greedy best-first search and A: Greedy best-first search and [A search](ai-a-star-search).

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

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

Mistakeهەڵە	Betterباشتر
“The search space is the set of solutions.”«فەزای گەڕان کۆمەڵەی چارەسەرەکانە.»	It is the set of all states. A solution is a path through states.کۆمەڵەی هەموو . چارەسەر ڕێگەیەکە بە ناو .
“The search tree and the map are the same thing.”« و نەخشەکە هەمان شتن.»	The map (state-space graph) has each state once; the search tree can repeat states and even be infinite.نەخشەکە () هەر یەک جار تێدایە؛ دەتوانێت دووبارە بکاتەوە و تەنانەت بێکۆتاش بێت.
“The optimal solution is the one with the fewest steps.”« ئەوەیە کە کەمترین هەنگاوی هەیە.»	It is the one with the lowest path cost. Fewest steps = lowest cost only when all steps cost the same.ئەوەیە کە کەمترین هەیە. کەمترین هەنگاو تەنها کاتێک کەمترین کۆستە کە هەموو هەنگاوەکان هەمان کۆستیان هەبێت.
Mixing up the frontier and the explored set.تێکەڵکردنی و .	Frontier = waiting to be expanded. Explored = already expanded. = چاوەڕێی فراوانکردنە. پشکنراو = پێشتر فراوان کراوە.
“Every uninformed search finds a solution if there is one.”« هەمیشە چارەسەر دەدۆزێتەوە ئەگەر هەبێت.»	Depth-first and depth-limited search can fail. و دەکرێت سەرنەکەون.
Measuring time complexity in seconds.پێوانەکردنی بە چرکە.	Count nodes (or steps) as a function of b, d and m. (یان هەنگاوەکان) بژمێرە وەک b، d و m.

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

ExerciseڕاهێنانThe 8-puzzleمەتەڵی 8

Describe the 8-puzzle as a search problem. (Eight numbered tiles and one blank square sit on a 3 × 3 board. A tile next to the blank can slide into it. The goal is to put the tiles in order 1–8 with the blank in the corner.) Give the states, the initial state, the actions, the transition model, the goal test and the path cost.

مەتەڵی 8 وەک وەسف بکە. (هەشت پارچەی ژمارەدار و یەک خانەی بەتاڵ لەسەر تەختەیەکی ⁦3 × 3⁩ن. پارچەیەک کە لە تەنیشت خانە بەتاڵەکەوەیە دەتوانێت بخزێتە ناوی. ئامانج ئەوەیە پارچەکان بە ڕیزی ⁦1–8⁩ دابنرێن و خانە بەتاڵەکە لە گۆشەدا بێت.) ، ، ، ، و بنووسە.

Hintئاماژە

Ask: what changes from one moment to the next? That is the state.

بپرسە: چی لە ساتێکەوە بۆ ساتێکی تر دەگۆڕێت؟ ئەوە .

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

Componentبەش	8-puzzleمەتەڵی 8
States	Every arrangement of the eight tiles and the blank on the board.هەموو شێوەیەکی ڕیزبوونی هەشت پارچەکە و خانە بەتاڵەکە لەسەر تەختەکە.
Initial state	Any given mixed-up board.هەر تەختەیەکی تێکچووی دراو.
Actions	Move the blank up, down, left or right (only where the board allows).جووڵاندنی خانە بەتاڵەکە بۆ سەرەوە، خوارەوە، چەپ یان ڕاست (تەنها لەو شوێنەی تەختەکە ڕێگە دەدات).
Transition model	The board after the blank and the tile next to it swap places.تەختەکە دوای ئەوەی خانە بەتاڵەکە و پارچەی تەنیشتی شوێن دەگۆڕنەوە.
Goal test	Is the board in the goal order?ئایا تەختەکە بە ڕیزی ئامانجە؟
Path cost	1 per move, so the number of moves.هەر جووڵەیەک 1، واتە ژمارەی جووڵەکان.

ExerciseڕاهێنانFrontier and explored set by handبەرە و کۆمەڵەی پشکنراو بە دەست

Use the general search loop on the town map. Start with the frontier [Home] and an empty explored set. (1) Remove and expand Home. (2) Then remove and expand Bazaar. After each step, write the frontier and the explored set.

خولی گشتیی گەڕان لەسەر نەخشەی شارۆچکەکە بەکار بهێنە. بە [ماڵ] و بەتاڵ دەست پێبکە. ⁦(1)⁩ ماڵ دەربهێنە و فراوانی بکە. ⁦(2)⁩ پاشان بازاڕ دەربهێنە و فراوانی بکە. دوای هەر هەنگاوێک و بنووسە.

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

After (1): frontier = {Bazaar, Park}; explored = {Home}.
After (2): Bazaar's children are Home, School and Teahouse. Home is already explored, so it is skipped. Frontier = {Park, School, Teahouse}; explored = {Home, Bazaar}. This is the moment shown in the search-tree figure.

دوای ⁦(1)⁩: = {بازاڕ، پارک}؛ پشکنراو = {ماڵ}.
دوای ⁦(2)⁩: منداڵەکانی بازاڕ ماڵ، قوتابخانە و چایخانەن. ماڵ پێشتر پشکنراوە، بۆیە جێدەهێڵرێت. = {پارک، قوتابخانە، چایخانە}؛ پشکنراو = {ماڵ، بازاڕ}. ئەمە ئەو ساتەیە کە لە وێنەی سەرەوەدا پیشان دراوە.

School is in the frontier now, but the search has not found it yet: the goal test runs when a node is removed.

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

ExerciseڕاهێنانCounting nodesژماردنی نۆدەکان

A tree has branching factor b = 2. How many nodes are at depth 5? How many nodes are there in total from depth 0 to depth 5?

⁦b = 2⁩ی هەیە. چەند لە 5دان؟ لە 0ەوە تا 5 کۆی گشتی چەند هەیە؟

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

At depth 5: 2^5 = 32 nodes. In total: 1 + 2 + 4 + 8 + 16 + 32 = 63 nodes. The last level alone holds about half of all the nodes.

لە ⁦5: 2⁩^⁦5 = 32⁩ . کۆی گشتی: ⁦1 + 2 + 4 + 8 + 16 + 32 = 63⁩ . ئاستی کۆتایی بە تەنها نزیکەی نیوەی هەموو لەخۆ دەگرێت.

Summaryپوختە

A search problem has a state space, an initial state, actions, a transition model, a goal test and a path cost.
A solution is a path from the start to a goal; the optimal solution has the lowest path cost.
The state-space graph has each state once; the search tree repeats states, so we keep an explored set.
Breadth-first, depth-first and uniform-cost search run the same loop; they differ mainly in which frontier node they remove.
We compare algorithms by completeness, optimality, time and space, counted in nodes with b, d and m.

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

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

What are the three main factors of a search problem in the lecture?سێ هۆکارە سەرەکییەکەی کێشەی گەڕان لە وانەکەدا چین؟

The search (state) space, the start state and the goal test.

فەزای گەڕان ()، و .

Why can a search tree be infinite when the map is small?بۆچی داری گەڕان دەتوانێت بێکۆتا بێت کاتێک نەخشەکە بچووکە؟

Because a path can go round a loop again and again (Home → Bazaar → Home …), and every path is a new node.

چونکە ڕێگەیەک دەتوانێت جار لە دوای جار بە دەوری بازنەیەکدا بسووڕێتەوە (ماڵ ← بازاڕ ← ماڵ …) و هەر ڕێگەیەک نوێیە.

Why is uninformed search also called blind search?بۆچی گەڕانی بێزانیاری پێی دەوترێت گەڕانی کوێرانەش؟

It searches with only the problem definition: no hint about where the goal is or how close it is.

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

What do b, d and m mean?b، d و m واتای چییە؟

b = branching factor, d = depth of the shallowest goal, m = maximum depth of the tree.

b = ، d = نزیکترین ئامانج، m = دارەکە.

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

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

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

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

Depth-First and Breadth-First Searchگەڕانی قووڵایی و گەڕانی پانایی

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