{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.1 基于搜索的问题求解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现实世界中许多问题都可以通过搜索的方法来求解，例如设计最佳出行路线或是制订合理的课程表。当给定一个待求解问题后，搜索算法会按照事先设定的逻辑来自动寻找符合求解问题的答案，因此一般可将搜索算法称为问题求解智能体。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://imgbed.momodel.cn//20200110155424.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1.1 搜索算法基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们把书中的公交换乘的问题，转为无向图中的的路径寻找问题。无向图指的是边没有方向的图。\n",
    "\n",
    "首先，我们画出如下的无向图。该无向图中有 A，B，C，D，E，F，G 七个节点，其中 A 是起点， G 是目标点。\n",
    "\n",
    "点与点之间的连线称为边，边可以有权重，可以代表点与点之间的距离或者从一个点转移到另一个点需要花费的代价。\n",
    "\n",
    "下面我们先创建一个图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 首先导入必要的包\n",
    "from search import SearchGraph\n",
    "import collections\n",
    "import matplotlib.pyplot as plt\n",
    "import collections\n",
    "from IPython import display\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义节点列表\n",
    "node_list = ['A', 'B', 'C', 'D', 'E', 'F', 'G']\n",
    "\n",
    "# 定义边及权重列表\n",
    "weighted_edges_list = [('A', 'B', 8), ('A', 'C', 20),\n",
    "                       ('B', 'F', 40), ('B', 'E', 30),\n",
    "                       ('B', 'D', 20), ('C', 'D', 10), \n",
    "                       ('D', 'G', 10), ('D', 'E', 10),\n",
    "                       ('E', 'F', 30), ('F', 'G', 30)]\n",
    "# 定义绘图中各个节点的坐标\n",
    "nodes_pos = {\"A\": (1, 1), \"B\": (3, 3), \"C\": (5, 0), \"D\": (9, 2),\n",
    "             \"E\": (7, 4), \"F\": (6,6),\"G\": (11,5)}\n",
    "\n",
    "# 绘制无向图\n",
    "g = SearchGraph(node_list, weighted_edges_list, 'A', 'G', max_depth=3, nodes_pos = nodes_pos )\n",
    "g.show_graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观察上图，可以看到从起点 A 到目标点 G 距离最短的路径是 A -> B -> D  -> G，其距离是 38，我们可以设计一个计算机程序，按照既定的规则，从起点 A 出发，不断尝试从一个节点移动到下一个节点，直到抵达目标点 G。\n",
    "\n",
    "在详细描述搜索算法之前，先了解下面四个重要的概念。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ **状态**。  在上面的例子中状态是什么？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ **测试目标**。 在上面的例子中测试目标是什么？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ **动作**。在上面的例子中动作是什么？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ **路径**。在上面的例子中路径是什么？\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更改下面的代码，设置一条路径并查看。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.show_graph(this_path=\"ABDG\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1.2 搜索算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搜索算法就是不断从某一状态转移到下一状态，直至到达终止状态为止。\n",
    "\n",
    "**搜索树**是什么？\n",
    "\n",
    "如何构造搜索树 ？\n",
    "\n",
    "思考一下，路径搜索能出现回路吗？\n",
    "\n",
    "在搜索树中能够扩展的节点需满足什么条件？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查看搜索树\n",
    "g.show_search_tree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1.3 深度优先搜索和广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://imgbed.momodel.cn//20200110151426.png\" width=600>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**深度优先搜索**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.animation_search_tree('dfs')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**广度优先搜索**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.animation_search_tree('bfs')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于一个搜索问题，只要存在答案（即从初始节点到终止节点存在满足条件的一条路径），那么深度优先搜索和广度优先搜索都能找到一个答案吗？找到的答案一定是路径最短的吗？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1.4 启发式搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "能否在搜索过程中利用问题的定义以外**辅助信息**？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**辅助信息：各个节点到目标节点G的直线距离**\n",
    "\n",
    "|站点|A|B|C|D|E|F|G|\n",
    "|--|--|--|--|--|--|--|--|\n",
    "|距离|30|20|19|10|5|25|0|\n",
    "\n",
    "如果每下一站都选最近的，那么称之为“贪婪”。\n",
    "\n",
    "利用下面的代码查看贪婪最佳优先算法搜索过程："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 为搜索算法提供辅助信息\n",
    "g.help_info = {'A': 30, 'B': 20, 'C': 19, 'D':10, 'E':5, 'F':25, 'G': 0}\n",
    "# 动态演示贪婪搜索\n",
    "g.animation_search_tree('greedy')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“贪婪”机制下找到的最佳路径是什么呢？它是最短路径吗？为什么会产生这样的搜索结果？\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何克服贪婪算法的不足？\n",
    " A\\*算法\n",
    "\n",
    " A\\*算法搜索过程：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 为搜索算法提供辅助信息\n",
    "g.help_info = {'A': 30, 'B': 20, 'C': 19, 'D':10, 'E':5, 'F':25, 'G': 0}\n",
    "# 动态演示 A* 算法\n",
    "g.animation_search_tree('a_star')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 可以调整辅助信息的比重\n",
    "# 当只考虑额外信息时，即 origin_info_weight 设置为 0 的时候，A* 算法退化为贪婪算法。\n",
    "g.animation_search_tree('a_star',help_info_weight=1, origin_info_weight=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在实际中，A\\* 算法的性能表现一定很优秀吗？如果启发函数设计的不好怎么办？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  思考与练习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下图是一张线路示意图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_list = [\"0\",\"1\",\"2\",\"3\",\"4\"]\n",
    "weighted_edges_list = [(\"0\",\"1\",10), (\"0\",\"2\",10),\n",
    "                       (\"1\", \"3\", 10), (\"2\", \"3\", 5), \n",
    "                       (\"2\", \"4\", 20), (\"3\", \"4\", 14),\n",
    "                       (\"3\", \"2\", 5)]\n",
    "nodes_pos = {\"0\":(1,7),\"1\":(5,1),\"2\":(5,13),\"3\":(9,7),\"4\":(11,13)}\n",
    "h_graph = SearchGraph(node_list, weighted_edges_list, \"0\", \"4\", 5, nodes_pos)\n",
    "h_graph.show_graph()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果使用深度优先搜索求状态 0 到状态 4 的一条路径，我们可以用下表来模拟搜索过程。注意：在下表中，结点的深度定义为它对应路径中状态转移的次数，如果多个未访问结点的深度相同，那么在这个例子里算法优先选择状态编号大的节点。\n",
    "\n",
    "|步骤|当前状态|当前未访问节点集合(用上划线标出了下一个扩展的节点)|\n",
    "|:--:|:--:|:--|\n",
    "|1|0|深度1：${0 -> 1,\\overline{0 -> 2}}$|\n",
    "|2|2|深度1：${0 -> 1}$ 深度2：$\\underline{（1）}$|\n",
    "|3|$\\underline{（2）}$|找到路径：0 -> 2 -> 4|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**问题 1**：请仔细观察上表中各项内容的含义，根据深度优先搜素的思路，横线（1）和（2）处应该填写什么。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**答案 1**：（在此处填写你的答案。）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**问题 2**：找到的路径0->2->4是代价最小的吗？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**答案 2**：（在此处填写你的答案。）\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}