experiment1_A_star_Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a716be6a",
   "metadata": {},
   "source": [
    "**Heuristic Function**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c078b79f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def heuristic(n):\n",
    "    h_dist = {\n",
    "        'A':11, 'B':6, 'C':99, 'D':1, 'E':7, 'G':0\n",
    "    }\n",
    "    return h_dist[n]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62cf516e",
   "metadata": {},
   "source": [
    "**Graph Nodes**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "82c2ab1e",
   "metadata": {},
   "outputs": [],
   "source": [
    "Graph_nodes = {\n",
    "    'A': [('B', 2), ('E', 3)], \n",
    "    'B': [('C', 1), ('G', 9)],\n",
    "    'C': None, \n",
    "    'E': [('D', 6)], \n",
    "    'D': [('G', 1)]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cac1b8f4",
   "metadata": {},
   "source": [
    "**Get Neighbors**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "bc9358fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighbors(v):\n",
    "    if v in Graph_nodes:\n",
    "        return Graph_nodes[v]\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ef09ab0",
   "metadata": {},
   "source": [
    "**A Star Algorithm**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "fc97c1e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def aStarAlgo(start_node, stop_node):\n",
    "    open_set = set(start_node)\n",
    "    closed_set = set()\n",
    "    g = {}\n",
    "    parents = {}\n",
    "    \n",
    "    g[start_node] = 0\n",
    "    \n",
    "    parents[start_node] = start_node\n",
    "    \n",
    "    while len(open_set) > 0:\n",
    "        n = None\n",
    "        \n",
    "        for v in open_set:\n",
    "            if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):\n",
    "                n = v\n",
    "            \n",
    "        if n == stop_node or Graph_nodes[n] == None:\n",
    "            pass\n",
    "            \n",
    "        else:\n",
    "            for (m, weight) in get_neighbors(n):\n",
    "                if m not in open_set and m not in closed_set:\n",
    "                    open_set.add(m)\n",
    "                    parents[m] = n\n",
    "                    g[m] = g[n] + weight\n",
    "                else: \n",
    "                    if g[m] > g[n] + weight:\n",
    "                        g[m] = g[n] + weight\n",
    "\n",
    "                        parents[m] = n\n",
    "\n",
    "                        if m in closed_set:\n",
    "                            closed_set.remove(m)\n",
    "                            open_set.add(m)\n",
    "\n",
    "        if n == None:\n",
    "            print('Path does not Exists!')\n",
    "            return None\n",
    "\n",
    "        if n == stop_node:\n",
    "            path = []\n",
    "\n",
    "            while parents[n] != n:\n",
    "                path.append(n)\n",
    "                n = parents[n]\n",
    "\n",
    "            path.append(start_node)\n",
    "            path.reverse()\n",
    "\n",
    "            print('Path Found: {}'.format(path))\n",
    "            return path\n",
    "\n",
    "        open_set.remove(n)\n",
    "        closed_set.add(n)\n",
    "            \n",
    "    print('Path does not Exists!')\n",
    "    return None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a617c00e",
   "metadata": {},
   "source": [
    "**A Star Algo Function Call**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "14b1a03e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path Found: ['A', 'E', 'D', 'G']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['A', 'E', 'D', 'G']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aStarAlgo('A', 'G')"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "535e7dfa4e79b8a16ee5958c03c29abfca9eab7a4cbaa00a7baba8beca86875c"
  },
  "kernelspec": {
   "display_name": "Python 3.10.0 64-bit",
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}