貪心演算法作業調度
① java代碼，多機調度問題，怎麼解釋
多機調度問題的Java實現（貪心演算法）
具體問題描述以及C/C++實現參見網址
[java]viewplainprint?
importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.LinkedList;
importjava.util.List;
/**
*多機調度問題--貪心演算法
*@authorLican
*
*/
publicclassJobMachine{
{
intid;//作業的標號
inttime;//作業時間
publicJobNode(intid,inttime){
this.id=id;
this.time=time;
}
@Override
publicintcompareTo(Objectx){//按時間從大到小排列
inttimes=((JobNode)x).time;
if(time>times)return-1;
if(time==times)return0;
return1;
}
}
{
intid;//機器的標號
intavail;//機器空閑的時間（即機器做完某一項工作的時間）
publicMachineNode(intid,intavail){
this.id=id;
this.avail=avail;
}
@Override
publicintcompareTo(Objecto){//升序排序，LinkedList的first為最小的
intxs=((MachineNode)o).avail;
if(avail<xs)return-1;
if(avail==xs)return0;
return1;
}
}
publicstaticintgreedy(int[]a,intm){
intn=a.length-1;//a的下標從1開始，所以n（作業的數目）=a.length-1
intsum=0;
if(n<=m){
for(inti=0;i<n;i++)
sum+=a[i+1];
System.out.println("為每個作業分別分配一台機器");
returnsum;
}
List<JobNode>d=newArrayList<JobNode>();//d保存所有的作業
for(inti=0;i<n;i++){//將所有的作業存入List中，每一項包含標號和時間
JobNodejb=newJobNode(i+1,a[i+1]);
d.add(jb);
}
Collections.sort(d);//對作業的List進行排序
LinkedList<MachineNode>h=newLinkedList<MachineNode>();//h保存所有的機器
for(inti=1;i<=m;i++){//將所有的機器存入LinkedList中
MachineNodex=newMachineNode(i,0);//初始時，每台機器的空閑時間（完成上一個作業的時間）都為0
h.add(x);
}
inttest=h.size();
for(inti=0;i<n;i++){
Collections.sort(h);
MachineNodex=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;
}
returnsum;
}
publicstaticvoidmain(String[]args){
int[]a={0,2,14,4,16,6,5,3};
intm=3;
intsum=greedy(a,m);
System.out.println("總時間為："+sum);
}
}
/**
運行結果：
將機器1從0到16的時間段分配給作業4
將機器2從0到14的時間段分配給作業2
將機器3從0到6的時間段分配給作業5
將機器3從6到11的時間段分配給作業6
將機器3從11到15的時間段分配給作業3
將機器2從14到17的時間段分配給作業7
將機器3從15到17的時間段分配給作業1
總時間為：17
*/
② 分治、貪心五大演算法
1、分治
分治（即分而治喊孫之），把一個復雜的問題分成多鄭激鏈個相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
適用場景：二分搜索、歸並排序、快速排序、大整數乘法、第K小元素、最近點對、快速傅里葉變換等。
2、動態規劃
動態規劃法也是把問題一層一層地分解為規模逐漸減小的同類型的子問題。動態規劃通常用來求最優化問題。此類問題可以有很多可行解，我們求出的是一個最優解，可能存在多個最優解。（最優子結構、公共子問題）
與分治法的區別是：分治的子問題是相互獨立的，動態規劃最好解決有公共子問題的，子問題相關性很大。
使用場景：矩陣連乘、鋼條切割、最長公共子序列、最優二叉搜索樹、流水作業調度、0/1背包問題等。
維特比演算法是動態規劃在HMM中的應用，維特比演算法用於解決HMM的預測或者叫解碼問題。
viterbi有最優解是因為HMM每一步是條件獨立的！既然後面的概率和前面的沒關系，那前面選最大的概率就行了。
而beam search時後面的概率依賴於前面所有的詞，相當於n-gram是滿的，viterbi的n-gram是2
背包問題：
https://blog.csdn.net/wind__chaser/article/details/89457771
https://blog.csdn.net/qq_38410730/article/details/81667885
3、貪心
通過局部最優選擇達鉛吵到全局最優選擇。貪心演算法不一定總產生最優解，貪心演算法是否產生優化解，需嚴格證明貪心演算法產生最優解的條件：（最優子結構、貪心選擇性）
貪心選擇性：當一個問題的全局最優解可以通過局部最優解得到，稱這個問題具有貪心選擇性。
適用場景：活動選擇問題、哈夫曼編碼問題、最小生成樹問題、單源最短路徑問題等。
貪心演算法：softmax之後取最大概率。與之對應的是，Beam Search演算法
http://www.360doc.com/content/18/0618/09/17563728_763230413.shtml
https://blog.csdn.net/qq_16234613/article/details/83012046
https://www.hu.com/question/54356960
分治和動態規劃的區別：
動態規劃也是一種分治思想（比如其狀態轉移方程就是一種分治），但與分治演算法不同的是，分治演算法是把原問題分解為若干個子問題，
自頂向下求解子問題，合並子問題的解，從而得到原問題的解。動態規劃也是把原始問題分解為若干個子問題，然後自底向上，
先求解最小的子問題，把結果存在表格中，在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重復計算，從而提高演算法效率。
動態規劃和分治法有些相像，都是把一個問題分成了很多子問題來求解，但是不同的是動態規劃會記憶之前解決的子問題的結果，
避免了重復計算。判斷一個問題是否能用動態規劃求解，要看它是否能劃分成合適的子問題，然後寫出遞推關系式。
動態規劃得到的解一定是最優解。
③ 最佳調度問題（c/c++）
如果各機器運行速度相等，換句話就是任務無論在哪台機器上運行完成時間都相等，則問題較簡單
1 . 先將任務由大到小排序
2 . 計算n個任務需要的總時間和平均到k個機器上的時間
3 . 將大於平均時間的任務各分配一個機器，找到最大完成時間
4 . 將其他任務順序安排在一台機器上，如果時間超出最大時間，則把該任務交給下一個機器，下一個任務繼續在這台機器上試安排，直到所有任務都不能在小於最大完成時間的情況下安排
5 . 安排下一台機器直道所有任務安排完，
6 . 或有可能安排某(些)任務找不到小於最大完成時間 那麼重新掃描各台機器使再加上該任務後時間最小，按此方法安排萬所有任物
數據結構採用鏈表比較合適，
K個機器k個鏈，n個任務按大小順序插入一個鏈表，安排後從任務鏈表中移動到機器鏈表中。知道鏈表為空
④ 貪心演算法
#include <stdio.h>
#define M 100
void main()
{
int i,j,k,temp,m,n;
int t[M]={2,14,4,16,6,5,3},p[M]={1,2,3,4,5,6,7},s[M],d[M]={0};
m=3;n=7;
for(i=0;i<7;i++)
for(j=0;j<7-i;j++)
if(t[j]<t[j+1])
{
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
for(i=0;i<m;i++) //求時間。
{
s[i]=p[i];
d[i]=t[i];
}
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
for(i=m;i<n;i++)
{
for(k=0;k<m-1;k++) //求最小。
{
temp=d[k];
if(temp>d[k+1])
{temp=d[k+1];j=k+1;}
}
printf("這是最小下標的： %d\n",j);
printf("最小的值： %d\n",temp);
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
//j=temp;
s[j]=s[j]+p[i];
d[j]=d[j]+t[i];
}
printf("\n");
for(k=0;k<7;k++)
printf(" %d",t[k]);
printf("\n");
for(k=0;k<7;k++)
printf(" %d",p[k]);
printf("\n");
for(k=0;k<m;k++)
printf(" %d",s[k]);
printf("\n");
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
}
⑤ 演算法怎麼學
貪心演算法的定義：
貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
解題的一般步驟是：
1.建立數學模型來描述問題；
2.把求解的問題分成若干個子問題；
3.對每一子問題求解，得到子問題的局部最優解；
4.把子問題的局部最優解合成原來問題的一個解。
如果大家比較了解動態規劃，就會發現它們之間的相似之處。最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。
話不多說，我們來看幾個具體的例子慢慢理解它：
1.活動選擇問題
這是《演算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。
關於貪心演算法的基礎知識就簡要介紹到這里，希望能作為大家繼續深入學習的基礎。
⑥ 姣忓ぉ涓涓鐭ヨ瘑鐐癸細璐濠綆楁硶鈥斺斾竴涓綆鍗曠殑璋冨害闂棰
鍓嶆彁鏄浣跨敤闈為勫崰璋冨害(nonpreemptive scheling)錛氬嵆涓鏃﹀紑濮嬩竴涓浣滀笟錛屽氨蹇呴』鎶婅ヤ綔涓氳繍琛屽畬銆
鍋囪劇幇鍦ㄦ湁鍥涗釜浣滀笟錛
璇ヨ皟搴︽葷殑浠ｄ環 C 涓
鍗籌細
鍙浠ョ湅鍒幫紝絎涓涓奼傚拰涓庝綔涓氱殑鎺掑簭鏃犲叧錛屽洜姝ゅ彧鏈夌浜屼釜奼傚拰褰卞搷鍒版誨紑閿銆傝懼湪涓涓鎺掑簭涓瀛樺湪 x > y 浣垮緱 < 銆傛ゆ椂錛岃＄畻琛ㄦ槑錛屼氦鎹 鍜 錛岀浜屼釜鍜屽炲姞錛屼粠鑰岄檷浣庝簡鎬葷殑寮閿銆傚洜姝わ紝鎵鐢ㄦ椂闂翠笉鏄鍗曡皟闈炲噺鐨勪換浣曠殑浣滀笟璋冨害蹇呯劧鏄嬈′紭鐨勩傚墿涓嬬殑鍙鏈夐偅浜涘叾浣滀笟鎸夌収鏈灝忚繍琛屾椂闂存渶鍏堝畨鎺掔殑璋冨害鏄鎵鏈夎皟搴︽柟妗堜腑鏈浼樼殑銆
榪欎釜緇撴灉鎸囧嚭涓轟粈涔堟搷浣滅郴緇熻皟搴︾▼搴忎竴鑸鎶婁紭鍏堟潈璧嬩簣閭ｄ簺鏇寸煭鐨勪綔涓氥
闈為勫崰璋冨害鐨勫墠鎻愪笉鍙橈紝鍋囪劇幇鍦ㄦ湁涔濅釜浣滀笟錛
瑙ｅ喅澶氬勭悊鍣ㄦ儏褰㈢殑綆楁硶鏄鎸夌収欏哄簭寮濮嬩綔涓氾紝澶勭悊鍣ㄤ箣闂磋疆鎹㈠垎閰嶄綔涓氥備笉闅捐瘉鏄庢病鏈夊摢涓鍏朵粬鐨勯『搴忚兘澶熷仛寰楁洿濂斤紝鉶界劧澶勭悊鍣ㄤ釜鏁 P 鑳藉熸暣闄や綔涓氭暟 N 鏃跺瓨鍦ㄨ稿氭渶浼樼殑欏哄簭銆
鍗充嬌 P 涓嶆伆濂芥暣闄 N錛屽摢鎬曟墍鏈夌殑浣滀笟鏃墮棿鏄浜掑紓鐨勶紝涔熻繕鏄鏈夎稿氭渶浼樿В銆
灝嗗畬鎴愭椂闂存渶灝忓寲錛屽嵆鏁翠釜搴忓垪鐨勫畬鎴愭椂闂存洿鏃┿