> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/ai-college-notes/practical-2-b-a-search-algorithm.md). # Practical 2(B) - A\* Search Algorithm **Language used:** Python 3 (standard library `queue` module, plus a helper module called `RMP` containing the map data) **Aim:** Implement the A\* search algorithm to find the shortest path between two cities, using both real road distances and an estimate of remaining distance to guide the search intelligently. *** ### 6.1 Before the code: what is A\*, in plain English Practical 1 (BFS) and Practical 2 (DFS) were both **uninformed search**. They had no idea how far away the goal actually was, they just blindly explored the map. A\* is **informed search**. It uses an extra piece of knowledge: an estimate, called a **heuristic**, of how far the current city is from the goal in a straight line. Combining the real cost so far with this estimate lets A\* make much smarter decisions about which path to explore next, instead of wandering randomly. For every possible path being considered, A\* calculates a score: ``` f(n) = g(n) + h(n) ``` | Term | Meaning | | ------ | ---------------------------------------------------------------------------------------------------------------------------------- | | `g(n)` | The actual cost already travelled to reach the current city, added up from the real road distances | | `h(n)` | The heuristic, an estimate of the remaining distance from the current city to the goal (here, straight line distance to Bucharest) | | `f(n)` | The total estimated cost of a path if it is completed through the current city | A\* always expands the path with the **lowest f(n)** next, which means it balances "how far have I already come" against "how much further do I probably have to go," instead of only looking at one or the other. ```mermaid flowchart TD Start[Start city] --> Calc["Calculate f = g + h for every path being tracked"] Calc --> Pick[Pick the path with the lowest f score] Pick --> Check{Is the last city in that path the goal?} Check -->|yes| Done[Stop, this is the answer] Check -->|no| Expand[Extend this path to each neighbour city, calculate new f scores] Expand --> Calc ``` *** ### 6.2 The map and the heuristic Same Romania road map used in earlier practicals, but this time every city also has a straight line distance to Bucharest, used as the heuristic. ```mermaid graph LR Arad --75--- Zerind Arad --140--- Sibiu Arad --118--- Timisoara Zerind --71--- Oradea Oradea --151--- Sibiu Sibiu --99--- Fagaras Sibiu --80--- Rimnicu Fagaras --211--- Bucharest Rimnicu --146--- Craiova Rimnicu --97--- Pitesti Pitesti --101--- Bucharest Craiova --120--- Drobeta Drobeta --75--- Mehadia Mehadia --70--- Lugoj Lugoj --111--- Timisoara Bucharest --90--- Giurgiu Bucharest --85--- Urziceni ``` | City | Straight line distance to Bucharest (heuristic) | | --------- | ----------------------------------------------- | | Arad | 366 | | Sibiu | 253 | | Rimnicu | 193 | | Pitesti | 100 | | Fagaras | 176 | | Bucharest | 0 | Notice how the heuristic values naturally get smaller and smaller as cities get physically closer to Bucharest, ending at exactly 0 once you are already there. This map and heuristic data lives in a separate file, imported as a module named `RMP` (Romania Map Problem), which is why the code begins with: ```python from RMP import dict_gn from RMP import dict_hn ``` `dict_gn` holds the real road distances between neighbouring cities, exactly like earlier practicals. `dict_hn` is new, it holds the straight line heuristic distance from every city to Bucharest. *** ### 6.3 The full code ```python import queue as q from RMP import dict_gn from RMP import dict_hn start = 'Arad' goal = 'Bucharest' result = '' def get_fn(citystr): cities = citystr.split(",") gn = 0 # calculate gn (cost from start to current node) for ctr in range(0, len(cities) - 1): gn = gn + dict_gn[cities[ctr]][cities[ctr + 1]] # calculate hn (heuristic cost from current node to goal) # the last city in the path is the current city for heuristic calculation hn = dict_hn[cities[-1]] return (gn + hn) def main(): global result cityq = q.PriorityQueue() # the priority queue stores tuples: (f_score, path_string, current_city) # f_score is (g_score + h_score) # path_string keeps track of the cities visited to reach the current city # current_city is the last city in the path_string cityq.put((get_fn(start), start, start)) while not cityq.empty(): f_score, current_path_str, current_city = cityq.get() if current_city == goal: result = current_path_str + "::" + str(f_score) break for neighbor_city in dict_gn[current_city]: new_path_str = current_path_str + ',' + neighbor_city new_f_score = get_fn(new_path_str) cityq.put((new_f_score, new_path_str, neighbor_city)) print("the A* path with the total is: ") print(result) main() ``` *** ### 6.4 Line by line explanation #### Imports and setup ```python import queue as q ``` Brings in Python's built in queue module. This time we need a special kind of queue called a **priority queue**, explained below. ```python from RMP import dict_gn from RMP import dict_hn ``` Imports the two dictionaries described in section 6.2, from a separate helper file called `RMP.py`. ```python start = 'Arad' goal = 'Bucharest' result = '' ``` Same idea as earlier practicals, the starting city, the goal city, and an empty string to eventually hold the final answer. #### The `get_fn` function: calculating f(n) for a whole path ```python def get_fn(citystr): cities = citystr.split(",") ``` This function receives a path as a single comma separated string, for example `"Arad,Sibiu,Rimnicu"`, and splits it back into a list of individual city names, `['Arad', 'Sibiu', 'Rimnicu']`. ```python gn = 0 for ctr in range(0, len(cities) - 1): gn = gn + dict_gn[cities[ctr]][cities[ctr + 1]] ``` This loop calculates `g(n)`, the real cost of the entire path so far. It walks through the list of cities two at a time (current city and the next city), and adds up the real road distance between each consecutive pair, using `dict_gn`. For `['Arad', 'Sibiu', 'Rimnicu']`, this adds `Arad to Sibiu` (140) plus `Sibiu to Rimnicu` (80), giving `gn = 220`. ```python hn = dict_hn[cities[-1]] return (gn + hn) ``` `cities[-1]` grabs the **last** city in the path, meaning the city we have currently reached. `dict_hn[cities[-1]]` looks up that city's straight line distance to Bucharest, this is `h(n)`. Finally the function returns `g(n) + h(n)`, the total f score for this path. #### The `main` function: running the actual search ```python def main(): global result cityq = q.PriorityQueue() ``` Creates an empty **priority queue**. Unlike the plain FIFO queue used in BFS, a priority queue does not serve items in the order they were added, it always serves whichever item has the **lowest priority value** first. Here, the priority is the f score, so the path with the smallest f score always comes out of the queue first, no matter when it was added. ```python cityq.put((get_fn(start), start, start)) ``` Adds the very first path into the queue: just the starting city on its own. Each entry in the queue is a tuple of 3 things: `(f_score, path_string_so_far, current_city)`. ```python while not cityq.empty(): f_score, current_path_str, current_city = cityq.get() ``` The main loop. `cityq.get()` always returns the path with the lowest f score currently waiting in the queue, and unpacks it into 3 variables. ```python if current_city == goal: result = current_path_str + "::" + str(f_score) break ``` Goal check. If the city we just pulled out of the queue is Bucharest, we are done, since the priority queue guarantees this is the best path found so far. We save the answer and immediately stop the loop. ```python for neighbor_city in dict_gn[current_city]: new_path_str = current_path_str + ',' + neighbor_city new_f_score = get_fn(new_path_str) cityq.put((new_f_score, new_path_str, neighbor_city)) ``` If we have not reached the goal yet, we look at every neighbour of the current city, build a brand new, longer path string that includes this neighbour, recalculate its full f score using `get_fn`, and add this new path back into the priority queue to be considered later. ```python print("the A* path with the total is: ") print(result) ``` Once the loop ends (goal found), print the winning path and its total f score. *** ### 6.5 Why a priority queue instead of a plain queue This is the single biggest difference between A\* and BFS/DFS. | Algorithm | Data structure | What decides which path is explored next | | --------- | ------------------------ | ------------------------------------------------------------ | | BFS | Plain queue (FIFO) | Whichever path was discovered first | | DFS | Stack / recursion (LIFO) | Whichever path was discovered most recently | | A\* | Priority queue | Whichever path currently has the lowest f score, g(n) + h(n) | Because the priority queue always pulls out the path with the smallest f score, A\* naturally focuses its effort on paths that look most promising, both in terms of distance already travelled and estimated distance remaining, instead of exploring in a fixed, blind order. *** ### 6.6 Step by step trace ```mermaid flowchart TD A["Arad\nf = 0 + 366 = 366"] --> Expand1[Expand Arad's neighbours] Expand1 --> Z["Arad,Zerind\nf = 75 + 374 = 449"] Expand1 --> S["Arad,Sibiu\nf = 140 + 253 = 393"] Expand1 --> T["Arad,Timisoara\nf = 118 + 329 = 447"] S -->|lowest f, expand next| Expand2[Expand Sibiu's neighbours] Expand2 --> SR["Arad,Sibiu,Rimnicu\nf = 220 + 193 = 413"] Expand2 --> SF["Arad,Sibiu,Fagaras\nf = 239 + 176 = 415"] SR -->|lowest f, expand next| Expand3[Expand Rimnicu's neighbours] Expand3 --> SRP["Arad,Sibiu,Rimnicu,Pitesti\nf = 317 + 100 = 417"] SRP -->|lowest f, expand next| Expand4[Expand Pitesti's neighbours] Expand4 --> Final["Arad,Sibiu,Rimnicu,Pitesti,Bucharest\nf = 418 + 0 = 418"] Final --> Goal[Bucharest reached, stop] ``` Notice that A\* never even seriously considers Zerind or Timisoara beyond their first expansion, their f scores are too high, so the priority queue keeps pushing paths through Sibiu to the front instead. This is the "smart" behaviour that uninformed search (BFS, DFS) does not have. | Step | Path being expanded | g(n) | h(n) | f(n) | | ---- | ---------------------------------------- | ---- | ---- | ---- | | 1 | Arad | 0 | 366 | 366 | | 2 | Arad, Sibiu | 140 | 253 | 393 | | 3 | Arad, Sibiu, Rimnicu | 220 | 193 | 413 | | 4 | Arad, Sibiu, Rimnicu, Pitesti | 317 | 100 | 417 | | 5 | Arad, Sibiu, Rimnicu, Pitesti, Bucharest | 418 | 0 | 418 | *** ### 6.7 Output (verified by running this exact code) ``` the A* path with the total is: Arad,Sibiu,Rimnicu,Pitesti,Bucharest::418 ``` The path found is **Arad, Sibiu, Rimnicu, Pitesti, Bucharest**, with a total real cost of **418** (140 + 80 + 97 + 101). This is the true shortest path in terms of real road distance, and A\* was able to find it efficiently by always trusting the lowest f score, without ever exploring the entire map the way BFS did in Practical 1. *** ### 6.8 Quick recap for viva * A\* combines `g(n)`, the real cost so far, with `h(n)`, a heuristic estimate of remaining distance, into a single score `f(n) = g(n) + h(n)`. * It always expands the path with the lowest f(n) next, using a priority queue instead of a plain queue or stack. * This makes A\* an example of **informed search**, unlike BFS and DFS which are uninformed. * A\* is guaranteed to find the optimal (cheapest) path, as long as the heuristic never overestimates the true remaining distance, a property called being **admissible**. Straight line distance is always admissible for road networks, since no road can ever be shorter than a straight line between two points. * If the heuristic `h(n)` was always 0 for every city, A\* would behave exactly like a different classic algorithm called **Uniform Cost Search**, since f(n) would just become g(n). --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://alham-rizvi.gitbook.io/alhamrizvi/ai-college-notes/practical-2-b-a-search-algorithm.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.