貪心算法具有2個(gè)性質(zhì)：

1、貪心選擇性質(zhì)：只在當(dāng)前狀態(tài)下做最優(yōu)選擇，即局部最優(yōu)選擇，再自頂向下，去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)子問題。每做一次選擇，問題就轉(zhuǎn)化為規(guī)模更小的子問題。對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步做出的選擇最終導(dǎo)致問題的整體最優(yōu)解。

2、最優(yōu)子結(jié)構(gòu)性質(zhì)：問題的最優(yōu)解包含子問題的最優(yōu)解。

?

貪心算法的幾個(gè)應(yīng)用：

哈夫曼編碼：二叉樹&最小優(yōu)先級隊(duì)列

dijktra：原始集合、選中節(jié)點(diǎn)集合、dist

最小生成樹：prim：原始集合、選中幾點(diǎn)集合、closest、lowcost

最小生成樹：kruskul：并查集&最小優(yōu)先級隊(duì)列

?

具體代碼：?

dijktra：

設(shè)鄰接矩陣：a[][]，有n個(gè)節(jié)點(diǎn)。

1.初始化：dist[i] = a[v][i]，原始集合中只有v。

2.取dist的最小值，加入原始集合中，更新其他dist，更新n-1次

具體代碼如下：

/*

5

0 10 10000 30 100

10000 0 50 10000 10000

10000 10000 0 10000 10

10000 10000 20 0 60

10000 10000 10000 10000 0

?

1

*/

?

#include<stdio.h>

#include<stdlib.h>

?

#define NUM 10

#define MAX_VALUE 10000

?

int dist[NUM];

int s[NUM];

int pre[NUM];

?

void? dijkstra(int v,int a[NUM][NUM], int n){

????? //初始化

????? int i=1,j=1;

????? for(i=1; i<=n; i++){

?????????? dist[i] = a[v][i];

?????????? s[i] = false;

?????????? if(a[v][i] == MAX_VALUE){

???????????????? pre[i] = 0;

?????????? }else{

???????????????? pre[i] = v;

?????????? }

????? }????

?????

????? s[v] = true;

????? dist[v] = 0;

?????

????? //更新n-1次

????? int min = 0,tmp=v;

????? for(i=1; i<n; i++){

??????????? //找最小的dist

??????????? min = MAX_VALUE;

??????????? for(j=1; j<=n; j++){

???????????????????? if(!s[j] && min>dist[j]){

????????????????????????????? min = dist[j];

????????????????????????????? tmp = j;

???????????????????? }

??????????? }

??????????? s[tmp] = true;?? //tmp的初始值是v，不能為0或者隨意

?????

??????????? //用最小的dist更新已有的dist

??????????? for(j=1; j<=n; j++){

???????????????????? if(!s[j] && a[tmp][j] < MAX_VALUE && (dist[tmp]+a[tmp][j] < dist[j])){

????????????????????????????? dist[j] = dist[tmp]+a[tmp][j];

????????????????????????????? pre[j] = tmp;

???????????????????? }

??????????? }

????? }

}

?

int main(){

??? int i=1,j=1,v,n,a[NUM][NUM];

???

??? //輸入鄰接矩陣

??? scanf("%d",&n);

??? for(i=1; i<=n; i++){

?????? for(j=1; j<=n; j++){

?????????? scanf("%d",&a[i][j]);

?????? }

??? }

???

??? //輸入起始節(jié)點(diǎn)

??? scanf("%d",&v);

???

??? //計(jì)算dijkstra

??? dijkstra(v,a,n);

???

??? //打印源點(diǎn)到各點(diǎn)的最短距離

??? int tmp = 0;

??? for(i=1; i<=n; i++){

?????????? printf("從%d到%d的距離是%d\n",v,i,dist[i]);

?????????? tmp = i;

?????????? printf("從%d到%d的最短路經(jīng)過:");

?????????? while(pre[tmp]>0 && pre[tmp] != v){

?????????????? printf("%d ",pre[tmp]);

?????????????? tmp = pre[tmp];

?????????? }

?????????? printf("%d\n",v);

??? }

?

??? system("pause");

??? return 0;

}

?

時(shí)間復(fù)雜度分析：使用鄰接矩陣，o(n*n)

?

最小生成樹：prim

/*
6
0 6 1 5 10000 10000
6 0 5 10000 3 10000
1 5 0 5 6 1
5 10000 5 0 10000 2
10000 3 6 10000 0 6
10000 10000 1 2 6 0

*/

#include<stdio.h>
#include<stdlib.h>

#define NUM 10
#define MAX_VALUE 10000
?
int closest[NUM];? //closest[j]記錄j和S中的鄰接節(jié)點(diǎn)中距離最近的節(jié)點(diǎn)?
int lowcost[NUM];? //lowcost[j]記錄j和S中最近鄰接點(diǎn)的距離?
int s[NUM];??????? //s[j] = true，標(biāo)記j在S中

int prim(int a[NUM][NUM],int n){
??? //初始化
??? int i,j,sum=0;
??? for(i=1; i<=n; i++){
???????????? closest[i] = 1;
???????????? lowcost[i] = a[i][1];
???????????? s[i] = false;
??? }
??? s[1] = true;

??? for(j=1; j<n; j++){
??????? //尋找離S中節(jié)點(diǎn)最近的節(jié)點(diǎn)及距離
??????? int min = MAX_VALUE,v=1;
??????? for(i=1; i<=n; i++){
???????????? if(!s[i] && min > lowcost[i]){
????????????????????? min = lowcost[i];
????????????????????? v = i;
???????????? }
??????? }
??????? s[v] = true;
??????? sum += lowcost[v];
????
??????? //每添加一個(gè)新的節(jié)點(diǎn)到S，比較節(jié)點(diǎn)i和S中以前節(jié)點(diǎn)的最短距離 和 i和新增節(jié)點(diǎn)的最短距離，更新closest和c
??????? for(i=1; i<=n; i++){
???????????? if(!s[i] && a[i][v] < lowcost[i]){
????????????????????? lowcost[i] = a[i][v];
???????????? }
??????? }????????????
??? }?????
????
??? return sum;???????????????????
????
}

int main(){
??? int i=1,j=1,n,a[NUM][NUM];
????
??? //輸入鄰接矩陣?
??? scanf("%d",&n);
??? for(i=1; i<=n; i++){
?????? for(j=1; j<=n; j++){
?????????? scanf("%d",&a[i][j]);
?????? }
??? }
????
??? printf("%d",prim(a,n));
????
??? system("pause");
??? return 0;
}?

時(shí)間復(fù)雜度是：o(n*n)。

說明：最小生成樹prim和dijkstra相似，dijkstra保存了各點(diǎn)和源點(diǎn)的最近距離(dist)，prim保存了各點(diǎn)和S中節(jié)點(diǎn)的最近鄰接點(diǎn)及和最近鄰接點(diǎn)的距離(closest, lowcost)。程序的書寫過程相似，先初始化，再找最小的距離，再更新數(shù)組。

總結(jié)

以上是生活随笔為你收集整理的贪心算法的几个应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。