Lab01_BFS.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "93d549dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum cost path from A to G is ['A', 'C', 'F', 'G']\n",
      "Cost: 44\n"
     ]
    }
   ],
   "source": [
    "def best_first_search(graph, start, goal, heuristic):\n",
    "    open_list = [(0, start)]\n",
    "    closed_list = set()\n",
    "    path = []\n",
    "\n",
    "    while open_list:\n",
    "        open_list.sort(key=lambda x: heuristic[x[1]])\n",
    "        cost, node = open_list.pop(0)\n",
    "        path.append(node)\n",
    "\n",
    "        if node == goal:\n",
    "            return cost, path\n",
    "\n",
    "        closed_list.add(node)\n",
    "\n",
    "        for neighbour, neighbour_cost in graph[node]:\n",
    "            if neighbour not in closed_list:\n",
    "                open_list.append((cost + neighbour_cost, neighbour))\n",
    "                closed_list.add(neighbour)\n",
    "\n",
    "    return None\n",
    "\n",
    "# Define the graph\n",
    "graph = {\n",
    "    'A': [('B', 11), ('C', 14), ('D', 7)],\n",
    "    'B': [('A', 11), ('E', 15)],\n",
    "    'C': [('A', 14), ('E', 8), ('D', 18), ('F', 10)],\n",
    "    'D': [('A', 7), ('F', 25), ('C', 18)],\n",
    "    'E': [('B', 15), ('C', 8), ('H', 9)],\n",
    "    'F': [('G', 20), ('C', 10), ('D', 25)],\n",
    "    'G': [],\n",
    "    'H': [('E', 9), ('G', 10)]\n",
    "}\n",
    "\n",
    "# Define the start and goal\n",
    "start = 'A'\n",
    "goal = 'G'\n",
    "\n",
    "# Define the heuristic values\n",
    "heuristic = {\n",
    "    'A': 40,\n",
    "    'B': 32,\n",
    "    'C': 25,\n",
    "    'D': 35,\n",
    "    'E': 19,\n",
    "    'F': 17,\n",
    "    'G': 0,\n",
    "    'H': 10\n",
    "}\n",
    "\n",
    "# Run the best-first search\n",
    "result = best_first_search(graph, start, goal, heuristic)\n",
    "\n",
    "# Print the results\n",
    "if result:\n",
    "    print(f\"Minimum cost path from {start} to {goal} is {result[1]}\")\n",
    "    print(f\"Cost: {result[0]}\")\n",
    "else:\n",
    "    print(f\"No path from {start} to {goal}\")\n"
   ]
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}