6 贪心算法
贪心算法
概述
思想
- 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
- 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
特点
- 贪心算法不能对所有问题都得到整体最优解。但对许多问题他能产生整体最优解，或者最优解的近似。
- 贪心算法中较大子问题的解敲好包含了较小子问题的解作为子集。与动态规划算法中的优化原则本质上一致。
- 动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑他的所有子问题的优化函数的值。然后从中选出最有的结果。贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当前的情况采取“只顾眼前”的贪心策略决定取舍。
贪心算法的适用条件
- 最优子结构性质
- 一个问题的最优解包含其子问题的最优解。问题具有最优子结构性质时，可以用动态规划算法或者贪心算法求解。
- 贪心选择性质
- 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
- 动态规划算法通常是自底向上的方式来求解各个子问题。贪心算法同行一自顶向下的方式，一迭代的方式作出相机的谈心选择。每左慈谈心选择就将所求问题简化为规模更小的子问题。
- 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
贪心算法正确性
- 贪心算法不一定得到最优解。贪心策略的选择可能有多重，选择合适的贪心策略并进行正确性证明。
方法
- 算法步数的归纳
- 问题规模的归纳
贪心的核心思想-特点
- 可行的：即它必须满足问题的约束。
- 局部最优：它是当前步骤中所有可行性选择中最佳的局部选择。
- 不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。
2 反向贪心思想
- 正向贪心思想，每次都能选择最优的结果，最终能够选择所有最优子问题构成的最优解。
- 反向贪心思想，虽然无法确定当前的最优结果。但是每次都能排除掉最差的结果。通过一系列排除最差结果的方法，得到最后的最优解。
实例
以上三个问题，每次的谈心选择，不是选择当前步骤的最优解，而是排除不可能的最差情况。
3 常见问题
分数背包问题
最短路径问题
Dijkstra’s Algorithm
Prim’s
Kruskal’s
Huffman 算法与决策树
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Estom的博客！
相关推荐
2020-09-26
triplot_demo
Triplot Demo创建和绘制非结构化三角形网格。 123import matplotlib.pyplot as pltimport matplotlib.tri as triimport numpy as np 在不指定三角形的情况下创建三角剖分会导致点的Delaunay三角剖分。 1234567891011121314151617181920# First create the x and y coordinates of the points.n_angles = 36n_radii = 8min_radius = 0.25radii = np.linspace(min_radius, 0.95, n_radii)angles = np.linspace(0, 2 * np.pi, n_angles, endpoint=False)angles = np.repeat(angles[..., np.newaxis], n_radii, axis=1)angles[:, 1::2] += np.pi / n_anglesx = (radii * np.cos(angle...
2020-09-26
boxplot_demo_pyplot
Boxplot 演示boxplot 的代码示例。 123456789101112import numpy as npimport matplotlib.pyplot as plt# Fixing random state for reproducibilitynp.random.seed(19680801)# fake up some dataspread = np.random.rand(50) * 100center = np.ones(25) * 50flier_high = np.random.rand(10) * 100 + 100flier_low = np.random.rand(10) * -100data = np.concatenate((spread, center, flier_high, flier_low)) 123fig1, ax1 = plt.subplots()ax1.set_title('Basic Plot')ax1.boxplot(data) 123fig2, ax2 = plt.subplots()ax2.set...
2021-04-07
23 慢查询日志
Redis的慢查询日志，用于记录执行时间超过给定时长的命令请求，用户可以通过这个日志来监视和优化查询速度。 服务器有两个选项和慢查询有关： slowlog-log-slower-than，指定执行时间超过多少微妙的命令请求会被记录到日志上。 slowlog-max-len，指定服务器上最多保存多少条慢查询日志。数量超过，则先入先出。 SLOWLOG GET可以查看服务器保存的慢查询日志。 23.1 慢查询日志的保存123456789101112131415161718192021222324252627struct redisServer { // 下一条日志的ID long long slowlog_entry_id; // 保存了所有日志的链表 lisg *slowlog; long long slowlog_log_slower_than; unsigned long slowlog_max_len;};// slowlog链表保存了所有慢查询日志，每个节点都保存了一个slowlogEntry结构，代表一条日志...
2020-09-26
spy_demos
Spy 演示绘制数组的稀疏模式。 1234567891011121314151617181920import matplotlib.pyplot as pltimport numpy as npfig, axs = plt.subplots(2, 2)ax1 = axs[0, 0]ax2 = axs[0, 1]ax3 = axs[1, 0]ax4 = axs[1, 1]x = np.random.randn(20, 20)x[5, :] = 0.x[:, 12] = 0.ax1.spy(x, markersize=5)ax2.spy(x, precision=0.1, markersize=5)ax3.spy(x)ax4.spy(x, precision=0.1)plt.show() 参考此示例中显示了以下函数，方法和类的使用： 123import matplotlibmatplotlib.axes.Axes.spymatplotlib.pyplot.spy 下载这个示例 下载python源码: spy_demos.py 下载Jupyter notebook: spy_de...
2020-10-14
01神经网络基础
神经网络基础 介绍神经网络的编程基础。看完视频，在总结这一部分。每一个视频，完成开始做笔记。 1 识别图片上的猫问题定义 场景定义：监督学习。图像识别领域。非结构化数据输入。 问题定义：分类问题。 算法定义：logistics回归。 问题描述 输入的特征向量：$x \in R^{n_x}$，其中 ${n_x}$是特征数量； 输出的标签，用于训练的标签：$y \in 0,1$ 训练集：${(x^{(1)},y^{(1)}),\dots,(x^{(m)},y^{(m)})}$紧凑矩阵表示训练集。约定使用列向量。 2 Logistic回归模型 Logistic 回归是一个用于二分分类的算法。 模型定义-假设函数 权重：$w \in R^{n_x}$ 偏置： $b \in R$ 输出：$\hat{y} = \sigma(w^Tx+b)$ Sigmoid 函数：$$s = \sigma(w^Tx+b) = \sigma(z) = \frac{1}{1+e^{-z}}$$ 将 $w^Tx+b$ 约束在 [0, 1] 间...
2020-09-26
tripcolor_demo
Tripcolor Demo非结构化三角形网格的伪彩色图。 123import matplotlib.pyplot as pltimport matplotlib.tri as triimport numpy as np 在不指定三角形的情况下创建三角剖分会导致点的Delaunay三角剖分。 123456789101112131415161718192021# First create the x and y coordinates of the points.n_angles = 36n_radii = 8min_radius = 0.25radii = np.linspace(min_radius, 0.95, n_radii)angles = np.linspace(0, 2 * np.pi, n_angles, endpoint=False)angles = np.repeat(angles[..., np.newaxis], n_radii, axis=1)angles[:, 1::2] += np.pi / n_anglesx = (radii * np.cos(a...
