閉區間線段覆蓋問題貪心演算法

『壹』 線段覆蓋問題 演算法及程序

我的演算法:
我採用貪心的演算法,
按照左端點排序,
建立一個以線段右端點為關鍵字的大根堆.
依次嘗試插入線段,
對於當前的一個線段,
如果能夠覆蓋,顯然我們選擇覆蓋,
而如果不能覆蓋,
我們進行一下討論.
首先我們需要知道
(1)
如果線段發生相交,
那麼只可能是兩條線段相交:
理由:
對於前面的所有線段,貪心法保證,也顯然,已經滿足兩兩不相交了,
那麼如果當前的線段,和另外兩條線段相交,
則必然將一條線段包含,
而我們按照線段左端點排序,
按次序嘗試覆蓋,
因此這種情況是不存在的.
那麼我們假設當前的線段是
[L0,
R0]
發生相交的線段是
[L1,
R1]
即有
L0
>=
L1
R0
<=
R1
這兩條線段是不能共存的.
顯然,我們要從中留下一個而捨去一個,
捨去哪個呢?
就應該選擇右端點小的那個!
為什麼?
因為右端點越靠左,對後面的線段的覆蓋產生的影響(就是發生覆蓋的機會)就越小!
很直觀的,
我們可以知道這種貪心法的正確性.
問題就解決了
時間復雜度
O(N
log
N)
我寫的代碼:
#include
#include
#include
#include
using
namespace
std;
const
int
maxn
=
10010;
struct
event
{
int
l,
r;
}e[maxn];
struct
__Comp
{
inline
int
operator()
(const
event
&a,
const
event
&b)
const
{
return
a.r
<
b.r;
}
};
priority_queue
,
__Comp>
hp;
int
n,
l,
r;
inline
int
comp(const
event
&a,
const
event
&b)
{return
a.l
<
b.l;}
int
main()
{
scanf("%d",
&n);
for
(int
i=0;i
?r};
}sort(e,
e+n,
comp);
for
(int
i=0;i
=
hp.top().r)
hp.push(e[i]);
else
if
(hp.top().r
>
e[i].r)
{
hp.pop();
hp.push(e[i]);
}
}
printf("%d\n",
hp.size());
scanf("%*s");
}

『貳』 近似演算法的集合覆蓋問題的近似演算法

問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬於F中的一個子集，即X= 。對於F中的一個子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得
|C*|=min{|C||CF且C覆蓋X}
集合覆蓋問題舉例：用12個黑點表示集合X。F={S1,S2,S3,S4,S5,S6,}，如圖所示。容易看出，對於這個例子，最小集合覆蓋為：C={S3,S4,S5,}。
集合覆蓋問題近似演算法——貪心演算法
Set greedySetCover (X,F)
{
U=X；
C=；
while (U !=) {
選擇F中使|S∩U|最大的子集S；
U=U-S；
C=C∪{S}；
}
return C；
}
演算法的循環體最多執行min{|X|，|F|}次。而循環體內的計算顯然可在O(|X||F|)時間內完成。因此，演算法的計算時間為O(|X||F|min{|X|，|F|})。由此即知，該演算法是一個多項式時間演算法。

『叄』 關於線段覆蓋的問題

如果一個點在一條線段上（包括這個點是線段端點的情況），我們說「這條線段覆蓋了這個點」。

『肆』 閉區間覆蓋問題的貪心選擇性如何證明

不會呀！你問問老師吧！~~~

『伍』 怎樣用閉區間套定理證明有限覆蓋定理

所謂有限覆蓋定理，是指：對於有界閉區間[a，b]的一個（無限）開覆蓋H中，總能選出有限個開區間來覆蓋[a，b]。
這一問題可用區間套定理來證明。（區間套定理：若[an,bn]是一個區間套，則在實數系中存在唯一一點C，使對任何n都有c屬於[an,bn].{an}單調遞增，{bn}單調遞減，都以c為極限。）

證明：用反證法 假定不能用H中有限個開區間來覆蓋[a,b].
將[a,b]等分為兩個子區間，則其中至少有一個子區間不能用H中有限個開區間來覆蓋。記這個子區間為[a1,b1],則[a1,b1]包含於[a,b],且b1-a1=(b-a)/2.
再將[a1,b1]等分為兩個子區間，同樣，其中至少有一個不能用H中有限個開區間覆蓋。記這個子區間為[a2,b2],則[a2,b2]包含於[a1,b1],且b2-a2=(b-a)/2^2.
重復以上步驟並不斷進行下去，則可得到區間列{[an,bn]},它滿足區間套條件，且其中每一個閉區間都不能用H中有限個開區間來覆蓋。
但，由區間套定理，存在唯一點c屬於所有區間[an,bn].由於H是[a,b]的開覆蓋，一定存在H中的一個開區間(a0,b0),使c屬於(a0,b0).即a0<c<b0.而{an}，{bn}都以c為極限，即知，存在N，當n>N時,a0<an<=c<=bn<b0.這表明，只用開區間(a0,b0)就覆蓋了區間[an,bn].
這與挑選[an,bn]時假設「[an,bn]不能用H中有限個開區間覆蓋」矛盾。從而證得，必存在H中有有限個開區間能覆蓋[a,b].

『陸』 貪心演算法

平面點集三角剖分的貪心演算法要求三角剖分後邊的總長度盡可能小。演算法的基本思想是將所有的兩點間距離從小到大排序，依次序每次取一條三角剖分的邊，直至達到要求的邊數。以下是兩種貪心演算法的主要步驟。

3.2.2.1 貪心演算法1

第一步:設置一個記錄三角剖分中邊的數組T。

第二步:計算點集S中所有點對之間的距離d(p_i，p_j)，1≤i，j≤n，i≠j，並且對距離從小到大進行排序，設為d₁，d₂，…，d_n(n-1)/2，相應的線段記為e₁，e₂，…，e_n(n-1)/2，將這些線段存儲在數組E中。

第三步:從線段集E中取出長度最短的邊e₁存到T中作為三角剖分的第一條邊，此時k=1。

第四步:依次從E中取出長度最短的邊e_k，與T中已有的邊進行求交運算，如果不相交則存到T中，並從E中刪除e_k。這一步運行到S中沒有邊為止，即至k=n(n-1)/2。

第五步:輸出T。

該演算法中，第二步需要計算n(n-1)/2次距離，另外距離排序需要O(n²lgn)次比較。T中元素隨第四步循環次數的增加而增加，因此向T中加入一條新邊所需要的判定兩條線段是否相交的次數也隨之增加。如果第四步的前3n-6次循環後已經構成點集的三角剖分，那麼第四步循環所需要的判定兩條線段是否相交的次數為

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常數時間內可以判定兩條線段是否相交，因此該演算法的時間復雜性為O(n³)。

3.2.2.2 貪心演算法2

第一步:求點集的凸殼，設凸殼頂點為p₁，p₂，…，p_m，凸殼的邊為e₁，e₂，…，e_m。並將凸殼頂點按順序連接成邊的e_i加入T(三角剖分的邊集合)，並且e_i的權值被賦為1。凸殼內點的集合為S₁={p_m+1，p_m+2，…，p_n}。

第二步:從內部點S₁中任取一點p_i，求與p_i距離最近的點p_j，將線段 存入T。

第三步:求與p_j距離最近的點(除點p_i外)，設為p_k，並將線段 加入T，並將這些邊的權值設為1，而w_ij、w_jk和w_ki的值加1，即為2。邊的權值為2則表示該邊為兩個三角形共有。

第五步:對權值為1的邊(除e₁，e₂，…，e_m外)的兩個端點分別求與其距離最近的點，並將其連線(得到新的三角形)加入T，新三角形邊的權值加1。

第六步:對權值為1的邊重復上一步，當一條邊被使用一次其權值增加1，直到所有邊的權值均為2為止(除e₁，e₂，…，e_m外)。

貪心演算法2中，第一步耗費O(nlgn);第二步需要計算n-1次距離與n-2次比較;第三步求p_k要計算n-2次的距離與n-3次比較;第四步要進行(n-3)×3次的距離計算及(n-4)×3次比較;第五步至多進行n-6次的距離計算與n-7次比較;第六步到第五步的循環次數不超過3n-9;因此整個貪心演算法2的時間復雜性為

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

『柒』 貪心演算法及其應用

求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。

比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？

我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？

把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。

貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。

雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；

然而，實際上的最短路徑是S->B->D->T，總代價為6。

所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。

除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。

我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？

這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。

我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？

這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。

對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？

我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。

我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。

貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。

『捌』 求一個演算法(貪心演算法)

首先,無所謂哪裡密集哪裡不密集的說法,這是人為的區分,需要首先遍歷全部格子才能確定,是最慢的演算法,全部遍歷過了就可以得出最優的路線了.
既然用貪心演算法,為了思考方便,可以假設棋盤無窮大,演算法的目的是判斷下一步該往右走還是往下走，思想如下:
判斷當前格子右、下兩個相鄰的格子是否有金塊，情形如下：
1）如果一個有一個沒有，則往有金塊的格子走
2）如果都沒有或都有，則需要判斷往哪個方向走能更快的拾到下一個金塊，方法如下：
讓機器人假設地各往兩個方向走一步，然後對當前格子作判斷情形如下：
A)一個格子繼續走能拾到金塊，另一個不能，則上一步往該格子走
B)如果仍舊都有或都沒有，重復2）直到找到符合A）的情形。

假設棋盤是N*N個格子，則貪心演算法最壞的情形是要遍歷整個棋盤，比如只有第一個格子有金塊時，就需要遍歷整個棋盤才能確定走法。最好的情形也需要遍歷4*N個格子。
時間復雜度上來算的話，應該是O（nLogn）

『玖』 求貪心演算法題（Pascal）

《編程之美》裡面有一道買書問題的貪心演算法。
題目是這樣的：
在節假日的時候，書店一般都會做促銷活動。由於《哈利波特》系列相當暢銷，店長決定通過促銷活動來回饋讀者。上櫃的《哈利波特》平裝本系列中，一共有五卷。假設每一卷單獨銷售均需8歐元 。如果讀者一次購買不同的兩卷，就可以扣除5%的費用，三卷則更多。假設具體折扣的情況如下：
本數 折扣
2 5%
3 10%
4 20%
5 25%
在一份訂單中，根據購買的卷數及本數，就會出現可以應用不同折扣規則的情況。但是，一本書只會應用一個折扣規則。比如，讀者一共買了兩本卷一，一本卷二。那麼，可以享受到5%的折扣。另外一本卷一則不能享受折扣。如果有多種折扣，希望計算出的總額盡可能的低。
要求根據以上需求，設計出演算法，能夠計算出讀者所購買一批書的最低價格。

『拾』 對於二分圖覆蓋問題設計一種貪婪啟發演算法，貪婪准則是：如果B中某一個頂點被A中一個頂點覆蓋，選擇A中這個

西南的吧，呵呵，這個用的是匈牙利演算法，參照．
bool g[][];
int xM[], yM[];
bool chk[];

bool find(int u)
{
int v;
for(v=1; v<=M; v++)
if(g[u][v] && !chk[v])
{
chk[v] = true;
if(yM[v] == -1 || find(yM[v]))
{
yM[v] = u;
xM[u] = v;
return true;
}
}
return false;
}
int MaxMatch()
{
int u, ret = 0;
memset(xM, -1, sizeof(xM));
memset(yM, -1, sizeof(yM));
for(u= 1;u<=N; u++) {
if(xM[u] == -1)
{
memset(chk, false, sizeof(chk));
if(find(u)) ret++;
}
}
return ret;
}