贪心算法和动态规划的个人理解_多段图的最短路径贪心-程序员宅基地

技术标签：算法

最近通过各个公司的笔试题发现，好多编程题都是贪心算法和动态规划算法。这两个也容易混淆，在网上也看了好多这两种算法的解析，通过这篇文章写下自己对这两种算法的理解。

使用动态规划的最大特性是原问题的最优解必须包含子问题的最优解。下面通过一个例子解释：求图的最短路径是解释动态规划最容易的问题。下面是一个多段图:

按照贪心算法的思路解决问题可以得到：v1到v2：1到2最短，所以选择2，总长s为2。v2到v3：2到5最短，所以选择5，总长为2+6=8。v3到v4：5到10最短，所以选择10，总长为8+6=14。v4到v5：10到11，总长为14+10=24。所以最短路径为1,2,5,10,11

但是这明显不是最短路径，所以通过贪心算法思路解决的话是错误的。

通过动态规划算法解决多段图最短路径规划问题的思想是，我们要计算每一个子段图到下一个子段图的所有可能的连接情况，并保留每种可能选择中最短的那个连接。

假设我们从终点反推到起点，则具体的操作可以是这样的：

v5到v4有三种路可选：11到8，11到9,11到10。记为{11,8}=6，{11,9}=5，{11,,10}=10.

v4到v3：8到5，8到6，9到6,10到5,10到6,10到7。记最短路径是：8到6，这是最短路径为11到8到6

v3到v2：6到2,6到3,6到4，记最短路径为：6到3，这是最短路径为11到8到6到3.

v2到v1：3到1，这时最短路径为11到8到6到3到1

从而求出多段图的最短路径为{1,3,6,8,11}

从上述推演过程中可以得知动态规划的算法每次都保留所有可能的最优解，那总体最优肯定包含着局部最优。而构成整体最优不一定是由当前最优解构成的。因此需要对全部解决方案进行标记。

一般我们采用动态规划算法解决问题时，首先要明确问题是否具有最优子结构，然后找出问题最优子结构的递推关系式，例如多段图最短路径规划问题中的递推公式可表述如下：

cost(i,j) = min{ c(j,l) + cost(i+1,l) }，l∈Vi+1，(j,l)∈E，E为多段图的边集，Vi+1为第i+1段中的点集

其中cost(i,j)表示的是第i段的第j个顶点到终点t的路径长度的最短值，l为第i+1段中的某个顶点，然后c(j,l)为顶点j到l之间的连接权值，即距离值。

贪心算法的解决思路就是：将问题分解为一个个子问题，找到子问题的最优解，就能得到原问题的最优解。

要求解的问题是一个最优化问题；
这个问题的解可以用n元组表示；
该问题满足最优子结构特性；
可以找到最优量度标准，并可以证明该最优量度标准能导致一个整体最优解；

适用场景：

1、单源最短路经问题
2、最小生成树问题
3、可任意分割的背包问题。如果不可以任意分割，就需要用动态规划求解。

贪心算法的原型：

SolutionType greedy(int[] a){

    // 一开始结果集为空
    SolutionType solution = {};
    // 进行n步选值
    for ( int i=0; i<n; i++ ) {
        // 选出当前局部最优解x
        x = select(a);
        // 判断x是否满足约束条件，若不满足则继续选
        while( !isFeasible(x) ){
            x = select(a);
        }
        // 将当前最优解添加至结果集中
        solution.add(x);
    }
}

本文链接：https://blog.csdn.net/weixin_41191846/article/details/81741203

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

5个超厉害的资源搜索网站，每一款都可以让你的资源满满！_最全资源搜索引擎-程序员宅基地

文章浏览阅读1.6w次，点赞8次，收藏41次。生活中我们无时不刻不都要在网站搜索资源，但就是缺少一个趁手的资源搜索网站，如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间！今天小编在这里为大家分享5款超厉害的资源搜索网站，每一款都可以让你的资源丰富精彩！网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗？这款网站传奇网站汇聚了4853w个资源，并且它每一天都会持续更新资源；..._最全资源搜索引擎

Book类的设计(Java)_6-1 book类的设计java-程序员宅基地

文章浏览阅读4.5k次，点赞5次，收藏18次。阅读测试程序，设计一个Book类。函数接口定义：class Book{}该类有四个私有属性分别是书籍名称、价格、作者、出版年份，以及相应的set 与get方法；该类有一个含有四个参数的构造方法，这四个参数依次是书籍名称、价格、作者、出版年份。裁判测试程序样例：import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java

基于微信小程序的校园导航小程序设计与实现_校园导航微信小程序系统的设计与实现-程序员宅基地

文章浏览阅读613次，点赞28次，收藏27次。相比于以前的传统手工管理方式，智能化的管理方式可以大幅降低学校的运营人员成本，实现了校园导航的标准化、制度化、程序化的管理，有效地防止了校园导航的随意管理，提高了信息的处理速度和精确度，能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术，前端以小程序页面呈现给学生，结合后台java语言使页面更加完善，后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能，从而实现智能化的管理方式，提高工作效率。

有状态和无状态登录

传统上用户登陆状态会以 Session 的形式保存在服务器上，而 Session ID 则保存在前端的 Cookie 中；而使用 JWT 以后，用户的认证信息将会以 Token 的形式保存在前端，服务器不需要保存任何的用户状态，这也就是为什么 JWT 被称为无状态登陆的原因，无状态登陆最大的优势就是完美支持分布式部署，可以使用一个 Token 发送给不同的服务器，而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。

九大角度全方位对比Android、iOS开发_ios 开发角度-程序员宅基地

文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要：即便Android市场份额已经超过80%，对于开发者来说，使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度

搜索引擎的发展历史

搜索引擎的发展历史可以追溯到20世纪90年代初，随着互联网的快速发展和信息量的急剧增加，人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进，以满足用户对信息获取的不断增长的需求。

随便推点

控制对象的特性_控制对象特性-程序员宅基地

文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是：输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后，所引起输出量变化的快慢。（动态参数） ..._控制对象特性

FRP搭建内网穿透(亲测有效)_locyanfrp-程序员宅基地

文章浏览阅读5.7w次，点赞50次，收藏276次。FRP搭建内网穿透1.概述：frp可以通过有公网IP的的服务器将内网的主机暴露给互联网，从而实现通过外网能直接访问到内网主机；frp有服务端和客户端，服务端需要装在有公网ip的服务器上，客户端装在内网主机上。2.简单的图解：3.准备工作：1.一个域名（www.test.xyz）2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp，选择适合的版本下载解压如下：我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp