A Star Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d91e9983",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A-star Agorithm for Romania Map\n",
      "\t\tA => G\n",
      "=======================================================\n",
      "List of Cities that are Expanded : ['A', 'E', 'D', 'G']\n",
      "Total Number of Cities that are Expanded : 4\n",
      "=======================================================\n",
      "Cities in Final path : ['A', 'E', 'D', 'G']\n",
      "Total Number of cities in final path are : 4\n",
      "Total Cost : 10\n"
     ]
    }
   ],
   "source": [
    "#Name: Sachin Bhaskar Patil\n",
    "#class: TY DS\n",
    "#Roll No: 43\n",
    "#PRN: 201106045\n",
    "#Experiment 5: Implement A* search algorithm to reach goal state.\n",
    "Graph_nodes = [\n",
    "    [\"A\",\"B\", 6],\n",
    "    [\"A\",\"E\",3],\n",
    "    [\"B\",\"C\",1],\n",
    "    [\"B\",\"G\",9],\n",
    "    [\"E\",\"D\",6],\n",
    "    [\"D\",\"G\",1]\n",
    "]\n",
    "l2=[[\"A\",2],[\"B\",6],[\"C\",99],[\"G\",0],[\"E\",7],[\"D\",1]]\n",
    "import heapq\n",
    "\t\n",
    "\n",
    "class priorityQueue:\n",
    "    def __init__(self):\n",
    "        self.cities = []\n",
    "    def push(self, city, cost):\n",
    "        heapq.heappush(self.cities, (cost, city))\n",
    "    def pop(self):\n",
    "        return heapq.heappop(self.cities)[1]\n",
    "    def isEmpty(self):\n",
    "        if (self.cities == []):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def check(self):\n",
    "        print(self.cities)\n",
    "\n",
    "class ctNode:\n",
    "    def __init__(self, city, distance):\n",
    "        self.city = str(city)\n",
    "        self.distance = str(distance)\n",
    "\n",
    "romania = {}\n",
    "\n",
    "def makedict():\n",
    "    for i in range(len(Graph_nodes)):\n",
    "        ct1 = Graph_nodes[i][0]\n",
    "        ct2 = Graph_nodes[i][1]\n",
    "        dist = int(Graph_nodes[i][2])\n",
    "        romania.setdefault(ct1, []).append(ctNode(ct2, dist))\n",
    "        romania.setdefault(ct2, []).append(ctNode(ct1, dist))\n",
    "        \n",
    "        \n",
    "def makehuristikdict():\n",
    "    H_dist = {\n",
    "            'A':2,\n",
    "            'B':6,\n",
    "            'C':99,\n",
    "            'G':0,\n",
    "            'E':7,\n",
    "            'D':1,\n",
    "        }\n",
    "    return H_dist\n",
    "\n",
    "def heuristic(node, values):\n",
    "    return values[node]\n",
    "\n",
    "def astar(start, end):\n",
    "    path = {}\n",
    "    distance = {}\n",
    "    q = priorityQueue()\n",
    "    h = makehuristikdict()\n",
    "    q.push(start, 0)\n",
    "    distance[start] = 0\n",
    "    path[start] = None\n",
    "    expandedList = []\n",
    "    while (q.isEmpty() == False):\n",
    "        current = q.pop()\n",
    "        expandedList.append(current)\n",
    "        if (current == end):\n",
    "            break\n",
    "        for new in romania[current]:\n",
    "            \n",
    "            g_cost = distance[current] + int(new.distance)\n",
    "            #print(new.city, new.distance, \"now : \" + str(distance[current]), g_cost)\n",
    "            if (new.city not in distance or g_cost < distance[new.city]):\n",
    "                distance[new.city] = g_cost\n",
    "                f_cost = g_cost + heuristic(new.city, h)\n",
    "                #print(f_cost)\n",
    "                q.push(new.city, f_cost)\n",
    "                path[new.city] = current\n",
    "    printoutput(start, end, path, distance, expandedList)\n",
    "\n",
    "def printoutput(start, end, path, distance, expandedlist):\n",
    "    finalpath = []\n",
    "    i = end\n",
    "    while (path.get(i) != None):\n",
    "        finalpath.append(i)\n",
    "        i = path[i]\n",
    "    finalpath.append(start)\n",
    "    finalpath.reverse()\n",
    "    print(\"A-star Agorithm for Romania Map\")\n",
    "    print(\"\\t\\tA => G\")\n",
    "    print(\"=======================================================\")\n",
    "    print(\"List of Cities that are Expanded : \" + str(expandedlist))\n",
    "    print(\"Total Number of Cities that are Expanded : \" + str(len(expandedlist)))\n",
    "    print(\"=======================================================\")\n",
    "    print(\"Cities in Final path : \" + str(finalpath))\n",
    "    print(\"Total Number of cities in final path are : \" + str(len(finalpath)))\n",
    "    print(\"Total Cost : \" + str(distance[end]))\n",
    "    \n",
    "\n",
    "def main():\n",
    "    src = \"A\"\n",
    "    dst = \"G\"\n",
    "    makedict()\n",
    "    astar(src, dst)\n",
    "\n",
    "if __name__ == \"__main__\" :\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e0ff0a3",
   "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.10.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}