貪心演算法和窮舉法不同

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規模的問題。

貪心原則：最能符合問題需求的選擇

貪心演算法需要論證
每次貪心選擇的解組合在一起就是最優解 這個結論是否正確