贪心算法的例题分析？贪心算法马的遍历时间复杂度

本文目录

• 贪心算法的例题分析
• 贪心算法马的遍历时间复杂度
• pascal贪心算法是什么啊
• 请用贪心算法设计一个算法,告诉探险家应该在何处充水,并使得充水次数最少
• 贪心算法的证明方法
• 求一个算法(贪心算法)
• 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi《=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c》 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #define N 8void dfs(int x,int y,int count){    int i,tx,ty;    if(count》N*N)    {        output_solution();//输出一个解        return;    }    for(i=0; i《8; i++)    {        tx=hn[i].x;//hn保存八个方位子结点        ty=hn[i].y;        s[tx][ty]=count;        dfs(tx,ty,count+1);//递归调用        s[tx][ty]=0;    }}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcedureFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x》10）or(y》10）or(x1》10）or(y1》10）Thenwriteln(’Error’){判断是否越界}ElseFind(x,y);Writeln(’Total:’,total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

贪心算法马的遍历时间复杂度

【问题描述】 马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 【初步设计】 首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下： 1、输入初始位置坐标x,y； 2、步骤c: 如果c》64输出一个解，返回上一步骤c-- (x,y)←c 计算(x,y)的八个方位的子结点，选出那此可行的子结点 循环遍历所有可行子结点，步骤c++重复2 显然（2）是一个递归调用的过程，大致如下： voiddfs(intx,inty,intcount) { inti,tx,ty; if(count》N*N) { output_solution();//输入一个解 return; } for(I=0;i《8;++i) { tx=hn[i].x;//hn保存八个方位子结点 ty=hn[i].y; s[tx][ty]=count; dfs(tx,ty,count+1);//递归调用 s[tx][ty]=0; } } 这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。 怎么才能快速地得到部分解呢？ 【贪心算法】 其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发示算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。 在前面的算法基础之上，增添一些程序加以实现： 函数1：计算结点出口多少 intways_out(intx,inty) { inti,count=0,tx,ty; if(x《0||y《0||x》=N||y》=N||s[x][y]》0) return-1;//-1表示该结点非法或者已经跳过了 for(i=0;i《8;++i) { tx=x+dx[i]; ty=y+dy[i]; if(tx《0||ty《0||tx》=N||ty》=N) continue; if(s[tx][ty]==0) ++count; } returncount; } 函数2：按结点出口进行排序 voidsortnode(h_node*hn,intn)//采用简单排序法，因为子结点数最多只有8 { inti,j,t; h_nodetemp; for(i=0;i《n;++i) { for(t=i,j=i+1;j《n;++j) if(hn[j].waysout《hn[t].waysout) t=j; if(t》i) { temp=hn[i]; hn[i]=hn[t]; hn[t]=temp; } } } 函数3：修改后的搜索函数 voiddfs(intx,inty,intcount) { inti,tx,ty; h_nodehn; if(count》N*N) { output_solution(); return; } for(i=0;i《8;++i)//求子结点和出口 { hn[i].x=tx=x+dx[i]; hn[i].y=ty=y+dy[i]; hn[i].waysout=ways_out(tx,ty); } sortnode(hn,8); for(i=0;hn[i].waysout《0;++i);//不考虑无用结点 for(;i《8;++i) { tx=hn[i].x; ty=hn[i].y; s[tx][ty]=count; dfs(tx,ty,count+1); s[tx][ty]=0; } } 函数4：主调函数 voidmain() { inti,j,x,y; for(i=0;i《N;++i)//初始化 for(j=0;j《N;++j) s[i][j]=0; printf(“HorsejumpwhileN=%d\nInputthepositiontostart:“,N); scanf(“%d%d“,&x,&y);//输入初始位置 while(x《0||y《0||x》=N||y》=N) { printf(“Error!x,yshouldbein0~%d“,N-1); scanf(“%d%d“,&x,&y); } s[x][y]=1; dfs(x,y,2);//开始搜索 } QQ:547758555 有问题的话QQ上说

pascal贪心算法是什么啊

贪心算法
1．概念
贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以
尽可能快地求得更好的解。当达到某算法中的某一步不能再继续
前进时，算法停止。这时就得到了问题的一个解，但不能保证求
得的最后解是最优的。在改进算法中，贪心算法演化为爬山法。
2．特点及使用范围
贪心算法的优点在于时间复杂度极底。贪心算法与其他最优化算
法的区别在于：它具有不可后撤性，可以有后效性，一般情况下
不满足最优化原理。贪心算法的特点就决定了它的适用范围，他
一般不适用于解决可行性问题，仅适用于较容易得到可行解的最
优性问题。这里较容易得到可行解的概念是：当前的策略选择后，
不会或极少使后面出现无解的情况。另外，对于近年来出现的交
互性题目，贪心算法是一个较好的选择。这是因为，在题目中，
一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知
道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后
效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提
供较优的初始界值。

请用贪心算法设计一个算法,告诉探险家应该在何处充水,并使得充水次数最少

首先,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:
判断当前格子右、下两个相邻的格子是否有水，情形如下：
1）如果一个有一个没有，则往有水的格子走
2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：
让探险家假设地各往两个方向走一步，然后对当前格子作判断情形如下：
A)一个格子继续走能到水，另一个不能，则上一步往该格子走
B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是N*N个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有水时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。
时间复杂度上来算的话，应该是O（nLogn）

贪心算法的证明方法

贪心算法的基本思路如下：
　　1.建立数学模型来描述问题。
　　2.把求解的问题分成若干个子问题。
　　3.对每一子问题求解，得到子问题的局部最优解。
　　4.把子问题的解局部最优解合成原来解问题的一个解。
----------------------------------------------
其实归纳起来也就一个类。其他的都是分支

求一个算法(贪心算法)

首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:
判断当前格子右、下两个相邻的格子是否有金块，情形如下：
1）如果一个有一个没有，则往有金块的格子走
2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：
让机器人假设地各往两个方向走一步，然后对当前格子作判断情形如下：
A)一个格子继续走能拾到金块，另一个不能，则上一步往该格子走
B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是N*N个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有金块时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。
时间复杂度上来算的话，应该是O（nLogn）

大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

《算法分析与设计》是一门理论与应用并重的专业课程。本课程以算法设计策略为知识单元，系统介绍计算机算法的设计方法和分析技巧。课程主要内容包括:第1章，算法概述；第二章，递归和分治策略；第三章，动态规划；第四章，贪婪算法；第五章，回溯法；第六章，分枝定界法。通过介绍经典实用的算法，使学生掌握算法设计的基本方法。结合案例分析，让学生深入了解算法设计的技巧和分析算法的能力。