بحث
مُقدَّم
مفردات
| English | المعنى |
|---|---|
| search tree | A tree of states and possible moves explored when solving a search problem. |
| heuristic/hjuːˈrɪstɪk/ | An estimate used to guide search, such as an estimate of the remaining path cost. |
English
The tree and the estimate
- A search tree: nodes are states, edges are moves. Uninformed search expands blindly — breadth-first (BFS, shortest when steps equal), depth-first (DFS, frugal memory). Informed search uses a heuristic $h(n)$: A* search picks the node minimising $f = g + h$.
{exercise:uni-cs1301-astar}
تدريب
A* chooses the node minimising —
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Cost so far plus admissible estimate to go.
English
The course route, exactly
- Course graph: D→A (4), D→B (2), A→C (3), B→C (1), C→G (5), B→G (9); $h = \{A{:}8, B{:}6, C{:}5, G{:}0\}$. A* pops D (0), B (8), C (8), G (8): optimal cost 8 via D→B→C→G, four expansions — BFS visits every node.
- Admissibility is the contract: $h(n) \le h^*(n)$ guarantees the first goal pop is optimal, because $f$ at that pop is a lower bound no open node can beat.
{exercise:uni-cs1301-trace}
تدريب
On the course graph, A* expands — nodes before the goal
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Pops D, B, C, then G at cost 8 - four expansions.
English
When the heuristic lies
- Overestimate $h(C) = 12$: C carries $f = 3 + 12 = 15$ while Goal-through-B carries $11$ — A* pops the Goal at cost 11 and stops: suboptimal ($11 > 8$).
- Complete (finds a solution) is not optimal (finds the best); BFS's frontier costs $O(b^d)$ memory.
{exercise:uni-cs1301-lies}
تدريب
Overestimating h(C) to 12 makes A* return cost —
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
C carries f=15 vs Goal 11: pops Goal early - trusts a lie.