古典的な貪欲法:時間系列問題とそのグローバル最適性の証明

欲張りアルゴリズムとは,問題を解く際に,常に現在から見れば最良の選択を行うことである.すなわち,全体的に考慮しないで,ある意味での局所最適解にすぎない.欲張りアルゴリズムが実行可能な解を求めると,このアルゴリズムが最適解を見つけたかどうかを決定する.このため、この解が最適であることを証明するか、アルゴリズムが非最適解を生成する反例を説明するかのいずれかである.
問題をより簡単に説明するために、次のテーマはHDUから取った例を分析します.2037:今年の夏休みはAC

Problem Description “     AC？” “  。” “      ？” “     ，  ！” “@#$%^&*%...”     ，     ，        ，    ACMer      ，     。     ，             ，  ，         ，             ，      （            ）、  6+7、    ，      《    》  ，                         ，       ？（             ） Input             ，                n(n<=100)，            ，   n   ，        Ti_s,Ti_e (1<=i<=n)，     i           ，      ，             。n=0      ，    。 Output         ，               ，            。 
Sample Input 12

1 3 

3 4

0 7 

3 8 

15 19

15 20

10 15

8 18 

6 12 

5 10

4 14

2 9

0 
Sample Output 5

問題をよく考察すると(自分で簡単な例を挙げて法則を探す)、アルゴリズムの各段階で、完全に視聴できる番組の中から最も早く終わる番組を選んで見ることが分かった.この貪欲アルゴリズムは,できるだけ多くの完全な番組を見ることができるという意味で最適なアルゴリズムであることを実証する.このアルゴリズムの最適性を実証するために,変数nに数学的帰納法を適用し,ここでnはアルゴリズムにおける番組数である.P(n)を命題とする:欲張りアルゴリズムがn個の番組を手配すれば、より多くの番組を手配することはできない.
基本手順:上記貪欲アルゴリズムを適用して1つの番組(Ti_s,Ti_e(1<=i<=n)のみを手配し、それぞれi番目の番組の開始時間と終了時間を表す)とし、これは他のすべての番組の開始時間が手配した1つの番組の終了時間T 1_であることを示すeより前、そして終了時間Ti_e <= T1_e.これはまた何を説明しましたか?いずれの番組も放送時間が重なっていることを示しているので、アルゴリズムに貪欲に1つの番組を手配すれば、より多くの番組を手配することはできない.
帰納ステップ:帰納ステップはP(k)が真であり、kは正の整数である.すなわち,欲張りアルゴリズムがk個の番組を手配すれば,より多くの番組を手配することは不可能である.次に,kが成立した条件下で,命題対k+1が依然として成立していることを証明する必要がある.言い換えれば、欲張りアルゴリズムがk+1番組を手配したと仮定すると、より多くの番組を手配できないことを証明する必要があります.私たちはできるだけ多くの番組を手配することを出発点として、最初の番組は一番早く終わるべきです.すべての番組の開始と終了時間が与えられているので、できるだけ多くの番組を手配するには、最初の番組を手配した後、残りの時間を最大化する必要があります.つまり、最初の番組は多くの番組の中で最も早く終わったもので、番組の手配数が最大化されることを保証します.残りの問題はやりやすくて、残りの時間はkつの番組を手配してすでに私たちのまとめの仮定P(k)が保証しました.
OK,我々はすでに基礎ステップと帰納ステップを完成し,数学帰納法の原理に基づいて,すべての正の整数nに対して,P(n)が真であることが分かった.これで最適性の証明が完成した.
この問題に対して貪欲法を用いて最適解を見つけることを保証できることを確定した後、私たちは着実にプログラムを書くことができて実現しました.

#include<stdio.h> #include<string.h>

void bubble_sort(int a[][2], int); //             

int main(void) { int n, i, count, first, second; int a[110][2]; while(scanf("%d", &n) && n) // n==0，    

 { i = 0; memset(a, 0, sizeof(a)); while(n--) { scanf("%d%d", &a[i][0], &a[i][1]); i++; } bubble_sort(a, i); // i       //     ，        ，       ，          <=      ，       ，      ，              。

 count = 1; first = 0; second = 1; while(1) { if(a[first][1] <= a[second][0]) { count++; first = second; } second++; if(second >= i) break; } printf("%d
", count);

 } return 0; } void bubble_sort(int a[][2], int n) { int temp; for(int outer = n-1; outer > 0; outer--) for(int inter = 0; inter < outer; inter++) { if(a[inter][1] > a[inter+1][1]) { temp = a[inter][1]; a[inter][1] = a[inter+1][1]; a[inter+1][1] = temp; temp = a[inter][0]; a[inter][0] = a[inter+1][0]; a[inter+1][0] = temp; } } }

 

All Rights Reserved.

Author：  :)

Copyright © xp_jiang. 

       ：http://www.cnblogs.com/xpjiang/p/4413903.html
  .