アルゴリズムベース(Java)--欲張りアルゴリズム

前言
前に簡単に8つの経典のソートアルゴリズムを紹介して、この文は貪欲なアルゴリズムを紹介して、そしていくつかのよくある貪欲なアルゴリズムのテーマを紹介します.
1.欲張りアルゴリズムの概念
欲張りアルゴリズムとは,問題を解く際に,常に現在から見れば最良の選択をすることである.すなわち,全体の最適化を考慮せずに,ある意味での局所最適解にすぎない.欲張りアルゴリズムには固定的なアルゴリズムフレームワークがなく、アルゴリズム設計の鍵は欲張り戦略の選択である.欲張りアルゴリズムはすべての問題に対して全体的に最適解を得ることができるのではなく,選択した欲張り戦略は,ある状態以降の過程が以前の状態に影響を及ぼさず,現在の状態にのみ関係する無後効性を備えなければならないことに注意しなければならない.だから、採用した貪欲な戦略に対して、後効性がないかどうかをよく分析しなければならない.
2.基本的な考え方

は、問題を記述するために数学モデルを構築する.

解を求める問題をいくつかのサブ問題に分ける.

は各サブ問題を解き,サブ問題の局所最適解を得た.

サブ問題の解局所最適解を元の解問題の1つの解に合成する.

3.適用される問題
貪欲な戦略が適用される前提は、局所最適化戦略がグローバル最適解を生成することである.すなわち,アルゴリズムが終了すると,局所最適化はグローバル最適化に等しい.
貪欲アルゴリズムでは局所最適解を解く戦略のみでグローバル最適解を達成できるため,問題が貪欲アルゴリズム戦略を採用するのに適しているかどうか,見つかった解が問題の最適解であるかどうかを判断することに注意しなければならない.欲張りアルゴリズムを使用できると判断したら、適切な欲張り戦略を選択しなければならない.
4.実例説明
4.1バックパックの問題
質問:リュックサックがあり、リュックサックの容量は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）               ，        。

一般的に,貪欲アルゴリズムの証明は,問題全体の最適解が貪欲戦略に存在するサブ問題の最適解から得られるに違いないことをめぐっている.
例題の中の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

ダイナミックプランニングでは、3つの最も基本的なリュックサックの問題を学びます.ゼロのリュックサック、一部のリュックサック、完全なリュックサックです.リュックサックの問題は欲張りアルゴリズムを使用できないことが証明されています.
なぜリュックサックの問題を引用して貪欲なアルゴリズムを説明しなければならないのか.
貪欲アルゴリズムの理解を深めるために,問題全体の最適解は必ず貪欲戦略に存在するサブ問題の最適解から得られる.
4.2貨幣のお釣り問題
この問題は私たちの日常生活の中でもっと普遍的になった.貪欲なアルゴリズムの思想では、一歩一歩できるだけ額面の大きい紙幣を使えばいいのは明らかだ.
紙幣の金額を1元、5元、10元、20元、50元、100元と仮定すると、123元はできるだけ少ない紙幣に両替しなければならない.試しに1枚100元、1枚20元、3枚1元に両替しなければなりません.
アルゴリズムの考え方は簡単で、できるだけ最大の面値から下に下がるだけでいいです.

static void splitChange(int money) {
    int[] prices = {100, 50, 20, 10, 5, 1};
    int[] notes = new int[prices.length];
    int change = money;
    if (money > 0) {
        while (change > 0) {
            for (int i = 0; i < prices.length; i++) {
                int count = 0;
                for (int k = 0; change - prices[i] >= 0; k++) {
                    if (change - prices[i] >= 0) {
                        change = change - prices[i];
                        count++;
                    } else break;
                }
                notes[i] = count;
            }
        }
    }
    System.out.println("  ：");
    for (int num = 0; num < prices.length; num++) {
        System.out.print(notes[num] + " " + prices[num] + "   ");
    }
}

4.3マルチマシンスケジューリングの問題
問題説明:n個の独立した作業{1,2,...,n}が設ける、m台の同じ機械で加工処理を行う.ジョブiに要する時間はtiである.約束:いかなる作業もいかなる機械で加工処理することができるが、完成しない前に処理を中断することは許されず、いかなる作業もより小さなサブ作業に分割することはできない.与えられたn個の作業をできるだけ短い時間でm台の機械加工処理で完了させる作業スケジューリングスキームが要求される.マルチマシンスケジューリング問題はNP完全問題であり,これまで完全に有効な解法はなかった.このような問題に対して,貪欲な選択戦略を用いて,比較的良い近似アルゴリズムを設計できる場合がある.
貪欲なアルゴリズムは構想を解く
最長処理時間作業優先の貪欲戦略を採用する:n≦mの場合、機械iの[0,ti]時間区間を作業iに割り当てるだけでよい.n>mの場合、n個のジョブを所望の処理時間に従って大きいものから小さいものに並べ替え、その後、空きプロセッサに順次ジョブを割り当てる.

/**
 * @Description:       
 * @Date: 15:49 2019/8/10
 * @Param: [a, m]
 * @return: int
 */
public static int greedy(int[] a, int m) {
    //int n = a.length - 1;//a    1  ，  n（     ）=a.length-1
    int n = a.length;
    int sum = 0;
    if (n <= m) {
        for (int i = 0; i < n; i++)
            sum += a[i + 1];
        System.out.println("             ");
        return sum;
    }
    List<JobNode> d = new ArrayList<>();//d       
    for (int i = 0; i < n; i++) {//        List ，          
        JobNode jb = new JobNode(i + 1, a[i]);
        d.add(jb);
    }
    Collections.sort(d);//    List    
    LinkedList<MachineNode> h = new LinkedList<>();//h       
    for (int i = 0; i <m; i++) {//        LinkedList 
        MachineNode x = new MachineNode(i+1, 0);//   ，         （          ）  0
        h.add(x);
    }

    for (int i = 0; i < n; i++) {
        Collections.sort(h);
        MachineNode x = h.peek();
        System.out.println("   " + x.id + " " + x.avail + " " + (x.avail + d.get(i).time) + "         " + d.get(i).id);
        x.avail += d.get(i).time;
        sum = x.avail;
    }
    return sum;
}


public static class JobNode implements Comparable {
    int id;//     
    int time;//    

    public JobNode(int id, int time) {
        this.id = id;
        this.time = time;
    }

    @Override
    public int compareTo(Object x) {//         
        int times = ((JobNode) x).time;
        return Integer.compare(times, time);
    }
}

public static class MachineNode implements Comparable {
    int id;//     
    int avail;//       （             ）

    public MachineNode(int id, int avail) {
        this.id = id;
        this.avail = avail;
    }

    @Override
    public int compareTo(Object o) {//    ，LinkedList first    
        int xs = ((MachineNode) o).avail;
        return Integer.compare(avail, xs);
    }
}

4.4【leetcode】630-カリキュラムIII
質問説明:n科目があり、番号は1からnまでです.各授業には対応する時間tと締め切り日dがある.1つの授業を選んだら、t日続けてdの前にこの授業を完成しなければなりません.初日から.n科目を与えて、(t,d)対で表すと、あなたが参加できる最も多くの授業数を見つける必要があります.同時に2つの授業を受けてはいけないことに注意してください.
問題の分析:
欲張り法は、まず配列をdでソートし、配列を巡る過程で現在の日付を維持し、カリキュラムがオプションであれば現在の日付を増やし、オプションでなければ、選択したカリキュラムから最も時間がかかるカリキュラムを見つけ、そのカリキュラムが現在のカリキュラムよりも時間がかかる場合は、交換します.この手順を繰り返します

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        });

        int count = 0, curtime = 0;
        for(int i = 0;i < courses.length;i++){
            //   ，      ，         courses 
            //  ， courses           ，                 ，   
            if(curtime + courses[i][0] <= courses[i][1]){
                courses[count++] = courses[i];
                curtime += courses[i][0];
            }else{
                int max_i = i;
                for(int j = count - 1;j >= 0;j--){
                    if(courses[j][0] > courses[max_i][0])   max_i = j;
                }
                if(courses[max_i][0] > courses[i][0]){
                    curtime += courses[i][0] - courses[max_i][0];
                    courses[max_i] = courses[i];
                }
            }
        }

        return count;
    }
}

4.5テストコード

public class greedyProgramTest {
    public static void main(String[] args) {
        //    
        int money = 123;
        greedyProgram.splitChange(money);

        System.out.println();
        System.out.println("-------");

        //      
        int[] a = {5,4,2,14,16,6,5,3};
        int m = 3;
        System.out.println("    ："+greedyProgram.greedy(a,m));

        System.out.println("-------");

        //   
        int[][] course = {{2,5},{2,19},{1,8},{1,3}};
        System.out.println(Solution.scheduleCourse(course));
    }
}

実行結果:

  ：
1 100   0 50   1 20   0 10   0 5   3 1   
-------
   1 0 16         5
   2 0 14         4
   3 0 6         6
   3 6 11         1
   3 11 16         7
   2 14 18         2
   3 16 19         8
   1 16 18         3
    ：18
-------
   ：4

5.まとめ&参考資料
小結
貪欲アルゴリズムに関する例は多く,これは一つ一つ列挙されず,主に貪欲アルゴリズムの主な思想を理解し,局所最適解によって全体最適解を得る問題である.欲張りアルゴリズムは効率的なアルゴリズムの一つであり,モデルを簡略化できれば欲張りアルゴリズムを利用して問題を解決することができる.
参考資料

Java-欲張りアルゴリズム

「データ構造とアルゴリズム分析Java音声記述」

ゼロから貪欲アルゴリズム

を学ぶ

貪欲アルゴリズム詳細