{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0d3dfd5d-5800-4ac2-880b-7c95ce2a8b78",
   "metadata": {
    "tags": []
   },
   "source": [
    "# A possible A* Search implementation for the finding-route problem on the Romanias' map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32886fc4-b774-48b2-871a-da38c375c1fb",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Precomputed distance matrix of Romania cities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4af56206-7c8b-4249-8cbb-c1930b14265f",
   "metadata": {},
   "outputs": [],
   "source": [
    "romania_dist = {\n",
    "    'Arad': {'Zerind': 75, 'Timisoara': 118, 'Sibiu': 140},\n",
    "    'Bucharest': {'Urziceni': 85, 'Pitesti': 101, 'Giurgiu': 90, 'Fagaras': 211},\n",
    "    'Craiova': {'Drobeta': 120, 'Rimnicu Vilcea': 146, 'Pitesti': 138},\n",
    "    'Drobeta': {'Mehadia': 75, 'Craiova': 120},\n",
    "    'Eforie': {'Hirsova': 86},\n",
    "    'Fagaras': {'Sibiu': 99, 'Bucharest': 211},\n",
    "    'Giurgiu': {'Bucharest': 90},\n",
    "    'Hirsova': {'Urziceni': 98, 'Eforie': 86},\n",
    "    'Iasi': {'Neamt': 87, 'Vaslui': 92},\n",
    "    'Lugoj': {'Timisoara': 111, 'Mehadia': 70},\n",
    "    'Mehadia': {'Drobeta': 75, 'Lugoj': 70},\n",
    "    'Neamt': {'Iasi': 87},\n",
    "    'Oradea': {'Zerind': 71, 'Sibiu': 151},\n",
    "    'Pitesti': {'Rimnicu Vilcea': 97, 'Bucharest': 101, 'Craiova': 138},\n",
    "    'Rimnicu Vilcea': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},\n",
    "    'Sibiu': {'Oradea': 151, 'Arad': 140, 'Fagaras': 99, 'Rimnicu Vilcea': 80},\n",
    "    'Timisoara': {'Arad': 118, 'Lugoj': 111},\n",
    "    'Urziceni': {'Vaslui': 142, 'Bucharest': 85, 'Hirsova': 98},\n",
    "    'Vaslui': {'Iasi': 92, 'Urziceni': 142},\n",
    "    'Zerind': {'Oradea': 71, 'Arad': 75}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0556cd5e-cf5d-4a06-a457-9a488aa889b9",
   "metadata": {},
   "source": [
    "# Heuristic distance from each city to Bucharest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "370c380c-5916-4429-9627-8b18b2d61ffb",
   "metadata": {},
   "outputs": [],
   "source": [
    "romania_h = {\n",
    "    'Arad': 366,\n",
    "    'Bucharest': 0,\n",
    "    'Craiova': 160,\n",
    "    'Drobeta': 242,\n",
    "    'Eforie': 161,\n",
    "    'Fagaras': 176,\n",
    "    'Giurgiu': 77,\n",
    "    'Hirsova': 151,\n",
    "    'Iasi': 226,\n",
    "    'Lugoj': 244,\n",
    "    'Mehadia': 241,\n",
    "    'Neamt': 234,\n",
    "    'Oradea': 380,\n",
    "    'Pitesti': 100,\n",
    "    'Rimnicu Vilcea': 193,\n",
    "    'Sibiu': 253,\n",
    "    'Timisoara': 329,\n",
    "    'Urziceni': 80,\n",
    "    'Vaslui': 199,\n",
    "    'Zerind': 374\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40ab14df-2143-4268-9e82-0597f5f8fc9b",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Here we use a heap for implementing the priority queue. It is available in the heapq module.\n",
    "\n",
    "# The function takes as input the start and goal nodes, the distance matrix graph, and the heuristic distance h from each node to the goal. It returns a list of nodes representing the optimal path from the start node to the goal node, or None if no path was found."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adedac71-b9a6-448a-ae98-badf663ecddc",
   "metadata": {
    "tags": []
   },
   "source": [
    "# The main loop of the A* search algorithm pops the node with the smallest f score from the heap and checks if it is the goal node. If so, it reconstructs the path from the start node to the goal node using the path dictionary and returns it. If not, it marks the current node as explored and iterates over its neighbors. \n",
    "\n",
    "# For each neighbor, it calculates the tentative g score and checks if the neighbor node has already been explored or is already in the frontier with a lower g score. If not, it adds the neighbor node to the frontier with its f score as the priority and updates the path and g_score dictionaries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f4a924b1-6061-4dc8-9d4f-4946ea3aeed3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "def a_star_search(start, goal, graph, h):\n",
    "    # Initialize the frontier with the start node and its f score\n",
    "    frontier = [(h[start], start)]\n",
    "    \n",
    "    # Initialize the explored set\n",
    "    explored = set()\n",
    "    \n",
    "    # Dictionary to keep track of the actual path\n",
    "    path = {start: None}\n",
    "    \n",
    "    # Dictionary to keep track of the cost of reaching each node\n",
    "    g_score = {start: 0}\n",
    "    \n",
    "    # Main loop of the A* search algorithm\n",
    "    while frontier:\n",
    "        # Pop the node with the smallest f score from the heap\n",
    "    \n",
    "        current = frontier[0][1]\n",
    "        frontier.remove(frontier[0])\n",
    "        \n",
    "        # Check if the current node is the goal\n",
    "        if current == goal:\n",
    "            # If so, reconstruct the path from the start node to the goal node\n",
    "            path_list = []\n",
    "            while current != start:\n",
    "                path_list.append(current)\n",
    "                current = path[current]\n",
    "            path_list.append(start)\n",
    "            path_list.reverse()\n",
    "            return path_list\n",
    "        \n",
    "        # Mark the current node as explored\n",
    "        explored.add(current)\n",
    "        \n",
    "        # Iterate over the neighbors of the current node\n",
    "        for neighbor in graph[current]:\n",
    "            distance = graph[current][neighbor]\n",
    "            \n",
    "            # Calculate the tentative g score for the neighbor node\n",
    "            tentative_g_score = g_score[current] + distance\n",
    "            \n",
    "            # Check if the neighbor node has already been explored\n",
    "            if neighbor in explored:\n",
    "                # Skip this neighbor node\n",
    "                continue\n",
    "            \n",
    "            # Calculate the f score for the neighbor node\n",
    "            f_score = tentative_g_score + h[neighbor]\n",
    "            \n",
    "            # Check if the neighbor node is already in the frontier\n",
    "            in_frontier = False\n",
    "            for i in range(len(frontier)):\n",
    "                if frontier[i][1] == neighbor:\n",
    "                    in_frontier = True\n",
    "                    frontier_node = frontier[i]\n",
    "                    break\n",
    "            \n",
    "            if in_frontier:\n",
    "                # Update the priority of the neighbor node in the frontier if it has a lower f score\n",
    "                if f_score < frontier_node[0]:\n",
    "                    frontier.remove(frontier_node)\n",
    "                    heapq.heappush(frontier, (f_score, neighbor))\n",
    "                    # Update the path and g score dictionaries for the neighbor node\n",
    "                    path[neighbor] = current\n",
    "                    g_score[neighbor] = tentative_g_score\n",
    "            else:\n",
    "                # Add the neighbor node to the frontier with its f score as the priority\n",
    "                heapq.heappush(frontier, (f_score, neighbor))\n",
    "                # Update the path and g score dictionaries for the neighbor node\n",
    "                path[neighbor] = current\n",
    "                g_score[neighbor] = tentative_g_score\n",
    "    \n",
    "    # If no path was found, return None\n",
    "    return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "da7bb930-5b57-4a29-aa47-9180b5bca7ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Arad', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest']\n"
     ]
    }
   ],
   "source": [
    "path = a_star_search('Arad', 'Bucharest', romania_dist, romania_h)\n",
    "print(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f64149fa-088e-4f74-9bf1-c8316f9eb448",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}