GBFS.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "import heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Definite class Tree"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, data, goal_cost):\n",
    "        self.data = data\n",
    "        self.children = []\n",
    "        self.goal_cost = goal_cost\n",
    "\n",
    "    def add_child(self, child):\n",
    "        self.children.append(child)\n",
    "\n",
    "    def get_children(self):\n",
    "        return self.children\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.goal_cost < other.goal_cost"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Greedy Best-first Search"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [],
   "source": [
    "def update_frontier(frontier, new_node):\n",
    "    for idx, n in enumerate(frontier):\n",
    "        if n == new_node:\n",
    "            if n.goal_cost > new_node.goal_cost:\n",
    "                frontier[idx] = new_node"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "def GBF_search(initial_state, goalTest):\n",
    "    frontier = []\n",
    "    explored = []\n",
    "    heapq.heapify(frontier)\n",
    "    heapq.heappush(frontier, initial_state)\n",
    "\n",
    "    while len(frontier) > 0:\n",
    "        state = heapq.heappop(frontier)\n",
    "        explored.append(state)\n",
    "        if state == goalTest:\n",
    "            return explored\n",
    "        for neighbor in state.get_children():\n",
    "            if neighbor not in (frontier and explored):\n",
    "                heapq.heappush(frontier, neighbor)\n",
    "            elif neighbor in frontier:\n",
    "                update_frontier(frontier, neighbor)\n",
    "    return False"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Graph\n",
    "![alt text](img.png \"Full graph\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [],
   "source": [
    "A = Tree(\"A\", 6)\n",
    "B = Tree(\"B\", 3)\n",
    "C = Tree(\"C\", 4)\n",
    "D = Tree(\"D\", 5)\n",
    "E = Tree(\"E\", 3)\n",
    "F = Tree(\"F\", 1)\n",
    "G = Tree(\"G\", 6)\n",
    "H = Tree(\"H\", 2)\n",
    "I = Tree(\"I\", 5)\n",
    "J = Tree(\"J\", 4)\n",
    "K = Tree(\"K\", 2)\n",
    "L = Tree(\"L\", 0)\n",
    "M = Tree(\"M\", 4)\n",
    "N = Tree(\"N\", 0)\n",
    "O = Tree(\"O\", 4)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [],
   "source": [
    "A.add_child(B)\n",
    "A.add_child(C)\n",
    "A.add_child(D)\n",
    "B.add_child(E)\n",
    "B.add_child(F)\n",
    "C.add_child(G)\n",
    "C.add_child(H)\n",
    "D.add_child(I)\n",
    "D.add_child(J)\n",
    "F.add_child(K)\n",
    "F.add_child(L)\n",
    "F.add_child(M)\n",
    "H.add_child(N)\n",
    "H.add_child(O)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "data": {
      "text/plain": "[<__main__.Tree at 0x10b52dbe0>,\n <__main__.Tree at 0x10b52d730>,\n <__main__.Tree at 0x10b52d6d0>,\n <__main__.Tree at 0x10b59bfa0>]"
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = GBF_search(A, L)\n",
    "result"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "explored: A B F L \n"
     ]
    }
   ],
   "source": [
    "if result:\n",
    "    s = 'explored: '\n",
    "    for i in result:\n",
    "        s += i.data + \" \"\n",
    "    print(s)\n",
    "else:\n",
    "    print(\"404 not found\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}