导航:首页 > 源码编译 > 贪心算法和穷举法不同

贪心算法和穷举法不同

发布时间:2023-03-26 20:34:37

A. PASCAL算法知识题~~高分~紧急~

6.1 穷举策略的概念

所谓枚举法,指的是从可能的解的集合中一一枚举各元素, 用题目给定的检验条件判定哪些是无用的,哪些是有用的。能使命题成立,即为其解。

有些问题可以用循环语句和条件语句直接求解,有些问题用循环求解时循环次数太多,无法编写程序,怎么办?下面是用“千军万马过独木桥,适者存”的方式实现穷举策略的。

6.2 典型例题与习题

例1.将2n个0和2n个1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法,用上面的方法产生出来的2n+1个二进制数都不相同。

例如,当n=2时,即22个0和22个1排成如下一圈:

比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101,011,111,110,100共8个二进制数且都不相同。

程序说明:

以n=4为例,即有16个0,16个1,数组a用以记录32个0,1的排法,数组b统计二进制数出现的可能性。

程序清单

PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27
WHILE A[J]=1 DO J:=J-1;
( A[J]:=1 )
FOR I:=J+1 TO 27 DO ( A[i]:=0 )
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
( S:=0)
FOR K:=I TO I+4 DO S:=S*2+A[k];
( B[S]:=1 )
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF ( S=32 ) THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.

例2:在A、B两个城市之间设有N个路站(如下图中的S1,且N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20,且每条路段上的距离均为一个整数)。
A,B的一条通路是指:从A出发,可经过任一路段到达S1,再从S1出发经过任一路段,…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。
例如:下图所示是当N=1时的情况:

从A到B的通路条数为6,但因其中通路5+5=4+6,所以满足条件的不同距离的通路条数为5。

算法说明:本题采用穷举算法。
数据结构:N:记录A,B间路站的个数
数组D[I,0]记录第I-1个到第I路站间路段的个数
D[I,1],D[I,2],…记录每个路段距离
数组G记录可取到的距离
程序清单:
program CHU7_6;
var i,j,n,s:integer;
b:array[0..100] of integer;
d:array[0..100,0..20] of integer;
g:array[0..1000] of 0..1;
begin
readln(n);
for i:=1 to n+1 do
begin
readln(d[i,0]);
for j:=1 to d[i,0] do read(d[i,j]);
end;
d[0,0]:=1;
for i:=1 to n+1 do b[i]:=1;
b[0]:=0;
for i:=1 to 1000 do g[i]:=0;
while b[0]<>1 do
begin
s:=0;
for i:=1 to n+1 do
s:= s+d[i,b[i]];
g[s]:=1;j:=n+1;
while b[j]=d[j,0] do j:=j-1;
b[j]:=b[j]+1;
for i:=j+1 to n+1 do b[i]:=1;
end;
s:=0;
for i:=1 to 1000 do
s:=s+g[i];
writeln(s);readln;
end.

2.1 递归的概念

1.概念

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

如:

procere a;

begin

.

.

.

a;

.

.

.

end;

这种方式是直接调用.

又如:

procere b; procere c;

begin begin

. .

. .

. .

c; b;

. .

. .

. .

end; end;

这种方式是间接调用.

例1计算n!可用递归公式如下:

1 当 n=0 时

fac(n)={n*fac(n-1) 当n>0时

可编写程序如下:

program fac2;

var

n:integer;

function fac(n:integer):real;

begin

if n=0 then fac:=1 else fac:=n*fac(n-1)

end;

begin

write('n=');readln(n);

writeln('fac(',n,')=',fac(n):6:0);

end.

例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.

设n阶台阶的走法数为f(n)

显然有

1 n=1

f(n)={2 n=2

f(n-1)+f(n-2) n>2

编程序如下:

program louti;

var n:integer;

function f(x:integer):integer;

begin

if x=1 then f:=1 else

if x=2 then f:=2 else f:=f(x-1)+f(x-2);

end;

begin

write('n=');read(n);

writeln('f(',n,')=',f(n))

end.

2.2 如何设计递归算法
1.确定递归公式

2.确定边界(终了)条件

练习:

用递归的方法完成下列问题

1.求数组中的最大数

2.1+2+3+...+n

3.求n个整数的积

4.求n个整数的平均值

5.求n个自然数的最大公约数与最小公倍数

6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题

例3 梵塔问题

如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上

不能出现大盘压小盘.找出移动次数最小的方案.

程序如下:

program fanta;

var

n:integer;

procere move(n,a,b,c:integer);

begin

if n=1 then writeln(a,'--->',c)

else begin

move(n-1,a,c,b);

writeln(a,'--->',c);

move(n-1,b,a,c);

end;

end;

begin

write('Enter n=');

read(n);

move(n,1,2,3);

end.

例4 快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

程序如下:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
3.1 回溯的设计

1.用栈保存好前进中的某些状态.

2.制定好约束条件

例1由键盘上输入任意n个符号;输出它的全排列.

program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.

例2.n个皇后问题:

program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;

end.

回溯算法的公式如下:

3.2 回溯算法的递归实现

由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。

上述例1的递归方法实现如下:

program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.

例2:n皇后问题的递归算法如下:

程序1:

program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.

程序2:

说明:当n=8 时有30条对角线分别用了l和r数组控制,

用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:

program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
7.1 贪心策略的定义

贪心策略是:指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

其实,从“贪心策略”一词我们便可以看出,贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例1:在n行m列的正整数矩阵中,要求从每一行中选一个数,使得选出的n个数的和最大。

本题可用贪心策略:选n次,每一次选相应行中的最大值即可。

例2:在一个N×M的方格阵中,每一格子赋予一个数(即为权)。规定每次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。

本题用贪心策略不能得到最优解,我们以2×4的矩阵为例。 3 4 6
1 2 10

若按贪心策略求解,所得路径为:1,3,4,6;

若按动态规划法求解,所得路径为:1,2,10,6。

例3:设定有n台处理机p1,p2,......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断,作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?

本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7

用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。

总之:
1. 不能保证求得的最后解是最佳的;
2. 只能用来求某些最大或最小解问题;
3. 能确定某些问题的可行解的范围,特别是给搜索算法提供了依据。

7. 2 贪心策略的特点
贪心算法有什么样的特点呢?我认为,适用于贪心算法解决的问题应具有以下2个特点:

1、贪心选择性质:

所谓贪心选择性质是指应用同一规则f,将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的选择。从全局来看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质,读者可在后文给出的贪心策略状态空间图中得到深刻地体会。

2、局部最优解:

我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解,但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解,但贪心策略比动态规划时间效率更高站用内存更少,编写程序更简单。

7.3 典型例题与习题

例4:背包问题:

有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品
A
B
C
D
E
F
G

重量
35
30
60
50
40
10
25

价值
10
40
30
50
35
40
30

分析:

目标函数: ∑pi最大
约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)

(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
(2)每次挑选所占空间最小的物品装入是否能得到最优解?
(3)每次选取单位容量价值最大的物品,成为解本题的策略。

程序如下:

program beibao;

const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;

procere init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;

procere make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;

begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.

例5:旅行家的预算问题:

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市,给定两个城市间的距离d1,汽车油箱的容量是c,每升汽油能行驶的距离d2,出发时每升汽油的价格是p,沿途加油站数为n(可为0),油站i离出发点的距离是di,每升汽油的价格是pi。

计算结果四舍五入保留小数点后两位,若无法到达目的地输出“No answer"

若输入:

d1=275.6 c=11.9 d2=27.4 p=8 n=2

d[1]=102 p[1]=2.9

d[2]=220 p[2]=2.2

output

26.95

本问题的贪心策略是:找下一个较便宜的油站,根据距离确定加满、不加、加到刚好到该站。

程序如下:

program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procere buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procere solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.

例6:n个部件,每个部件必须经过先A后B两道工序。

以知部件i在A,B 机器上的时间分别为ai,bi。如何安排加工顺序,总加工时间最短?

输入:

5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9

输出:

34

1 5 4 2 3

本问题的贪心策略是A机器上加工短的应优先,B机器上加工短的应靠后。

程序如下:

program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procere init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procere sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procere playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procere calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.

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

对于,大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题,首先要来聊聊他们的联系:1、都是一种推导算法;2、将它们分解为子问题求解,它们都需要有最优子结构。这两个特征师门的联系。

拓展资料:

贪婪算法是指在解决问题时,它总是在当前做出最佳选择。也就是说,在不考虑全局优化的情况下,该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。

动态规划是运筹学的一个分支,是解决决策过程优化的过程。20世纪50年代初,美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时,提出了着名的最优化原理,建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用,在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显着的成果。

C. 算法与程序有何区别和联系

联系:程序是计算机指令的有序集合,是算法用某种程序设计语言的表述,是算法在计算机上的具体实现。

区别:

一、形式不同

1、算法:算法在描述上一般使用半角式化的语言。

2、程序:程序是用形式化的计算机语言描述的。

二、性质不同

1、算法:算法是解决问题的步骤。

2、程序:程序是算法的代码实现。

三、特点不同

1、算法:算法要依靠程序来完成功能。

2、程序:程序需要算法作为灵魂。

D. 程序和算法的区别是什么

一、算法和程序的区别是:

1、在语言描述上不同:程序必须是用规定的程序设计语言来写,而算法很随意。

2、在执行时间上不同:算法所描述的步骤一定是有限的,而程序可以无限地执行下去。

3、两者定义不同:算法是对特定问题求解步骤的描述,它是有限序列指令。程序是实现预期目的而进行操作的一系列语句和指令。

(4)贪心算法和穷举法不同扩展阅读:

一、程序的运行

使计算机程序得以运行,计算机需要加载代码,同时也要加载数据。从计算机的底层来说,这是由高级语言(例如Java,C/C++,C#等)代码转译成机器语言而被CPU所理解,进行加载。

如果您在一个符合大多数的计算机上,操作系统例如Windows、Linux等,加载并执行很多的程序,在这种情况下,每一个程序是一个单独的映射,并不是计算机上的所有可执行程序。

为了得到某种结果而可以由计算机等具有信息处理能力的装置执行的代码化指令序列,或者可以被自动转换成代码化指令序列的符号化指令序列或者符号化语句序列。同一计算机程序的源程序和目标程序为同一作品。

二、算法:包括递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法等。

大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。

参考资料来源:网络-程序

参考资料来源:网络-算法

E. 简述贪心,递归,动态规划,及分治算法之间的区别和联系

联系:都是问题求解之时的一种算法。

区别:

一、作用不同

1、贪心算法:把子问题的解局部最优解合成原来解问题的一个解。

2、递归算法:问题解法按递归算法实现。如Hanoi问题;数据的结构形式是按递归定义的。如二叉树、广义表等。

3、动态规划:动态规划算法通常用于求解具有某种最优性质的问题。

4、分治算法:可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。

二、方法不同

1、贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。

2、递归算法:通过重复将问题分解为同类的子问题而解决问题。

3、动态规划:将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。

4、分治算法:将一个规模为N的问题分解为K个规模较小的子问题。

三、特点不同

1、贪心算法:根据题意选取一种量度标准。

2、递归算法:递归就是在过程或函数里调用自身。

3、动态规划:虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。

4、分治算法:原问题可以分解为多个子问题;原问题在分解过程中,递归地求解子问题;在求解并得到各个子问题的解后。

F. 算法的方法

程序调用自身的编程技巧称为递归(recursion)。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
用贪心法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法,其核心是根据题意选取一种量度标准,然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量,如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下,要选出最优量度标准并不是一件容易的事,但对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征:
(1) 该问题的规模缩小到一定的程度就可以容易地解决;
(2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3) 利用该问题分解出的子问题的解可以合并为该问题的解;
(4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。
动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。 分枝界限法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支,这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
与贪心算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
其基本思想是,在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。 若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

G. 动态规划与贪心算法

很奇怪,动态规划和贪心算法也有很多相似之处:
相同点:
0,两者都用于求解最优化问题
1,两者都将待求解的问题分解成若干子问题
2,两者都需要确定最优子结构,才能决定是否可以使用该方法
3,两者都需要构造递归式

最优子结构:一个问题的最优解包含其子问题的最优解

不同点:
1,动态规划是自底向上计算,类似于将问题的规模从1开始,计算到n,其中i的求解依赖于i-1的结果;贪心算法则是自顶向下计算,选择当前一个最优解,然后再看剩余问题的最优解,一路剥削下去

2,动态规划比贪心算法更加细致精确,贪心算法有时候求不出最优解

贪心算法:面对规模为n的问题,每次选择当前情况的一个最优解,然后在看剩余的n-1规模的问题。

贪心原则:最能符合问题需求的选择

贪心算法需要论证
每次贪心选择的解组合在一起就是最优解 这个结论是否正确

阅读全文

与贪心算法和穷举法不同相关的资料

热点内容
xzforandroid 浏览:575
程序员那么可爱歌曲完整版 浏览:904
为什么购买pdf 浏览:43
操作系统代码编译 浏览:483
程序员东北大学 浏览:426
编译忽略空字符 浏览:117
多店铺阿里云服务器教程 浏览:378
单片机求初值 浏览:420
安卓机如何在电脑备份图片 浏览:925
ca证书加密机价格 浏览:798
天干地支年份算法 浏览:796
程序员打造的视频 浏览:7
java和php通信 浏览:680
为什么黑程序员 浏览:163
程序员男生 浏览:456
戴尔文件夹内文件怎么置顶 浏览:582
云服务器6m网速 浏览:722
vivo手机中国联通服务器地址 浏览:862
工程总控编译失败 浏览:707
燕赵红枫app如何下载 浏览:867