貪心演算法
基本概念
所謂貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇，也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的區域最優解，
貪心演算法沒有固定的演算法框架，演算法設計的關鍵是貪心策略的選擇，必須注意的是，貪心演算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的程序不會影響以前的狀態，只與當前狀態有關，
所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性，貪心演算法的基本思路
- 建立數學模型來描述問題，
2. 把求解的問題分成若干個子問題，
3. 對每一子問題求解，得到子問題的區域最優解，
4. 把子問題的解區域最優解合成原來解問題的一個解，
貪心演算法的 實作框架
貪心演算法適用的前提是：區域最優策略能導致產生全域最優解
實際上，貪心演算法適用的情況很少，一般，對一個問題分析是否適用于貪心演算法，可以先選擇該問題下的幾個實際資料進行分析，就可做出判斷，
貪心演算法的實作框架
從問題的某一初始解出發； while （能朝給定總目標前進一步） { 利用可行的決策，求出可行解的一個解元素； } 由所有解元素組合成問題的一個可行解；貪心策略的選擇
因為用貪心演算法只能通過解區域最優解的策略來達到全域最優解，因此，一定要注意判斷問題是否適合采用貪心演算法策略，找到的解是否一定是問題的最優解，例題分析
下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解， [背包問題]有一個背包，背包容量是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）每次選取單位重量價值最大的物品，成為解本題的策略， 值得注意的是，貪心演算法并不是完全不可以使用，貪心策略一旦經過證明成立后，它就是一種高效的演算法， 比如，求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法， 貪心演算法還是很常見的演算法之一，這是由于它簡單易行，構造貪心策略不是很困難， 可惜的是，它需要證明后才能真正運用到題目的演算法中， 一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的， 對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下： （1）貪心策略：選取價值最大者，反例： W=30 物品：A B C 重量：28 12 12 價值：30 20 20 根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好， （2）貪心策略：選取重量最小，它的反例與第一種策略的反例差不多， （3）貪心策略：選取單位重量價值最大的物品，反例： W=30 物品： A B C 重量：28 20 10 價值：28 20 10 根據策略，三種物品單位重量價值一樣，程式無法依據現有策略作出判斷，如果選擇A，則答案錯誤，其實該情況是符合貪心策略的，因為該總情況不管先選哪兩個都會把背包塞滿，因為該題物品可以分割成任意大小，所以，就算空下一下，也可以將最后一個物品分割，放進去，它們的單位重量的價值是一樣的，所以，最后背包最后重量相同，重量相同那么價值也相同，）
所以采用第三種策略，代碼如下：
package cn.itcast.recursion;
import java.util.Arrays;
public class GreedyPackage {
private int MAX_WEIGHT = 150;
private int[] weights = new int[]{35, 30, 60, 50, 40, 10, 25};
private int[] values = new int[]{10, 40, 30, 50, 35, 40, 30};
private void packageGreedy(int capacity, int weights[], int[] values) {
int n = weights.length;//物品的數量
double[] r = new double[n];//性價比陣列
int[] index = new int[n];//性價比排序物品的下標
for (int i = 0; i < n; i++) {
r[i] = (double) values[i] / weights[i];
index[i] = i;//默認排序
}
double temp = 0;//對性價比進行排序
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
//降序，對性價比和對應下標進行排序
if (r[i] < r[j]) {
temp = r[i];
r[i] = r[j];
r[j] = temp;
int x = index[i];
index[i] = index[j];
index[j] = x;
}
}
}
//排序好的重量和價值分別存到陣列
int[] w1 = new int[n];
int[] v1 = new int[n];
//排序好的重量和價值分別存到陣列
for (int i = 0; i < n; i++) {
w1[i] = weights[index[i]];
v1[i] = values[index[i]];
}
//用來裝物品的陣列
int[] x = new int[n];
//放入物品的最大價值
int maxValue = https://www.cnblogs.com/xiaozhongfeixiang/p/0;
//放入物品的總重量
int totalweights = 0;
for (int i = 0; i < n; i++) {
//物品重量比包的總容量小，表示還可以裝得下
if (w1[i] < capacity) {
x[i] = 1;//表示該物品被裝了
maxValue += v1[i];
System.out.println(w1[i] + "kg的物品被放進包包,價值：" + v1[i]);
totalweights += w1[i];
capacity = capacity - w1[i];
}
}
System.out.println("總共放入的物品數量：" + Arrays.toString(x));
System.out.println("總共放入的物品總重量" + totalweights);
System.out.println("放入物品的最大價值：" + maxValue);
}
public static void main(String[] args) {
GreedyPackage greedyPackage = new GreedyPackage();
greedyPackage.packageGreedy(greedyPackage.MAX_WEIGHT, greedyPackage.weights, greedyPackage.values);
}
}
分治演算法
定義
將原問題劃分成n個規模較小，并且結構與原問題相似的子問題，遞回地解決這些子問題，然后再合并其結果，就得到原問題的解，
分治策略
“分而治之”，大問題能夠拆成相似的小問題，記住這些小問題需要具有相似性，而后將小問題的每個解合成為大問題的解，所以說大問題如何拆，小問題如何合并才是這個演算法最主要的一個思想，實際上很多演算法如貪心演算法，動態規劃等等都是要求把大問題拆成小問題，而分治演算法的重要一點就是要適用于能夠重新把小問題的解合并為大問題的解，
使用分治演算法的前提條件
- 原問題與分解成的小問題具有相同的模式；
- 原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治演算法跟動態規劃的明顯區別；
- 具有分解終止條件，也就是說，當問題足夠小時，可以直接求解；
- 可以將子問題合并成原問題，而這個合并操作的復雜度不能太高，否則就起不到減小演算法總體復雜度的效果了
每一次遞回都會涉及三個操作
- 分解：將原問題分解成一系列子問題；
- 解決：遞回地求解各個子問題，若子問題足夠小，則直接求解；
- 合并：將子問題的結果合并成原問題；
分治法適用條件
1、該問題的規模縮小到一定程度就可以很容易解決；
2、該問題可以分解為若干個規模較小的相同問題，這里注意是最優子結構性質；
3、利用該問題分解出的子問題的解可以合并為該問題的解；
4、該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共子問題；
對于很多演算法而言，第一條往往是必要的，因為資料量一旦大起來，問題往往復雜度上升的特別快，這里就需要將這個大問題分解為小問題，小問題處理起來更加方便，第二、三條的才是分治思想的核心，因為很多時候我們會采用遞回的方式進行解決，所以在大問題分解為小問題的時候需要保證小問題之間的相同性，單單分解為小問題之后還不能算完成，必須要能夠將小問題的解合并為這個問題的最終解才能算真正用到了分治的思想，最后一條也是最關鍵的，各個子問題之間必須要保證獨立性，即不互相影響，如果相互之間有影響，這時候我們采用的是動態規劃就更加好一點，
例題
其實演算法的思想不用講太多，能夠化為幾句話是最好的，下面就舉幾個例子來看看分治演算法：
例題一：二分查找，給定一個按照升序排好的陣列array，要在這個陣列中找出一個特定的元素x；
當我們遇到一個問題，完全可以在心里問自己下面四個問題：
1、當前問題能不能切分？
答：能切分，因為陣列按照升序來排列，所以當x大于某個元素array[mid]時，x一定在array[mid]的右邊，以此再來切分，每次切一半
2、分解出來的子問題相同嗎？
答：相同，每個子問題的資料集都是父問題的1/2倍，并且每次只比較子問題的中間的資料
3、子問題的解能合并為父問題的解嗎？
答：不需要合并，子問題的解即為父問題的解，
4、子問題之間相互獨立嗎？
答：獨立，子問題只是判斷，不需要和父問題有很強的關聯性（這里可以參考一下動態規劃演算法，就能理解子問題之間怎么判斷是獨立的）
例題二：歸并排序，給定一個無序陣列array[7]={49,38,65,97,76,13,27}，使其變的有序
同樣在自己心里問問4個問題
1、當前問題能切分嗎？
答：能，最簡單的就是兩個數之間的比較，這個陣列可以看成多個兩個數來比較
2、分解出來的子問題是否相同？
答：相同，都是兩個數比較大小，
3、子問題的解能夠合成父問題的解嗎？
答：每兩個有序陣列再按照一定順序合起來就是最終的題解，這里就是有個合并的程序
4、子問題之間相互獨立嗎？
答：獨立，分到最小的時候子問題之間互不影響，
下面是歸并排序代碼：
總結
分治演算法只是一種思想，不是一個具體的套路，只能說在碰見具體問題時我們能夠從這個思路去思考，切分問題？合并問題？子問題之間影響關聯大不大？這些都是具體問題具體考慮，還有很多很多題目是用了分治演算法，也可以多刷刷題
回圈賽日常表：
設有n=2^k個運動員，要進行網球回圈賽，現在要設計一個滿足以下要求的比賽日程表
（1）每個選手必須與其他n-1個選手各賽一場
（2）每個選手一天只能賽一次
（3）回圈賽一共進行n-1天
將比賽日程表設計成n行n列，表中除了第一列，其他n-1列才是我們要的，陣列下標行列都從0開始，第i行j列代表第（i+1）位選手在第j天的對手：
以8個選手為例子，下面是填表的步驟：
①我們先初始化第一行各個數為1~8（2~8為：第1天 — 第7天）；
②因為是遞回，那么要填8x8的左下角和右下角，分別需要知道它的右上角和左上角
③而8x8的盒子它的左上角是一個4x4的盒子，要填4x4的左下角和右下角，也分別需要知道它的右上角和左上角
④現在遞回到4x4的盒子的左上角，是一個2x2的盒子，它不需要遞回了，直接沿對角線填左下角和右下角的數字，也就是上面的圖②
⑤可以看到，經過上面的②③步，我們左上角4x4的盒子，它的·右上角和左上角已經知道了，那就可以沿對角線填它的左下角和右下角了，所以出現了圖④
⑥其他的依次類推
通俗易懂地講，就是如果你想填一個大的，你得先得出它左上角和右上角兩個盒子 ， 再沿對角線分別抄到右下角和左下角， 而為了得出它左上角和右上角，就需要遞回了，
package cn.itcast.recursion;
public class SportsSchedule {
public void scheduleTable(int[][] table, int n) {
if (n == 1) {
table[0][0] = 1;
} else {
/* 填充左上區域矩陣
n值的變化：8 4 2 1
m值的變化：4 2 1 1 */
int m = n / 2;
scheduleTable(table, m);
//填充右上區域矩陣
for (int i = 0; i < m; i++) {
for (int j = m; j < n; j++) {
table[i][j] = table[i][j - m] + m;
}
}
//填充左下區域矩陣
for (int i = m; i < n; i++) {
for (int j = 0; j < m; j++) {
table[i][j] = table[i - m][j] + m;
}
}
//填充右下區域矩陣
for (int i = m; i < n; i++) {
for (int j = m; j < n; j++) {
table[i][j] = table[i - m][j - m];
}
}
}
}
public static void main(String[] args) {
int[][] table = new int[8][8];
int n = 8;
SportsSchedule schedule = new SportsSchedule();
schedule.scheduleTable(table, n);
int c = 0;
//列印二維陣列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(table[i][j] + " ");
c++;//每列印一個數，c++
if (c % n == 0) {//說明列印一行了
System.out.println();//換行
}
}
}
}
}
L型骨牌棋盤覆寫
問題描述
在一個2^k×2^k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格（特殊點），且稱該棋盤為一特殊棋盤，在棋盤覆寫問題中，要用圖示的4種不同形態的L型骨牌覆寫給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆寫，
解題思路
分析：
當k>0時，將2^k×2^k 棋盤分割為4個2^k-1×2^k-1 子棋盤(a)所示，特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格，為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個L型骨牌覆寫這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為4個較小規模的棋盤覆寫問題，遞回地使用這種分割，直至棋盤簡化為棋盤1×1，
實作：
每次都對分割后的四個小方塊進行判斷，判斷特殊方格是否在里面，這里的判斷的方法是每次先記錄下整個大方塊的左上角方格的行列坐標，然后再與特殊方格坐標進行比較，就可以知道特殊方格是否在該塊中，如果特殊方塊在里面，這直接遞回下去求即可，如果不在，這根據分割的四個方塊的不同位置，把右下角、左下角、右上角或者左上角的方格標記為特殊方塊，然后繼續遞回，在遞回函式里，還要有一個變數subSize來記錄邊的方格數，每次對方塊進行劃分時，邊的方格數都會減半，這個變數是為了方便判斷特殊方格的位置，
覆寫步驟如圖：
代碼實作:
package cn.itcast.recursion; public class ChessBoradProblem { private int[][] board;//棋盤 private int specialRow;//特殊點行下標 private int specialCol;//特殊點列下標 private int size;//矩陣大小 private int type = 0;//骨牌型別，1,2,3,4 因為是用數字表示的，所以用int public ChessBoradProblem(int specialRow, int specialCol, int size) { this.specialRow = specialRow; this.specialCol = specialCol; this.size = size; board = new int[size][size]; } /** * @param specialRow 特殊點的行下標 * @param specialCol 特殊點的列下標 * @param leftRow 分割成4個后每個矩陣的左邊的起點行下標 * @param leftCol 分割成4個后每個矩陣的左邊起點列下標 * @param size 矩陣的寬或者高 */ //相對于四個方格中右上的方格，左邊起點的leftRow不一定是0了 private void ChessBoard(int specialRow, int specialCol, int leftRow, int leftCol, int size) { if (size == 1) { return; } int subSize = size / 2; type = type % 4 + 1;//不斷+1，超過4就取模 int n = type; //假設特殊點在左上角，然后行和列都小于一半 if (specialRow < leftRow + subSize && specialCol < leftCol + subSize) { ChessBoard(specialRow, specialCol, leftRow, leftCol, subSize); } else { //不在左上角，左上角矩陣的右下角就是特殊點 board[leftRow + subSize - 1][leftCol + subSize - 1] = n; ChessBoard(leftRow + subSize - 1, leftRow + subSize - 1, leftRow, leftCol, subSize); } //特殊點在右上方，行小于一半，列大于一半 if (specialRow < leftRow + subSize && specialCol >= leftCol + subSize) { ChessBoard(specialRow, specialCol, leftRow, leftCol + subSize, subSize); } else { board[leftRow + subSize - 1][leftCol + subSize] = n; ChessBoard(leftRow + subSize - 1, leftCol + subSize, leftRow, leftCol + subSize, subSize); } //特殊點在左下方 if (specialRow >= leftRow + subSize && specialCol < leftCol + subSize) { ChessBoard(specialRow, specialCol, leftRow + subSize, leftCol, subSize); } else { board[leftRow + subSize][leftCol + subSize - 1] = n; ChessBoard(leftRow + subSize, leftCol + subSize - 1, leftRow + subSize, leftCol, subSize); } //特殊點在右下方 if (specialRow >= leftRow + subSize && specialCol >= leftCol + subSize) { ChessBoard(specialRow, specialCol, leftRow + subSize, leftCol + subSize, subSize); } else { board[leftRow + subSize][leftCol + subSize] = n; ChessBoard(leftRow + subSize, leftCol + subSize, leftRow + subSize, leftCol + subSize, subSize); } } public void printBoard(int specialRow, int specialCol, int size) { ChessBoard(specialRow, specialCol, 0, 0, size); printResult(); } private void printResult() { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { System.out.print(board[i][j] + " ");//注意：print } System.out.println(); } } public static void main(String[] args) { int N = 4;//矩陣大小 //選取特殊點 int specialRow = 0; int specialCol = 1; ChessBoradProblem boradProblem = new ChessBoradProblem(specialRow, specialCol, N); boradProblem.printBoard(specialRow, specialCol, N); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119196.html
標籤：其他
上一篇：遙感！
下一篇：有關南方cass