貪心演算法多機調度問題

『壹』 求高手幫忙做一套演算法分析的題目。做好之後再加100。

如何選擇排序、矩陣相乘、樹和圖演算法的時間復雜性計量單位？
排序：排序的循環次數（或遞歸次數）。
矩陣相乘：做實數乘法的次數。
樹：搜索的次數。
圖：同樹。
演算法有幾種基本結構？各種結構的時間復雜度的計算規則？
3種
順序結構：T(n)=O(c)
選擇結構：T(n)=O(c)
循環結構：T(n)=O(n)
最壞情況下的時間復雜性和平均情況下的時間復雜性的定義？
在規模n的全部輸入中，可以找尋執行一個演算法所需的最大時間資源的量，這個量稱為對規模n的輸入，演算法的最壞情況時間復雜性。
對規模都為n的一些有限輸入集，執行演算法所需的平均時間資源的量稱為平均情況下的時間復雜性。
為什麼選擇時間復雜度的漸進性態評價演算法？
因為在規模較小的時候無法客觀體現一個演算法的效率。
解釋f(n)=O(g(n))的意義。
若f(n)和g(n)是定義在正整數集合上的 兩個函數，則f(n)=O(g(n))表示存在正的常數C和n0 ,使得當n≥n0時滿足0≤f(n)≤C*g(n)。
簡述之就是這兩個函數當整型自變數n趨向於無窮大時，兩者的比值是一個不等於0的常數。
有效演算法和無效演算法的劃分原則？
區分在於問題是否能夠精確求解。
用分治法設計演算法有什麼好處？為什麼描述分治演算法需要使用遞歸技術？
分治法可以將問題分為許規模更小的子問題，這些子問題相互獨立且與原問題相同。使用遞歸技術，雖然一些簡單的循環結構替代之，但是復雜的問題，比如二階遞歸是無法替代的。
歸並排序演算法和快速排序演算法劃分子問題和合並子問題的解的方法各是是怎樣的？
歸並排序演算法：
劃分子問題：每次分成2個大小大致相同的子集和
合並子問題：將2個排好序的子數組合並為一個數組
快速排序演算法：對輸入的子數組a[p:r]
劃分子問題：劃分為a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小於a[q]，a[q+1:r] 任意元素大於a[q]
合並子問題：不需要（因為劃分過程就已經排序完成了）
簡述二分檢索（折半查找）演算法為什麼比順序查找的效率高？
對於二分搜索 最壞情況為O(logn)時間完成
而順序查找 需要O(n)次比較
顯然二分搜索效率高
貪心法的核心是什麼？
貪心演算法是通過一系列選擇得到問題的解，它所作出的選擇都是當前狀態下的最佳選擇。
背包問題的目標函數是什麼？背包問題貪心演算法的最優量度是什麼？演算法是否獲得最優解？ 用貪心演算法解0/1背包問題是否可獲得最優解？
Max=∑Vi*Xi (V是價值X取1，0表示裝入或不裝)
每次選取單位重量價值最高的
不一定是最優解

情況不妙啊 LZ還要繼續否。。。
早知發郵件了。。。

『貳』 演算法分析與設計題目

第一題用貪心思想 找出用時最短的m個作業交給機器同時開始加工 然後再依次將剩下的作業中最短完成作業取出放入已完成的機器加工 當最後一台機器完工時間就是所用最短時間 思路是這樣子 具體演算法實現的話。。由於我也是學生=、=寫代碼還不是很熟練。。可能等我寫好了你考試來不及。。。你還是自己來吧

第二題
1.背包問題是什麼=、=我們教材不一樣 不了解具體問題。。
2.4皇後
#include<iostream.h>
const int n = 4 ;
const int n_sub = n - 1 ;
int queen[n] ;
bool row[n] ;
bool passive[2*n-1];
bool negative[2*n-1];
int main()
{
int cur = 0 ;
bool flag = false ;
queen[0] = -1 ;
int count = 0 ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag)
{
queen[cur]++ ;
if(queen[cur] >= n)
{
queen[cur] = -1 ;
cur-- ;
if(cur>=0)
{
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
false ;
}
else
{
if(row[queen[cur]] == false)
{
flag = true ;
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
}
else
flag = true ;
if(flag) {
if(cur == n-1)
{
count++ ;
}
row[queen[cur]] = true ;
passive[queen[cur] + cur] = true ;
negative[n_sub + cur - queen[cur]] = true ;
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
flag = false ;
}
}
}
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
這個是代碼。。。狀態空間樹這里畫不出來。。。

第三題
你網路下基本都有的=、=。。。我網路出來不好意思貼了你自己去看下吧
比如1.的答案：
最壞情況給出了演算法執行時間的上界，我們可以確信，無論給什麼輸入，演算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。

『叄』 高分懸賞貪心演算法的作業

一、演算法思想

貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1. 不能保證求得的最後解是最佳的；
2. 不能用來求最大或最小解問題；
3. 只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

二、例題分析

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）每次選取單位容量價值最大的物品，成為解本題的策略。 ?

2、[單源最短路徑]一個有向圖G，它的每條邊都有一個非負的權值c[i,j]，「路徑長度」就是所經過的所有邊的權值之和。對於源點需要找出從源點出發到達其他所有結點的最短路徑。

E.Dijkstra發明的貪婪演算法可以解決最短路徑問題。演算法的主要思想是：分步求出最短路徑，每一步產生一個到達新目的頂點的最短路徑。下一步所能達到的目的頂點通過如下貪婪准則選取：在未產生最短路徑的頂點中，選擇路徑最短的目的頂點。
設置頂點集合S並不斷作貪心選擇來擴充這個集合。當且僅當頂點到該頂點的最短路徑已知時該頂點屬於集合S。初始時S中只含源。
設u為G中一頂點，我們把從源點到u且中間僅經過集合S中的頂點的路稱為從源到u特殊路徑，並把這個特殊路徑記錄下來（例如程序中的dist[i，j]）。
每次從V-S選出具有最短特殊路徑長度的頂點u，將u添加到S中，同時對特殊路徑長度進行必要的修改。一旦V=S，就得到從源到其他所有頂點的最短路徑，也就得到問題的解 。

stra.pas
3、[機器調度]現有N項任務和無限多台機器。任務可以在機器上處理。每件任務開始時間和完成時間有下表：

任務 a b c d e f g
開始(si) 0 3 4 9 7 1 6
完成(fi) 2 7 7 11 10 5 8

在可行分配中每台機器在任何時刻最多處理一個任務。最優分配是指使用的機器最少的可行分配方案。請就本題給出的條件，求出最優分配。

?三、練習題：
已知5個城市之間有班機傳遞郵件，目的是為了尋找一條耗油量較少的飛行路線。5個城市的聯系網路如圖所示。圖中編號的結點表示城市，兩個城市之間的連線上的值表示班機沿該航線已行的耗油量，並假定從城市i到j和城市j到i之間的耗油量是相同的。

分析：
1. 運用貪心思想：
在每一步前進的選擇上，選取相對當前城市耗油量最小的航線；
2. 圖解：若從1出發，有圖：

總耗油量=14 1-2-5-3-4-1
但若路線改為：1-5-3-4-2-1，則總耗油量=13
所以，這樣的貪心法並不能得出最佳解。
3. 改善方案：
從所有城市出發的信心過程，求最優的。

編程：
1. 數據結構：
城市聯系網路圖的描述(圖的鄰接矩陣的描述)：
const
c=array[1..5,1..5] of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 貪心過程：
begin
初始化所有城市的算途徑標志；
設置出發城市V；
for i:=1 to n-1 do {n-1個城市}
begin
s:=從V至所有未曾到過的城市的邊集中耗油量最少的那個城市；
累加耗油量；
V:=s；
設V城市的訪問標志；
end;
最後一個城市返回第一個城市，累加耗油量；
end;
3. 主過程：實現改善方案
begin
for i:=1 to n do
begin
cost1:=maxint; {初始化}
調用貪心過程，返回本次搜索耗油量cost；
if cost<cost1 then 替換；
end;
輸出；
end

『肆』 貪心演算法的多機調度問題

多塔問題？？
可用動態規劃試一下。。
記錄m台機器中使用時間最長的，時間為Tmax，以及其它m-1台機器所用時間為Ti。
將Ti與Tmax時間差的和記錄為St。則St越小時間Tmax越短。

『伍』 貪心演算法多機調度問題偽代碼

void machineWork::Sort( int timeId[] )
{
for( int i = 0 ; i < works ; i++ )
timeId[i] = i;
for( i = 0 ; i < works - 1 ; i++ )
{
double min = timesUnsorted[ timeId[i] ];
int p = i;
for( int j = i + 1 ; j < works ; j++ )
{
if( this->timesUnsorted[ timeId[j] ] > min )
{
min = this->timesUnsorted[ timeId[j] ];
p = j;
}
}
int t = timeId[i];
timeId[i] = timeId[p];
timeId[p] = t;
}
}

『陸』 演算法分析與設計這門課程第四章貪心演算法的知識點有哪些

演算法分析與設計這門課第四章貪心演算法的知識點包含章節導引,第一節活動安排問題,第二節貪心演算法基本要素,第三節最優裝載,第四節單源最短路徑,第五節多機調度問題,課後練習,。

『柒』 演算法怎麼學

貪心演算法的定義：

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

解題的一般步驟是：

1.建立數學模型來描述問題；

2.把求解的問題分成若干個子問題；

3.對每一子問題求解，得到子問題的局部最優解；

4.把子問題的局部最優解合成原來問題的一個解。

如果大家比較了解動態規劃，就會發現它們之間的相似之處。最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

話不多說，我們來看幾個具體的例子慢慢理解它：

1.活動選擇問題

這是《演算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。

關於貪心演算法的基礎知識就簡要介紹到這里，希望能作為大家繼續深入學習的基礎。

『捌』 求C語言高手 多機調度問題 ，設計個程序 要C語言版的 不要C++的 謝謝啊

#include<stdio.h>
#define N 10

typedef struct node
{
int ID,time;
}jobnode;

typedef struct Node
{
int ID,avail;
}manode;

manode machine[N];
jobnode job[N];

manode* Find_min(manode a[],int m)
{
manode* temp=&a[0];
for(int i=1;i<m;i++)
{
if(a[i].avail<temp->avail)
temp=&a[i];
}
return temp;
}
void Sort(jobnode t[],int n)
{
jobnode temp;
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if(job[j].time>job[j-1].time)
{
temp=job[j];
job[j]=job[j-1];
job[j-1]=temp;
}
}

}

void main()
{
int n,m,temp;
manode* ma;
printf("輸入作業數目(作業編號按輸入順序處理)\n");
scanf("%d",&n);
printf("輸入相應作業所需處理時間:\n");
for(int i=0;i<n;i++)
{
scanf("%d",&job[i].time);
job[i].ID=i+1;
}
printf("輸入機器數目(機器編號按輸入順序處理)\n");
scanf("%d",&m);
for(i=0;i<m;i++)
{
machine[i].ID=i+1;
machine[i].avail=0;
}
putchar('\n');
if(n<=m)
{
printf("為每個作業分配一台機器,可完成任務!\n");
return;
}
Sort(job,n);
for(i=0;i<n;i++)
{
ma=Find_min(machine,m);
printf("將機器: %d 從 %d -----> %d 的時間段分配給作業: %d\n",ma->ID,ma->avail,ma->avail+job[i].time,job[i].ID);
ma->avail+=job[i].time;
}
temp=machine[0].avail;
for(i=1;i<m;i++)
{
if(machine[i].avail>temp)
temp=machine[i].avail;
}
putchar('\n');
printf("該批作業處理完成所需加工時間為: %d\n",temp);

}

剛寫的，試過了，運行通過．主要運用貪心演算法，應該算比較典型的吧，呵呵，該睡覺了，明天還有考試呢，希望對你有幫助！共同進步哈！