uniform_cost_search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2f30dcff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum cost from 0 to 7 is 10\n",
      "Path: 0 -> 4 -> 5 -> 18 -> 6 -> 7\n"
     ]
    }
   ],
   "source": [
    "# uniform cost function\n",
    "from queue import PriorityQueue\n",
    "# returns the minimum cost (Bonus: returns path to minimum cost as well)\n",
    "def  uniform_cost_search(start, goal, graph, cost):\n",
    "    answer = {node: {'cost': float('inf'), 'path': []} for node in goal}\n",
    "#     **************************************\n",
    "#     ******** Write your code here ********\n",
    "#     **************************************\n",
    "    frontier = PriorityQueue()\n",
    "    frontier.put((0, start, [start]))\n",
    "\n",
    "    while not frontier.empty():\n",
    "        current_cost, current_node, path = frontier.get()\n",
    "\n",
    "        if current_node in goal:\n",
    "            if current_cost < answer[current_node]['cost']:\n",
    "                answer[current_node] = {'cost' : current_cost, 'path': path}\n",
    "            continue\n",
    "\n",
    "        for neighbor in graph[current_node]:\n",
    "            edge_cost = cost.get((current_node, neighbor), float('inf'))\n",
    "            if edge_cost != float('inf'):\n",
    "                total_cost = current_cost + edge_cost\n",
    "                new_path = path + [neighbor]\n",
    "                frontier.put((total_cost, neighbor, new_path))\n",
    "\n",
    "    return answer\n",
    " \n",
    "# main function\n",
    "if __name__ == '__main__':\n",
    "     \n",
    "    # create a graph with no more than 30 nodes\n",
    "    graph, cost = [[] for i in range(30)], {}\n",
    " \n",
    "    # add edges to the graph\n",
    "    graph[0].append(4)\n",
    "    graph[0].append(5)\n",
    "    graph[0].append(16)\n",
    "    graph[2].append(1)\n",
    "    graph[3].append(1)\n",
    "    graph[4].append(2)\n",
    "    graph[4].append(3)\n",
    "    graph[4].append(5)\n",
    "    graph[5].append(8)\n",
    "    graph[5].append(18)\n",
    "    graph[6].append(3)\n",
    "    graph[6].append(7)\n",
    "    graph[8].append(16)\n",
    "    graph[8].append(17)\n",
    "    graph[16].append(17)\n",
    "    graph[18].append(6)\n",
    "    \n",
    " \n",
    "    # add cost to each edge\n",
    "    cost[(0, 4)] = 3\n",
    "    cost[(0, 5)] = 9\n",
    "    cost[(0, 16)] = 1\n",
    "    cost[(2, 1)] = 2\n",
    "    cost[(3, 1)] = 2\n",
    "    cost[(4, 2)] = 1\n",
    "    cost[(4, 3)] = 8\n",
    "    cost[(4, 5)] = 2\n",
    "    cost[(5, 8)] = 3\n",
    "    cost[(5, 18)] = 2\n",
    "    cost[(6, 3)] = 3\n",
    "    cost[(6, 7)] = 2\n",
    "    cost[(8, 16)] = 4\n",
    "    cost[(8, 17)] = 4\n",
    "    cost[(16, 17)] = 15\n",
    "    cost[(18, 6)] = 1\n",
    "    \n",
    "    # set start state \n",
    "    start = 0\n",
    "    \n",
    "    # set goal state, there can be multiple goal states\n",
    "    goal = [7]\n",
    "    \n",
    "    # call uniform_search_cost function to get the minimum cost to reach goal. Bonus points for path\n",
    "    # ****** You have to implement this function *****\n",
    "    min_cost_info = uniform_cost_search(start, goal, graph, cost)\n",
    "\n",
    "    for node, info in min_cost_info.items():\n",
    "        print(f'Minimum cost from {start} to {node} is {info[\"cost\"]}')\n",
    "        if info[\"path\"]:\n",
    "                print(f'Path: {\" -> \".join(map(str, info[\"path\"]))}')\n",
    "      \n",
    "    #   **** Bonus ****\n",
    "    #   print(f'Path: {info[\"path\"]}')"
   ]
  }
 ],
 "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}