{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 2.1 基于搜索的问题求解"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<center><video src=\"http://files.momodel.cn/search_problem.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"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": [
"<center><video src=\"http://files.momodel.cn/search_basic_concept.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"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 Graph\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 = Graph()\n",
"g.add_nodes_from(node_list)\n",
"g.add_weighted_edges_from(weighted_edges_list)\n",
"g.set_nodes_pos(nodes_pos)\n",
"\n",
"# 设置起点\n",
"g.set_start_node('A')\n",
"# 设置目标点\n",
"g.set_target_node(\"G\")\n",
"# 设置最大搜索深度\n",
"g.set_max_depth(3)\n",
"\n",
"# 显示无向图\n",
"g.show_graph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"观察上图，可以看到从起点 A 到目标点 G 距离最短的路径是 A -> B -> D -> G，其距离是 38，我们可以设计一个计算机程序，按照既定的规则，从起点 A 出发，不断尝试从一个节点移动到下一个节点，直到抵达目标点 G。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"搜索算法四个重要的概念分别是什么？"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**动手练**"
]
},
{
"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": [
"<center><video src=\"http://files.momodel.cn/search_tree.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"搜索算法就是不断从某一状态转移到下一状态，直至到达终止状态为止。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"搜索树是什么？\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": [
"<center><video src=\"http://files.momodel.cn/search_dfs_bfs.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"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.animate_search_tree('dfs')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**广度优先搜索**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g.animate_search_tree('bfs')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"对于一个搜索问题，只要存在答案（即从初始节点到终止节点存在满足条件的一条路径），那么深度优先搜索和广度优先搜索都能找到一个答案吗？找到的答案一定是路径最短的吗？"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 扩展内容\n",
"** 深度优先搜索 dfs ** 基础代码解读\n",
"\n",
"```\n",
"def iter_dfs(G, start, target):\n",
" '''\n",
" 深度优先搜索\n",
" :param G: 字典，存储每个点的相邻点\n",
" :param start: 初始点\n",
" :param target: 目标点\n",
" :return:\n",
" '''\n",
"\n",
" # 定义已访问的点的集合\n",
" S = set()\n",
" # 定义一个待访问点的列表\n",
" Q = []\n",
" # 把初始点放进列表中\n",
" Q.append(start)\n",
" while Q:\n",
" # 只要带访问的列表不为空，那么从列表中拿取最后一个元素，也就是一个点，记作 u\n",
" u = Q.pop()\n",
" # 如果当前点是目标点，则结束查找\n",
" if u == target:\n",
" break\n",
" # 如果该点已经被访问了，则跳过此点\n",
" if u in S:\n",
" continue\n",
" # 访问此点，将点加入已访问点的结合 S 中\n",
" S.add(u)\n",
" # 将点 u 相邻的点放入待访问的列表中\n",
" Q.extend(G[u])\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2.1.4 启发式搜索"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<center><video src=\"http://files.momodel.cn/search_greedy.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"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",
"help_info = {'A': 30, 'B': 20, 'C': 19, 'D':10, 'E':5, 'F':25, 'G': 0}\n",
"g.set_help_info(help_info)\n",
"# 动态演示贪婪搜索\n",
"g.animate_search_tree('greedy', sleep_time=5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"“贪婪”机制下找到的最佳路径是什么呢？它是最短路径吗？为什么会产生这样的搜索结果？\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"另一种启发式搜索算法—— A* 算法克服了贪婪算法的不足。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<center><video src=\"http://files.momodel.cn/search_a_star.mp4\" controls=\"controls\" width=800px></center>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A\\*算法搜索过程："
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 为搜索算法提供辅助信息\n",
"help_info = {'A': 30, 'B': 20, 'C': 19, 'D':10, 'E':5, 'F':25, 'G': 0}\n",
"g.set_help_info(help_info)\n",
"# 动态演示 A* 算法\n",
"g.animate_search_tree('a_star', sleep_time=5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 可以调整辅助信息的比重\n",
"# help_info_weight 为辅助信息的比重，origin_info_weight 为原始信息的比重\n",
"# 当只考虑额外信息时，即 origin_info_weight 设置为 0 的时候，A* 算法退化为贪婪算法。\n",
"# 可以设置 sleep_time 来调整动态演示的速度\n",
"g.animate_search_tree('a_star', help_info_weight=1, origin_info_weight=0, sleep_time=5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**想一想**"
]
},
{
"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": [
"# 首先导入必要的包\n",
"from search import Graph\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 = [\"0\", \"1\", \"2\", \"3\", \"4\"]\n",
"\n",
"# 定义边及权重列表\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",
"\n",
"# 定义绘图中各个节点的坐标\n",
"nodes_pos = {\"0\": (1, 7), \"1\": (5, 1), \"2\": (5, 13), \"3\": (9, 7),\n",
" \"4\": (11, 13)}\n",
"\n",
"# 实例化图\n",
"h_graph = Graph()\n",
"h_graph.add_nodes_from(node_list)\n",
"h_graph.add_weighted_edges_from(weighted_edges_list)\n",
"h_graph.set_nodes_pos(nodes_pos)\n",
"\n",
"# 设置起点\n",
"h_graph.set_start_node('0')\n",
"# 设置目标点\n",
"h_graph.set_target_node(\"5\")\n",
"# 设置最大搜索深度\n",
"h_graph.set_max_depth(3)\n",
"\n",
"# 显示无向图\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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 扩展阅读\n",
"1. [Introduction to the A* Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n",
"2. [游戏开发中的人工智能：A* 路径寻找算法](https://blog.csdn.net/Jurbo/article/details/75532885)\n",
"3. [A* Search Algorithm](https://www.101computing.net/a-star-search-algorithm/)\n",
"4. [A star Pathfinding A星寻路算法](https://www.bilibili.com/video/av32847834/)"
]
}
],
"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
}
