算法图解/chap08-贪婪算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第8章 贪婪算法\n",
    "## 8.1 教室调度问题\n",
    "\n",
    "如下课程表，你希望将尽可能多的课程安排在某间教室上。没法让这些课都在这间教室上，因为有些课的上课时间有冲突\n",
    "![](https://i.loli.net/2019/08/11/A2OQediGgmpsuWI.png)\n",
    "\n",
    "算法如下：\n",
    "- (1) 选出结束最早的课，它就是要在这间教室上的第一堂课。\n",
    "- (2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。\n",
    "\n",
    "![](https://i.loli.net/2019/08/11/BU9dZ5tVgowEDqL.png)\n",
    "\n",
    "贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。\n",
    "\n",
    "## 8.2 背包问题\n",
    "\n",
    "假设你是个贪婪的小偷，背着可装35磅（1磅≈0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。你力图往背包中装入价值最高的商品，你会使用哪种算法呢？\n",
    "\n",
    "同样，你采取贪婪策略，这非常简单。\n",
    "- (1) 盗窃可装入背包的最贵商品。\n",
    "- (2) 再盗窃还可装入背包的最贵商品，以此类推。\n",
    "\n",
    "![](https://i.loli.net/2019/08/11/pTe65g9wEV8yAcZ.png)\n",
    "\n",
    "音响最贵，你把它给偷了，但背包没有空间装其他东西了。你偷到了价值3000美元的东西。如果不是偷音响，而是偷笔记本电脑和吉他，总价将为3500美元！\n",
    "\n",
    "在这里，贪婪策略显然不能获得最优解，但非常接近。下一章将介绍如何找出最优解。不过小偷去购物中心行窃时，不会强求所偷东西的总价最高，只要差不多就行了。\n",
    "\n",
    "从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。\n",
    "\n",
    "下面来看最后一个例子。在这个例子中，你别无选择，只能使用贪婪算法。\n",
    "\n",
    "## 8.3 集合覆盖问题\n",
    "\n",
    "假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。\n",
    "\n",
    "每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。\n",
    "\n",
    "![](https://i.loli.net/2019/08/11/BSkwEKMp8gFRUY7.png)\n",
    "\n",
    "如何找出覆盖全美50个州的最小广播台集合呢？\n",
    "\n",
    "听起来很容易，但其实非常难。具体方法如下。\n",
    "\n",
    "- (1) 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有$2^n$ 个。\n",
    "- (2) 在这些集合中，选出覆盖全美50个州的最小集合。\n",
    "\n",
    "问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2 n 个，因此运行时间为$O (2^n )$。如果广播台不多，只有5～10个，这是可行的。但如果广播台很多，结果将如何呢？随着广播台的增多，需要的时间将激增。假设你每秒可计算10个子集，所需的时间将如下。\n",
    "\n",
    "![](https://i.loli.net/2019/08/11/g48wrbWLjQ316pF.png)\n",
    "\n",
    "没有任何算法可以足够快地解决这个问题！怎么办呢？\n",
    "\n",
    "### 近似算法\n",
    "\n",
    "使用下面的贪婪算法可得到非常接近的解。\n",
    "- (1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。\n",
    "- (2) 重复第一步，直到覆盖了所有的州。\n",
    "\n",
    "这是一种近似算法（approximation algorithm）。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：\n",
    "- 速度有多快；\n",
    "- 得到的近似解与最优解的接近程度。\n",
    "\n",
    "**1. 准备工作**\n",
    "出于简化考虑，这里假设要覆盖的州没有那么多，广播台也没有那么多。\n",
    "首先，创建一个列表，其中包含要覆盖的州。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "states_needed = set([\"mt\", \"wa\", \"or\", \"id\", \"nv\", \"ut\",\"ca\", \"az\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我使用集合来表示要覆盖的州。集合类似于列表，只是同样的元素只能出现一次，即集合不能包含重复的元素。\n",
    "\n",
    "还需要有可供选择的广播台清单，我选择使用散列表来表示它。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "stations = {}\n",
    "stations[\"kone\"] = set([\"id\", \"nv\", \"ut\"])\n",
    "stations[\"ktwo\"] = set([\"wa\", \"id\", \"mt\"])\n",
    "stations[\"kthree\"] = set([\"or\", \"nv\", \"ca\"])\n",
    "stations[\"kfour\"] = set([\"nv\", \"ut\"])\n",
    "stations[\"kfive\"] = set([\"ca\", \"az\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中的键为广播台的名称，值为广播台覆盖的州。\n",
    "\n",
    "最后，需要使用一个集合来存储最终选择的广播台。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "final_stations = set()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. 计算答案**\n",
    "\n",
    "接下来需要计算要使用哪些广播台。你需要遍历所有的广播台，从中选择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在best_station中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "states_covered 是一个集合，包含该广播台覆盖的所有未覆盖的州。 for 循环迭代每个广播台，并确定它是否是最佳的广播台。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "while states_needed:\n",
    "    best_station = None\n",
    "    states_covered = set()\n",
    "    for station, states in stations.items(): #找到覆盖未覆盖州最多的电台\n",
    "        covered = states_needed & states\n",
    "        if len(covered) > len(states_covered):\n",
    "            best_station = station\n",
    "            states_covered = covered\n",
    "    stations -= best_station #去掉已经取出来的电台\n",
    "    states_needed -= states_covered #去掉已经覆盖的州\n",
    "    final_stations.add(best_station) #在结果中添加现在找到的电台"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'kfive', 'kone', 'kthree', 'ktwo'}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final_stations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8.4 NP 完全问题\n",
    "\n",
    "为解决集合覆盖问题，你必须计算每个可能的集合。\n",
    "\n",
    "这可能让你想起了第1章介绍的旅行商问题。在这个问题中，旅行商需要前往5个不同的城市。他需要找出前往这5个城市的最短路径，为此，必须计算每条可能的路径。\n",
    "\n",
    "### 8.4.1 旅行商问题详解\n",
    "\n",
    "我们从城市数较少的情况着手。假设只涉及两个城市，因此可供选择的路线有两条。\n",
    "\n",
    "你可能认为这两条路线相同，难道从旧金山到马林的距离与从马林到旧金山的距离不同吗？不一定。有些城市（如旧金山）有很多单行线，因此你无法按原路返回。你可能需要离开原路行驶一两英里才能找到上高速的匝道。因此，这两条路线不一定相同。\n",
    "\n",
    "你可能心存疑惑：在旅行商问题中，必须从特定的城市出发吗？例如，假设我是旅行商。我居住在旧金山，需要前往其他4个城市，因此我将从旧金山出发。\n",
    "\n",
    "但有时候，不确定要从哪个城市出发。假设联邦快递将包裹从芝加哥发往湾区，包裹将通过航运发送到联邦快递在湾区的50个集散点之一，再装上经过不同配送点的卡车。该通过航运发送到哪个集散点呢？在这个例子中，起点就是未知的。因此，你需要通过计算为旅行商找出起点和最佳路线。\n",
    "\n",
    "在这两种情况下，运行时间是相同的。但出发城市未定时更容易处理，因此这里以这种情况为例。\n",
    "\n",
    "- 涉及两个城市时，可能的路线有两条。\n",
    "- 3个城市时，可能的路线有6条。\n",
    "- 可能的出发城市有4个，从每个城市出发时都有6条可能的路线，因此可能的路线有4 × 6 = 24条。\n",
    "- 涉及6个城市时，可能的路线有720条\n",
    "\n",
    "这被称为阶乘函数（factorial function），第3章介绍过。5! = 120。假设有10个城市，可能的路线有多少条呢？10! = 3 628 800。换句话说，涉及10个城市时，需要计算的可能路线超过300万条。正如你看到的，可能的路线数增加得非常快！因此，如果涉及的城市很多，根本就无法找出旅行商问题的正确解。\n",
    "\n",
    "旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。\n",
    "\n",
    "NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。\n",
    "\n",
    "### 8.4.2 如何识别 NP 完全问题\n",
    "\n",
    "NP完全问题无处不在！如果能够判断出要解决的问题属于NP完全问题就好了，这样就不用去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。例如，前一章深入讨论了最短路径，你知道如何找出从A点到B点的最短路径。\n",
    "\n",
    "\n",
    "但如果要找出经由指定几个点的的最短路径，就是旅行商问题——NP完全问题。简言之，没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的。\n",
    "\n",
    "- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。\n",
    "- 涉及“所有组合”的问题通常是NP完全问题。\n",
    "- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。\n",
    "- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。\n",
    "- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。\n",
    "- 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。\n",
    "\n",
    "## 8.5 小结\n",
    "\n",
    "- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。\n",
    "- 对于NP完全问题，还没有找到快速解决方案。\n",
    "- 面临NP完全问题时，最佳的做法是使用近似算法。\n",
    "- 贪婪算法易于实现、运行速度快，是不错的近似算法。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (system-wide)",
   "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}