CA 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "73456fac",
   "metadata": {},
   "source": [
    "## پروژه اول درس هوش مصنوعی با موضوع الگوریتم های جستجوی آگاهانه و ناآگاهانه"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89406161",
   "metadata": {},
   "source": [
    "### در این پروژه سعی میکنیم با استفاده از الگوریتم های زیر مساله ی یافتن راهی برای جمع آوری معجون ها از معبدی با شکل شطرنجی را حل کنیم"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fec1c5f7",
   "metadata": {},
   "source": [
    "## BFS , IDS & A*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6fef698",
   "metadata": {},
   "source": [
    "# Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2bef7f63",
   "metadata": {},
   "outputs": [],
   "source": [
    "#import numpy as np\n",
    "import time\n",
    "from copy import deepcopy\n",
    "import queue as qu"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12509f30",
   "metadata": {},
   "source": [
    "# Body"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c7f3233",
   "metadata": {},
   "source": [
    "## Load tests data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8137c96e",
   "metadata": {},
   "outputs": [],
   "source": [
    "tests = []\n",
    "file = open(\"test1.in\")\n",
    "tests.append(file.readlines())\n",
    "file.close()\n",
    "file = open(\"test2.in\")\n",
    "tests.append(file.readlines())\n",
    "file.close()\n",
    "file = open(\"test3.in\")\n",
    "tests.append(file.readlines())\n",
    "file.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98cfb176",
   "metadata": {},
   "source": [
    "#### داده های تست ها را از فایل هایی که در پوشه پروژه قرار دارند برای تست برنامه لود می کنیم\n",
    "#### با توجه به تست های موجود فرض می شود که تعداد سطر ها و ستون ها اعداد تک رقمی می باشند "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e2a441",
   "metadata": {},
   "source": [
    "## Create tests maps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "65671ca9",
   "metadata": {},
   "outputs": [],
   "source": [
    "maps = []\n",
    "Cs = []\n",
    "Ks = []\n",
    "for test in tests:\n",
    "    num_of_row = int(test[0][0])\n",
    "    num_of_col = int(test[0][2])\n",
    "    curr_map = [['e'] * num_of_col for i in range(num_of_row)]\n",
    "    curr_c = int(test[1][0])\n",
    "    curr_k = int(test[1][2])\n",
    "    curr_Cs = []\n",
    "    curr_Ks = []\n",
    "    for i in range(0, curr_c):\n",
    "        curr_Cs.append([int(test[2+i][0]), int(test[2+i][2]), False])\n",
    "        curr_map[int(test[2+i][0])][int(test[2+i][2])] = 'c'\n",
    "    for i in range(0, curr_k):\n",
    "        curr_Ks.append([int(test[2+curr_c+i][0]), int(test[2+curr_c+i][2]), False])\n",
    "        curr_map[int(test[2+curr_c+i][0])][int(test[2+curr_c+i][2])] = 'k'\n",
    "    curr_d = int(test[2+curr_c+curr_k])\n",
    "    for i in range(0, curr_d):\n",
    "        curr_map[int(test[3+curr_c+curr_k+i][0])][int(test[3+curr_c+curr_k+i][2])] = 'd'\n",
    "    maps.append(curr_map)\n",
    "    Cs.append(curr_Cs)\n",
    "    Ks.append(curr_Ks)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cfe253e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[['e', 'k', 'c', 'e'],\n",
       "  ['e', 'e', 'd', 'e'],\n",
       "  ['c', 'e', 'e', 'e'],\n",
       "  ['e', 'e', 'e', 'e']],\n",
       " [['k', 'e', 'e', 'd'],\n",
       "  ['e', 'k', 'c', 'd'],\n",
       "  ['c', 'c', 'e', 'e'],\n",
       "  ['e', 'k', 'e', 'e']],\n",
       " [['e', 'e', 'd', 'e', 'e', 'e'],\n",
       "  ['e', 'd', 'c', 'e', 'e', 'c'],\n",
       "  ['e', 'e', 'k', 'e', 'e', 'e'],\n",
       "  ['d', 'e', 'e', 'e', 'e', 'c'],\n",
       "  ['e', 'd', 'k', 'c', 'e', 'e'],\n",
       "  ['e', 'c', 'e', 'e', 'e', 'e']]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maps"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "410807b6",
   "metadata": {},
   "source": [
    "#### مشاهده می شود که نقشه های تست به درستی  لود شده اند"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69134301",
   "metadata": {},
   "source": [
    "## Model Description"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de72a0a0",
   "metadata": {},
   "source": [
    "### Actions : Di up, Di down, Di right, Di left (for i in range num of doctors)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc16b71c",
   "metadata": {},
   "source": [
    "### Initial State : A doctor in (0, 0) and the map looks like the test files"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ea70874",
   "metadata": {},
   "source": [
    "### Goal State : Every doctor in (n-1, m-1) and no 'c' remain in the map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12f4234d",
   "metadata": {},
   "source": [
    "### Path cost : sum of moves (Actions) of all doctors (from Initial state to Goal state)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c029aab",
   "metadata": {},
   "source": [
    "### State : position of elements in the map in a node represents the current state for this node"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44c7d6c4",
   "metadata": {},
   "source": [
    "### Transition Model : اگر دکتری به خانه ای که دارای دارو است وارد شود آن خانه تبدیل به خانه ی خالی شده و یک دکتر در خانه ی پایین سمت چپ جدول ایجاد می شود . اگر دکتری وارد خانه ای دارای معجون شود آن خانه به خانه ی خالی تبدیل می شود . برای حرکت دکتر ها هم تنها در صورتی که خانه ی مورد نظر مجاز باشد و قابل رفتن باشد به آنجا می رود"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7c4684d",
   "metadata": {},
   "source": [
    "## Common Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "c12f4f01",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_in_list(node, ls, bfs):\n",
    "    if bfs:\n",
    "        for nd in ls:\n",
    "            if nd.is_same_for_BFS(node):\n",
    "                return True\n",
    "        return False\n",
    "    else:\n",
    "        for nd in ls:\n",
    "            if nd.is_same_for_IDS(node):\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "def eat_drug(Ks, x, y):\n",
    "    for k in Ks:\n",
    "        if k[0] == x and k[1] == y:\n",
    "            if k[2]:\n",
    "                return False\n",
    "            else:\n",
    "                k[2] = True\n",
    "                return True\n",
    "            \n",
    "def pick_confection(Cs, x, y):\n",
    "    for c in Cs:\n",
    "        if c[0] == x and c[1] == y:\n",
    "            c[2] = True\n",
    "            return\n",
    "        \n",
    "def is_dr_in_list(dr, drs, m, n):\n",
    "    if dr[1] == m-1 and dr[2] == n-1:\n",
    "        return True\n",
    "    for d in drs:\n",
    "        if d[1] == dr[1] and d[2] == dr[2]:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def get_best(frontier, alfa = 1):\n",
    "    length = len(frontier)\n",
    "    if length == 0:\n",
    "        return None\n",
    "    elif length == 1:\n",
    "        return frontier.pop()\n",
    "    answer = frontier[0]\n",
    "    index = 0\n",
    "    for i in range(1, length):\n",
    "        if frontier[i].hur*alfa + frontier[i].path_cost < answer.hur*alfa + answer.path_cost:\n",
    "            answer = frontier[i]\n",
    "            index = i\n",
    "    return frontier.pop(index)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "273f0cd3",
   "metadata": {},
   "source": [
    "## Data Structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "6ff5e320",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Fifo:\n",
    "    def __init__(self):\n",
    "        self.ls = []\n",
    "        self.front = 0\n",
    "        self.rear = 0\n",
    "        \n",
    "    def put(self, element):\n",
    "        self.ls.append(element)\n",
    "        self.rear += 1\n",
    "        \n",
    "    def get(self):\n",
    "        self.front += 1\n",
    "        return self.ls[self.front-1]\n",
    "    \n",
    "    def empty(self):\n",
    "        return self.front >= self.rear\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "0e662b41",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Lifo:\n",
    "    def __init__(self):\n",
    "        self.ls = []\n",
    "        self.top = 0\n",
    "        \n",
    "    def put(self, element):\n",
    "        self.ls.append(element)\n",
    "        self.top += 1\n",
    "        \n",
    "    def get(self):\n",
    "        self.top -= 1\n",
    "        return self.ls.pop()\n",
    "    \n",
    "    def empty(self):\n",
    "        return self.top <= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "id": "34d39723",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, curr_map, curr_Cs, curr_Ks, path_until_there, path_cost_until_there, curr_Drs, row, col):\n",
    "        self.map = curr_map\n",
    "        self.Cs = curr_Cs\n",
    "        self.Ks = curr_Ks\n",
    "        self.path = path_until_there\n",
    "        self.path_cost = path_cost_until_there\n",
    "        self.Drs = curr_Drs\n",
    "        self.m = row\n",
    "        self.n = col\n",
    "        self.hur = self.h()\n",
    "        if self.path_cost == 0:\n",
    "            if self.map[0][0] == 'k':\n",
    "                eat_drug(self.Ks, 0, 0)\n",
    "                self.Drs.append([1, self.m-1, 0])\n",
    "    \n",
    "    def Goal_test(self):\n",
    "        for c in self.Cs:\n",
    "            if c[2] is False:\n",
    "                return False\n",
    "        for dr in self.Drs:\n",
    "            if dr[1] != self.m-1 or dr[2] != self.n-1:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    #Implementation with BFS\n",
    "    def expand(self, queue, expanded):\n",
    "        expanded.append(self)\n",
    "        for dr in self.Drs:\n",
    "            if dr[1] == self.m-1 and dr[2] == self.n-1:\n",
    "                continue\n",
    "            if dr[1]+1 < self.m:\n",
    "                if self.map[dr[1]+1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]+1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]+1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"D\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if temp_node.Goal_test():\n",
    "                            return temp_node\n",
    "                        if not is_in_list(temp_node, queue.ls, True):\n",
    "                            queue.put(temp_node)\n",
    "            if dr[1] > 0:\n",
    "                if self.map[dr[1]-1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]-1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]-1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"U\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if temp_node.Goal_test():\n",
    "                            return temp_node\n",
    "                        if not is_in_list(temp_node, queue.ls, True):\n",
    "                            queue.put(temp_node)\n",
    "            if dr[2]+1 < self.n:\n",
    "                if self.map[dr[1]][dr[2]+1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]+1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]+1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"R\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if temp_node.Goal_test():\n",
    "                            return temp_node\n",
    "                        if not is_in_list(temp_node, queue.ls, True):\n",
    "                            queue.put(temp_node)\n",
    "            if dr[2] > 0:\n",
    "                if self.map[dr[1]][dr[2]-1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]-1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]-1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"L\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if temp_node.Goal_test():\n",
    "                            return temp_node\n",
    "                        if not is_in_list(temp_node, queue.ls, True):\n",
    "                            queue.put(temp_node)\n",
    "            break  \n",
    "        return None\n",
    "    \n",
    "    #Implementation with IDS\n",
    "    def RDLS(self, expanded, limit):\n",
    "        if self.Goal_test():\n",
    "            return self\n",
    "        if limit == 0:\n",
    "            return None\n",
    "        expanded.append(self)\n",
    "        for dr in self.Drs:\n",
    "            if dr[1] == self.m-1 and dr[2] == self.n-1:\n",
    "                continue\n",
    "            if dr[1]+1 < self.m:\n",
    "                if self.map[dr[1]+1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]+1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]+1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"D\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, False):\n",
    "                        result = temp_node.RDLS(expanded, limit-1)\n",
    "                        if result != None:\n",
    "                            return result\n",
    "            if dr[1] > 0:\n",
    "                if self.map[dr[1]-1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]-1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]-1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"U\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, False):\n",
    "                        result = temp_node.RDLS(expanded, limit-1)\n",
    "                        if result != None:\n",
    "                            return result\n",
    "            if dr[2]+1 < self.n:\n",
    "                if self.map[dr[1]][dr[2]+1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]+1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]+1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"R\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, False):\n",
    "                        result = temp_node.RDLS(expanded, limit-1)\n",
    "                        if result != None:\n",
    "                            return result\n",
    "            if dr[2] > 0:\n",
    "                if self.map[dr[1]][dr[2]-1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]-1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]-1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"L\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, False):\n",
    "                        result = temp_node.RDLS(expanded, limit-1)\n",
    "                        if result != None:\n",
    "                            return result\n",
    "            break\n",
    "        return None\n",
    "    \n",
    "    #Implementation with A* with consistent heuristic\n",
    "    def RBFS(self, frontier, expanded):\n",
    "        if self.Goal_test():\n",
    "            return self\n",
    "        expanded.append(self)\n",
    "        for dr in self.Drs:\n",
    "            if dr[1] == self.m-1 and dr[2] == self.n-1:\n",
    "                continue\n",
    "            if dr[1]+1 < self.m:\n",
    "                if self.map[dr[1]+1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]+1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]+1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]+1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"D\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if not is_in_list(temp_node, frontier, True):\n",
    "                            frontier.append(temp_node)\n",
    "            if dr[1] > 0:\n",
    "                if self.map[dr[1]-1][dr[2]] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][1] = dr[1]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1]-1, dr[2]):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]-1][dr[2]] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1]-1, dr[2])\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"U\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if not is_in_list(temp_node, frontier, True):\n",
    "                            frontier.append(temp_node)\n",
    "            if dr[2]+1 < self.n:\n",
    "                if self.map[dr[1]][dr[2]+1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]+1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]+1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]+1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]+1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"R\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if not is_in_list(temp_node, frontier, True):\n",
    "                            frontier.append(temp_node)\n",
    "            if dr[2] > 0:\n",
    "                if self.map[dr[1]][dr[2]-1] != 'd':\n",
    "                    temp_drs = deepcopy(self.Drs)\n",
    "                    temp_drs[dr[0]][2] = dr[2]-1\n",
    "                    temp_Ks = deepcopy(self.Ks)\n",
    "                    temp_Cs = deepcopy(self.Cs)\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'k':\n",
    "                        if eat_drug(temp_Ks, dr[1], dr[2]-1):\n",
    "                            temp_drs.append([len(self.Drs), self.m-1, 0])\n",
    "                    if self.map[dr[1]][dr[2]-1] == 'c':\n",
    "                        pick_confection(temp_Cs, dr[1], dr[2]-1)\n",
    "                    temp_path = deepcopy(self.path)\n",
    "                    temp_path.append([dr[0], \"L\"])\n",
    "                    temp_node = Node(self.map, temp_Cs, temp_Ks, temp_path, self.path_cost+1, temp_drs, self.m, self.n)\n",
    "                    if not is_in_list(temp_node, expanded, True):\n",
    "                        if not is_in_list(temp_node, frontier, True):\n",
    "                            frontier.append(temp_node)\n",
    "            break\n",
    "        return None\n",
    "        \n",
    "    #Calculat Huristic\n",
    "    def h(self):\n",
    "        value = 0\n",
    "        for dr in self.Drs:\n",
    "            temp = ((self.m-1) - dr[1]) + ((self.n-1) - dr[2])\n",
    "            if temp > value:\n",
    "                value = temp\n",
    "        return value\n",
    "        \n",
    "    def is_same_for_BFS(self, node):\n",
    "        if self.Cs == node.Cs and self.Ks == node.Ks:\n",
    "            for dr in self.Drs:\n",
    "                if not is_dr_in_list(dr, node.Drs, self.m, self.n):\n",
    "                    return False\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def is_same_for_IDS(self, node):\n",
    "        if len(self.Drs) == len(node.Drs) and self.path_cost == node.path_cost:\n",
    "            if self.Cs == node.Cs and self.Ks == node.Ks:\n",
    "                if self.Drs == node.Drs:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30b152f0",
   "metadata": {},
   "source": [
    "## Test Implementation with BFS"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27700e40",
   "metadata": {},
   "source": [
    "### این الگوریتم کامل است و همواره جواب بهینه را به دست می آورد ولی از نظر تعداد استیت های دیده شده و زمان اجرا بهینه نیست "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "644ff36b",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "7606f130",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo = Fifo()\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "d91cf6ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo.put(Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "0d5f40d2",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'R'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "while not fifo.empty():\n",
    "    curr_node = fifo.get()\n",
    "    answer = curr_node.expand(fifo, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "b4e8f97c",
   "metadata": {},
   "outputs": [],
   "source": [
    "bfs_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "bcc28013",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.005742311477661133"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "1d4e9863",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "63"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be023cc3",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "0dfe4153",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo = Fifo()\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "id": "6dd5a7b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo.put(Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "89c266b6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "while not fifo.empty():\n",
    "    curr_node = fifo.get()\n",
    "    answer = curr_node.expand(fifo, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "4bafcf18",
   "metadata": {},
   "outputs": [],
   "source": [
    "bfs_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "id": "067b7f1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.021946191787719727"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "id": "008b3c46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "157"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53c27462",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "568e8261",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo = Fifo()\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "4748294e",
   "metadata": {},
   "outputs": [],
   "source": [
    "fifo.put(Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "b34d1ac0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 19\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "while not fifo.empty():\n",
    "    curr_node = fifo.get()\n",
    "    answer = curr_node.expand(fifo, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "8d7c2d38",
   "metadata": {},
   "outputs": [],
   "source": [
    "bfs_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "632e9954",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4844472408294678"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "745a8fe3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1010"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3de50c52",
   "metadata": {},
   "source": [
    "## Test Implementation with IDS"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afb9f05b",
   "metadata": {},
   "source": [
    "### این الگوریتم کامل است و همواره جواب بهینه را می دهد ولی از نظر تعداد استیت ها و زمان اجرا بهینه نیست "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddc93798",
   "metadata": {},
   "source": [
    "### زمان اجرای این الگوریتم از بی اف اس نیز بیشتر است چرا که به ازای هر بار که لیمیت افزایش پیدا می کند تمام نود ها با ارتفاع کمتر که در مرحله ی قبل دیده شده اند باز بررسی می شوند"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f24ccb3",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "53407d38",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time() \n",
    "answer = None\n",
    "all_expanded = []\n",
    "limit = 1\n",
    "\n",
    "while answer == None:\n",
    "    all_expanded.extend(expanded)\n",
    "    expanded = []\n",
    "    first_node = Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0]))\n",
    "    answer = first_node.RDLS(expanded, limit)\n",
    "    limit += 1\n",
    "last_time = time.time()\n",
    "\n",
    "print(\"answer found\")\n",
    "print(\"path cost =\", answer.path_cost)\n",
    "print(answer.path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "97959d7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "ids_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "d9154571",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.15900492668151855"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ids_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "d96f0a3f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7046"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(all_expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4d527d2",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "7a8f5282",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time() \n",
    "answer = None\n",
    "all_expanded = []\n",
    "limit = 1\n",
    "\n",
    "while answer == None:\n",
    "    all_expanded.extend(expanded)\n",
    "    expanded = []\n",
    "    first_node = Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0]))\n",
    "    answer = first_node.RDLS(expanded, limit)\n",
    "    limit += 1\n",
    "last_time = time.time()\n",
    "\n",
    "print(\"answer found\")\n",
    "print(\"path cost =\", answer.path_cost)\n",
    "print(answer.path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "42fda782",
   "metadata": {},
   "outputs": [],
   "source": [
    "ids_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "3df3ec78",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.45502138137817383"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ids_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "16eede86",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1903"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(all_expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9eb3184",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "4c2e65ac",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 19\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time() \n",
    "answer = None\n",
    "all_expanded = []\n",
    "limit = 19\n",
    "\n",
    "while answer == None:\n",
    "    all_expanded.extend(expanded)\n",
    "    expanded = []\n",
    "    first_node = Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0]))\n",
    "    answer = first_node.RDLS(expanded, limit)\n",
    "    limit += 1\n",
    "last_time = time.time()\n",
    "\n",
    "print(\"answer found\")\n",
    "print(\"path cost =\", answer.path_cost)\n",
    "print(answer.path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "edcf71fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "ids_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "10869578",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.031402587890625"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ids_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "f5a78761",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "794"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(all_expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34cca8a7",
   "metadata": {},
   "source": [
    "## Test Implementation with A* with consistent heuristic"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92c137c8",
   "metadata": {},
   "source": [
    "### این الگوریتم کامل است و همواره جواب بهینه را می دهد و از نظر تعداد استیت ها و زمان اجرا نیز از دو الگوریتم قبلی بهتر است چون بر خلاف دو الگوریتم قبلی که جستجوی نا آگاهانه بودند این الگوریتم جستجوی آگاهانه است و همچنین ثابت می شود که بهینه ترین الگوریتم کاملی است که جواب بهینه را به دست می آورد "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88bd9c7b",
   "metadata": {},
   "source": [
    "### هیوریستیک  را برابر بیشترین میزان فاصله ی منهتن دکترها تا خانه ی پایان در نظر می گیریم"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e922b178",
   "metadata": {},
   "source": [
    "### واضح است که این هیوریستیک ادمیسیبل می باشد چون برای رسیدن همه ی دکتر ها به خانه ی پایان هر کدام باید حداقل به میزان فاصله ی منهتن شان تا خانه ی پایانی حرکت انجام دهند بنا براین میزان فاصله تا هدف همواره بیشتر از این هیوریستسک می باشد"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b009f5e",
   "metadata": {},
   "source": [
    "### از طرفی چون هیوریستیک را برابر بیشتر مقدار فاصله ی منهتن دکتر ها در نظر گرفتیم پس همواره نزولی است و با اضافه شدن دکتر جدید نیز چون فاصله تا هدف نیز افزایش می یابد پس افزایش احتمالی مقدار این هیوریستیک با کانسیستنسی در تناقض نیست بنا بر این هیوریستیک انتخاب شده کانسیستنت است"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc8e6118",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "b1b87765",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "id": "df27b931",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "id": "d5591c5a",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "id": "8edc1bcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "fb119df5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.004033803939819336"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "50fb0a28",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f378772",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "id": "e09218e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "id": "af270277",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "id": "c50ffff0",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "id": "9679dea7",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "id": "e287fdc4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.015845537185668945"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "id": "cf87fd54",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "126"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe40f712",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "id": "2935a631",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "id": "74b990db",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "c211e91e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 19\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "id": "f8f2fde9",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "id": "fd773c45",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.12406754493713379"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "049aefc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "517"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac0823ea",
   "metadata": {},
   "source": [
    "## Implementation with weighted A* with Alfa = 1.3 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b3aa65b",
   "metadata": {},
   "source": [
    "### این الگوریتم کامل است ولی همواره جواب بهینه را نمی دهد چون به دلیل وجود ضریب آلفا امکان دارد به مسیر غیر بهینه امتیاز بیشتری بدهد ولی از نظر تعداد استیت ها و زمان اجرا ممکن است از تمامی الگوریتم های بالا بهتر و سریع تر باشد (که این سرعت ممکن است به قیمت به دست آوردن جوابی غیر بهینه تمام شود) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bda602b",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "d5d55e5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "id": "0ebaa0d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "4385bf51",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 1.3)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "b924dd67",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "id": "f8b2618d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0032253265380859375"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "id": "b3326746",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb00277f",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "8f79c3e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "c8a13018",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "id": "891bd557",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 1.3)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "id": "651eb8bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "id": "50ba80f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.017159461975097656"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "id": "0f0af975",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "127"
      ]
     },
     "execution_count": 188,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddc153c8",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "id": "869630ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "id": "94652e4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "id": "7d4dcfd2",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 19\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 1.3)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "id": "bfdc0118",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "id": "b82c0e03",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0933837890625"
      ]
     },
     "execution_count": 193,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "id": "bc548303",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "423"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73dbbf22",
   "metadata": {},
   "source": [
    "## Implementation with weighted A* with Alfa = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d116ad75",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "id": "a52c0d11",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "3f2a9a66",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "08d88103",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 2)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "id": "bc6e31e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "id": "98e4d06e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.002824544906616211"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "id": "0f4414d6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "655d7ad4",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "id": "4eb4c94a",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "id": "2494bc4d",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "id": "a21e525c",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 2)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "id": "139bb795",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "id": "17370d05",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.015638351440429688"
      ]
     },
     "execution_count": 205,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "id": "6ddcd067",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "126"
      ]
     },
     "execution_count": 206,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c794005c",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "id": "1c40bd49",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "id": "e65c6fe8",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "id": "b025450e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 19\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 1.5)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "id": "2a88f01f",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "id": "a944f39a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.10792803764343262"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "id": "7009cf4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "415"
      ]
     },
     "execution_count": 212,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e21ec1f",
   "metadata": {},
   "source": [
    "## Implementation with weighted A* with Alfa = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94f95260",
   "metadata": {},
   "source": [
    "## Test 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "id": "a7b6feff",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "id": "bba9c1ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[0], Cs[0], Ks[0], [], 0, [[0, 0, 0]], len(maps[0]), len(maps[0][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "id": "a7f77766",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 11\n",
      "[[0, 'R'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 5)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "id": "4afc099b",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "id": "f68d6ffc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0028481483459472656"
      ]
     },
     "execution_count": 217,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "id": "e66d3c60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "39"
      ]
     },
     "execution_count": 218,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e81f126",
   "metadata": {},
   "source": [
    "## Test 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "id": "d1660871",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "id": "f10abb91",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[1], Cs[1], Ks[1], [], 0, [[0, 0, 0]], len(maps[1]), len(maps[1][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "id": "75f51d21",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 13\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'D'], [0, 'R'], [1, 'U'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'D'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 5)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "id": "befe4e0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "id": "df53cee6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.014698028564453125"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "f7b910d8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "117"
      ]
     },
     "execution_count": 224,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed3751d3",
   "metadata": {},
   "source": [
    "### مشاهده می شود که در تست بالا به علت زیاد بودن مقدار آلفا جوابی غیر بهینه به دست آمده است"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e774e84f",
   "metadata": {},
   "source": [
    "## Test 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "id": "b94575ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier = []\n",
    "expanded = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "id": "d7a11951",
   "metadata": {},
   "outputs": [],
   "source": [
    "frontier.append(Node(maps[2], Cs[2], Ks[2], [], 0, [[0, 0, 0]], len(maps[2]), len(maps[2][0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "id": "d10067c4",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "answer found\n",
      "path cost = 21\n",
      "[[0, 'D'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'D'], [0, 'R'], [0, 'R'], [0, 'U'], [0, 'R'], [0, 'D'], [0, 'D'], [0, 'D'], [0, 'D'], [1, 'R'], [1, 'R'], [1, 'R'], [1, 'U'], [1, 'D'], [1, 'R'], [1, 'R']]\n"
     ]
    }
   ],
   "source": [
    "first_time = time.time()\n",
    "answer = None\n",
    "while answer == None:\n",
    "    curr_node = get_best(frontier, 5)\n",
    "    if curr_node == None:\n",
    "        break\n",
    "    answer = curr_node.RBFS(frontier, expanded)\n",
    "    if answer != None:\n",
    "        print(\"answer found\")\n",
    "        print(\"path cost =\", answer.path_cost)\n",
    "        print(answer.path)\n",
    "        break\n",
    "last_time = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "86528307",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_star_time = last_time - first_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "id": "3746d495",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1055455207824707"
      ]
     },
     "execution_count": 229,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_star_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "id": "43786b15",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "446"
      ]
     },
     "execution_count": 230,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "169cf076",
   "metadata": {},
   "source": [
    "### در این تست نیز جوابی غیر بهینه به دست آمده است"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29dd400f",
   "metadata": {},
   "source": [
    "# نتیجه گیری"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "125f27bb",
   "metadata": {},
   "source": [
    "### بهترین الگوریتم کامل که همواره جواب بهینه را با بیشترین سرعت ممکن به دست آورد الگوریتم زیر می باشد"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89c7fb0a",
   "metadata": {},
   "source": [
    "## A* with cosistent huristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a15d995",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}