fai_project_AI_09.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/DayaAlex/FAI_CourseProject/blob/main/fai_project_AI_09.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3490a750",
        "outputId": "85e54231-17c4-4f2d-c405-4d8cb62a6e5d"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{'arad': {'zerind': 75, 'timisoara': 118, 'sibiu': 140}, 'zerind': {'oradea': 71, 'arad': 75}, 'timisoara': {'Lugoj': 111, 'arad': 118}, 'sibiu': {'fagaras': 99, 'oradea': 151, 'arad': 140, 'rimnicuvilcea': 80}, 'oradea': {'zerind': 71, 'sibiu': 151}, 'fagaras': {'sibiu': 99, 'bucharest': 211}, 'bucharest': {'fagaras': 211, 'pitesti': 101, 'urziceni': 85, 'giurgiu': 90}, 'pitesti': {'rimnicuvilcea': 97, 'bucharest': 101, 'craiova': 138}, 'urziceni': {'bucharest': 85, 'hirsova': 98, 'vaslui': 142}, 'giurgiu': {'bucharest': 90}, 'rimnicuvilcea': {'sibiu': 80, 'pitesti': 97, 'craiova': 146}, 'craiova': {'rimnicuvilcea': 146, 'pitesti': 138, 'drobeta': 120}, 'hirsova': {'eforie': 86, 'urziceni': 98}, 'vaslui': {'urziceni': 142, 'iasi': 92}, 'drobeta': {'mehadia': 75, 'craiova': 120}, 'eforie': {'hirsova': 86}, 'iasi': {'vaslui': 92, 'neamt': 87}, 'mehadia': {'Lugoj': 70, 'drobeta': 75}, 'neamt': {'iasi': 87}, 'Lugoj': {'timisoara': 111, 'mehadia': 70}}\n",
            "140\n"
          ]
        }
      ],
      "source": [
        "\n",
        "#create graph\n",
        "def create_graph():\n",
        "#creating graph as a dictionary of dictionaries\n",
        "\tgraph={'arad':{'zerind':75,'timisoara':118,'sibiu':140},\n",
        "\t\t   'zerind':{'oradea':71,'arad':75},\n",
        "\t\t   'timisoara':{'Lugoj':111,'arad':118},\n",
        "\t\t   'sibiu':{'fagaras':99, 'oradea':151,'arad':140,'rimnicuvilcea':80},\n",
        "\t\t   'oradea':{'zerind':71,'sibiu':151},\n",
        "\t\t   'fagaras':{'sibiu':99,'bucharest':211},\n",
        "\t\t   'bucharest':{'fagaras':211,'pitesti':101,'urziceni':85,'giurgiu':90},\n",
        "\t\t   'pitesti':{'rimnicuvilcea':97,'bucharest':101,'craiova':138},\n",
        "\t\t   'urziceni':{'bucharest':85,'hirsova':98,'vaslui':142},\n",
        "\t\t   'giurgiu':{'bucharest':90},\n",
        "\t\t   'rimnicuvilcea':{'sibiu':80,'pitesti':97,'craiova':146},\n",
        "\t\t   'craiova':{'rimnicuvilcea':146,'pitesti':138,'drobeta':120},\n",
        "\t\t   'hirsova':{'eforie':86,'urziceni':98},\n",
        "\t\t   'vaslui':{'urziceni':142,'iasi':92},\n",
        "\t\t   'drobeta':{'mehadia':75,'craiova':120},\n",
        "\t\t   'eforie':{'hirsova':86},\n",
        "\t\t   'iasi':{'vaslui':92,'neamt':87},\n",
        "\t\t   'mehadia':{'Lugoj':70,'drobeta':75},\n",
        "\t\t   'neamt':{'iasi':87},\n",
        "\t\t   'Lugoj':{'timisoara':111,'mehadia':70},\n",
        "\t}\n",
        "\treturn graph\n",
        "hn = {      'arad': 55,\n",
        "            'zerind': 62,\n",
        "             'oradea': 136,\n",
        "             'timisoara': 108,\n",
        "             'Lugoj': 60,\n",
        "             'mehadia': 68,\n",
        "             'drobeta': 110,\n",
        "             'craiova': 125,\n",
        "             'sibiu': 76,\n",
        "             'rimnicu':  88,\n",
        "             'pitesti': 95,\n",
        "             'fagaras': 187,\n",
        "             'bucharest': 0,\n",
        "             'giurgiu': 83,\n",
        "             'urziceni': 80,\n",
        "             'vaslui': 83,\n",
        "             'iasi': 77,\n",
        "             'neamt': 83,\n",
        "             'rimnicuvilcea':50,\n",
        "             'hirsova': 78,\n",
        "             'eforie': 70}\n",
        "\n",
        "def get_weight(graph, node1, node2):\n",
        "    if node2 in graph[node1].keys():\n",
        "        return graph[node1][node2]\n",
        "    else:\n",
        "        return None\n",
        "\n",
        "def get_cost(graph,path):\n",
        "    cost=0\n",
        "    for i in range(len(path)-1):\n",
        "        cost+=get_weight(graph, path[i], path[i+1])\n",
        "    return cost\n",
        "\n",
        "graph = create_graph()\n",
        "print(graph)\n",
        "print(get_weight(graph,'arad','sibiu'))\n"
      ],
      "id": "3490a750"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "78a0fb74",
        "outputId": "5209307b-bccd-423c-e78f-a453148b4760",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "532\n",
            "['zerind', 'oradea', 'sibiu', 'fagaras', 'bucharest']\n"
          ]
        }
      ],
      "source": [
        "from collections import deque\n",
        "def breadth_first_search(graph,start,goal):\n",
        "\tqueue=deque([(start,[start])])#create a deque named queue with node and the path to the node as elements, list of tupple.\n",
        "\twhile queue:\n",
        "\t\t(vertex,path)=queue.popleft()\n",
        "\t\tfor neighbour in graph[vertex].keys():\n",
        "\t\t\tif neighbour==goal:\n",
        "\t\t\t\treturn path+[neighbour]#appends the path to include neighbour's name\n",
        "\t\t\telse:\n",
        "\t\t\t\tqueue.append((neighbour,path+[neighbour]))#appends the neighbour and updated path to neighbour\n",
        "\treturn None\n",
        "\n",
        "path=breadth_first_search(graph,\"zerind\",\"bucharest\")\n",
        "print(get_cost(graph,path))\n",
        "print(path)"
      ],
      "id": "78a0fb74"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "73c0189a",
        "outputId": "6070c4ac-504d-4ac7-9645-67f84edef85d",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            " DFS path from zerind to bucharest is ['zerind', 'oradea', 'sibiu', 'fagaras', 'bucharest']\n",
            "DFS path cost is 532\n"
          ]
        }
      ],
      "source": [
        "#define a function to calculate path based on depth first search algorithm, using recursive fuction calling to perform as stack\n",
        "def Depth_first_search(graph, start, goal, path=[]):\n",
        "\tpath= path + [start]\n",
        "\tif start == goal:\n",
        "\t\treturn path\n",
        "\tif start not in graph:\n",
        "\t\treturn None\n",
        "\t#iterate over all adjacent nodes of start\n",
        "\tfor neighbour in graph[start].keys():\n",
        "\t\t#check if the node has been visited before\n",
        "\t\tif neighbour not in path:\n",
        "\t\t\t#assign the path retrieved from dfs on the neighbour to new_path\n",
        "\t\t\t#dfs called such that updated neighbour is assigned to its argument start, and path to neighbour assigned to path\n",
        "\t\t\tnew_path=Depth_first_search(graph,neighbour,goal,path)\n",
        "\t\t\t#pass the updated new_path to base dfs\n",
        "\t\t\tif new_path:\n",
        "\t\t\t\treturn new_path\n",
        "\t#if no goal state reached return none, meaning goal is in a disjoint graph\n",
        "\treturn None\n",
        "\n",
        "print(\"\\n DFS path from zerind to bucharest is {}\".format(Depth_first_search(graph,\"zerind\",\"bucharest\")))\n",
        "print('DFS path cost is {}'.format(get_cost(graph,Depth_first_search(graph,\"zerind\",\"bucharest\"))))"
      ],
      "id": "73c0189a"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "fa65944c",
        "outputId": "e9761429-4a44-405a-86a9-9a2689c963ad",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['zerind', 'arad', 'sibiu', 'rimnicuvilcea', 'pitesti', 'bucharest']\n",
            "493\n"
          ]
        }
      ],
      "source": [
        "import heapq\n",
        "#uniform cost search is like breadth first search but next level exploration is done through the node with least path cost\n",
        "def uniform_cost_search(graph,start,goal):\n",
        "\t#create a list 'queue' containing: path cost to node, node, and path of node\n",
        "\tqueue=[(0,start,[])]\n",
        "\t#create an array 'visited' to store visited nodes without repetition\n",
        "\tvisited=set()\n",
        "\n",
        "\twhile(queue):\n",
        "\t\t#initialising node to explore by selecting minimum value in queue using heappop\n",
        "\t\t(node_cost,node,node_path)=heapq.heappop(queue)\n",
        "\t\t#check membership of node in visited set and continue to next iteration of while if visited before otherwise add the node to visited set and update path\n",
        "\t\tif node in visited:\n",
        "\t\t\tcontinue\n",
        "\t\tvisited.add(node)\n",
        "\t\tnode_path=node_path+[node]\n",
        "\t\t#if goal state reached then update path and cost and return them\n",
        "\t\tif node==goal:\n",
        "\t\t\treturn node_path,node_cost\n",
        "\t\t#append the queue with the neighbours of node using heappush\n",
        "\t\tfor neighbour_node,neighbour_node_path_cost in graph[node].items():\n",
        "\t\t\theapq.heappush(queue,(neighbour_node_path_cost + node_cost,neighbour_node,node_path))\n",
        "\treturn None\n",
        "\n",
        "path,cost=uniform_cost_search(graph,'zerind','bucharest')\n",
        "print(path)\n",
        "print(cost)"
      ],
      "id": "fa65944c"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "1ce4d92a",
        "outputId": "aba169c3-4743-4d6f-e9cc-bb479a5eb528",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['zerind', 'arad', 'sibiu', 'fagaras', 'bucharest'] 525\n"
          ]
        }
      ],
      "source": [
        "def iddfs(graph, start, goal, max_depth):\n",
        "    stack = [(start, [])]\n",
        "    while stack:\n",
        "        (node, path) = stack.pop()\n",
        "        if node in path:\n",
        "            continue\n",
        "        path = path + [node]\n",
        "        if node == goal:\n",
        "            return path\n",
        "        if len(path) <= max_depth:\n",
        "            for neighbor in graph[node].keys():\n",
        "                stack.append((neighbor, path))\n",
        "    return None\n",
        "\n",
        "def iterative_deepening_dfs(graph, start, goal):\n",
        "    for depth in range(0, 100):\n",
        "        path = iddfs(graph, start, goal, depth)\n",
        "        if path is not None:\n",
        "            return path\n",
        "    return None\n",
        "\n",
        "path = iterative_deepening_dfs(graph, \"zerind\", \"bucharest\")\n",
        "cost=get_cost(graph,path)\n",
        "print(path,cost)"
      ],
      "id": "1ce4d92a"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "cdf48df7",
        "outputId": "e2f882d7-d84a-460b-ed31-6a8dd2ee3328",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['zerind', 'oradea', 'sibiu', 'fagaras', 'bucharest'] 532\n"
          ]
        }
      ],
      "source": [
        "def dls(graph, node, goal, limit):\n",
        "    if node == goal:\n",
        "        return [node]\n",
        "    if limit == 0:\n",
        "        return None\n",
        "    for neighbor in graph[node].keys():\n",
        "        path = dls(graph, neighbor, goal, limit-1)\n",
        "        if path is not None:\n",
        "            return [node] + path\n",
        "    return None\n",
        "path=dls(graph, \"zerind\", \"bucharest\", 4)\n",
        "cost=get_cost(graph,path)\n",
        "\n",
        "print(path,cost)"
      ],
      "id": "cdf48df7"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3b2e37b1",
        "outputId": "d87fd5d0-527d-43ea-d556-6162544e70e7"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['zerind', 'arad', 'sibiu', 'rimnicuvilcea', 'pitesti', 'bucharest'] 493\n"
          ]
        }
      ],
      "source": [
        "#best first search\n",
        "from queue import PriorityQueue\n",
        "\n",
        "def bestfirst(graph, start, end):\n",
        "    queue = PriorityQueue()\n",
        "    heuristic_cost=hn[start]\n",
        "    queue.put((heuristic_cost, [start], start))\n",
        "    visited = []\n",
        "    qq = 30\n",
        "\n",
        "    while not queue.empty() and qq:\n",
        "        qq -=1\n",
        "\n",
        "        (priority, path, node) = queue.get()\n",
        "\n",
        "        if node not in visited :\n",
        "          visited.append(node)\n",
        "\n",
        "        if node == end:\n",
        "            return path\n",
        "        for next_node,cost in graph[node].items():\n",
        "          \n",
        "            if next_node not in visited:\n",
        "              heuristic_cost =hn[next_node]\n",
        "              queue.put((heuristic_cost, path + [next_node], next_node))          \n",
        "            \n",
        "    return None\n",
        "\n",
        "\n",
        "path = bestfirst(graph,\"zerind\", \"bucharest\")\n",
        "cost=get_cost(graph,path)\n",
        "print(path,cost)"
      ],
      "id": "3b2e37b1"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "05aaf0b5",
        "outputId": "dff57299-18f5-4a44-c75a-1ec68dc0deed",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(['zerind', 'arad', 'sibiu', 'rimnicuvilcea', 'pitesti', 'bucharest'], 831)\n"
          ]
        }
      ],
      "source": [
        "from queue import PriorityQueue\n",
        "import math\n",
        "\n",
        "def astar(graph, start, goal):\n",
        "    queue = PriorityQueue()\n",
        "    queue.put((0, [start], start))\n",
        "    while queue:\n",
        "        (priority, path, node) = queue.get()\n",
        "        if node == goal:\n",
        "            return path, priority\n",
        "        for next_node, cost in graph[node].items():\n",
        "            heuristic_cost = hn[node]\n",
        "            queue.put((priority + cost + heuristic_cost, path + [next_node], next_node))       \n",
        "            \n",
        "    return None\n",
        "\n",
        "path = astar(graph, \"zerind\", \"bucharest\")\n",
        "\n",
        "print(path)"
      ],
      "id": "05aaf0b5"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6c6fe6c3"
      },
      "outputs": [],
      "source": [],
      "id": "6c6fe6c3"
    }
  ],
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "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
}