數(shù)據(jù)庫(kù)課程設(shè)計(jì) 飛行員配對(duì)問(wèn)題_第1頁(yè)
數(shù)據(jù)庫(kù)課程設(shè)計(jì) 飛行員配對(duì)問(wèn)題_第2頁(yè)
數(shù)據(jù)庫(kù)課程設(shè)計(jì) 飛行員配對(duì)問(wèn)題_第3頁(yè)
數(shù)據(jù)庫(kù)課程設(shè)計(jì) 飛行員配對(duì)問(wèn)題_第4頁(yè)
數(shù)據(jù)庫(kù)課程設(shè)計(jì) 飛行員配對(duì)問(wèn)題_第5頁(yè)
已閱讀5頁(yè),還剩7頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、吉林財(cái)經(jīng)大學(xué)算法設(shè)計(jì)與分析課程設(shè)計(jì) 專業(yè):計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào): 1401101431 姓名: 黃河一·課設(shè)內(nèi)容分析1)問(wèn)題描述第二次世界大戰(zhàn)時(shí)期,英國(guó)皇家空軍從淪陷國(guó)征募了大量外籍飛行員。由皇家空軍派出的每一架飛機(jī)都需要配備在航行技能和語(yǔ)言上能互相配合的2 名飛行員,其中1名是英國(guó)飛行員,另1名是外籍飛行員。在眾多的飛行員中,每一名外籍飛行員都可以與其他若干名英國(guó)飛行員很好地配合。如何選擇配對(duì)飛行的飛行員才能使一次派出最多的飛機(jī)。對(duì)于給定的外籍飛行員與英國(guó)飛行員的配合情況,試設(shè)計(jì)一個(gè)算法找出最佳飛行員配對(duì)方案,使皇家空軍一次能派出最多的飛機(jī)。2)問(wèn)題分析基礎(chǔ)的二分圖最大匹配問(wèn)題。

2、 給定一個(gè)二分圖G,M為G邊集的一個(gè)子集,如果M滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn),則稱M是一個(gè)匹配。極大匹配是指在當(dāng)前已完成的匹配下,無(wú)法再通過(guò)增加未完成匹配的邊的方式來(lái)增加匹配的邊數(shù)。最大匹配是所有極大匹配當(dāng)中邊數(shù)最大的一個(gè)匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題。如果一個(gè)匹配中,圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián),則稱此匹配為完全匹配,也稱作完備匹配。求二分圖最大匹配可以用最大流或者匈牙利算法。 3)建模方法 在二分圖的基礎(chǔ)上增加源S和匯T。 (1): S向X集合中每個(gè)頂點(diǎn)連一條容量為1的有向邊。 (2): Y集合中每個(gè)頂點(diǎn)向T連一條容量為1的有向邊。 (3): XY集合

3、之間的邊都設(shè)為從A集合中的點(diǎn)到B集合之中的點(diǎn),容量為1的有向邊。 4)建模分析 基本的二分圖最大匹配,可以直接用匈牙利算法或Hopcroft_Karp算法解決,更一般的方法是網(wǎng)絡(luò)最大流。 求網(wǎng)絡(luò)最大流,流量就是匹配數(shù),所有滿流邊是一組可行解。 可行解的輸出:枚舉所以邊< u , v >,如果uX,vY,并且< u , v >滿流,那么當(dāng)前邊為可行解的一組匹配。 二·課程設(shè)計(jì)目的 通過(guò)課程設(shè)計(jì),提高用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力,提高獨(dú)立實(shí)踐的能力,將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái),鍛煉分析解決實(shí)際問(wèn)題的能力。提高結(jié)合實(shí)際的編程能力。在實(shí)際的編程和調(diào)試綜合試題

4、的基礎(chǔ)上,把高級(jí)語(yǔ)言程序設(shè)計(jì)的思想、編程巧和解題思路進(jìn)行總結(jié)與概括,通過(guò)比較系統(tǒng)地練習(xí)達(dá)到真正比較熟練地掌握計(jì)算機(jī)編程的基本功,為后續(xù)的學(xué)習(xí)打下基礎(chǔ)。 最重要的事培養(yǎng)自己的理性思維,無(wú)論是在編程還是在以后的工作生活中養(yǎng)成一個(gè)良好的思維習(xí)慣。三·算法原理及思路運(yùn)用數(shù)學(xué)上的短除法讓一個(gè)整數(shù)對(duì)二取余,然后再讓這個(gè)整數(shù)除以二,取整數(shù)部分,然后繼續(xù)對(duì)二取余,如此繼續(xù)循環(huán),中間只要對(duì)二取余的結(jié)果是一,就累加一次,直到該整數(shù)最后為零,最后把累加的結(jié)果輸出,就是該整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)后里面有多少個(gè)一。四·源代碼 #include <iostream.h>#include <

5、cstdio>#include <cstring>#include <algorithm>#define maxn 10020#define INF 100000000using namespace std;int n, m, s, t, tot, ans, dmaxn, headmaxn, distmaxn;struct E int from;int to;int next;int tab;edgemaxn;void add_edge(int u, int v, int f) tot+; edgetot.from = u, edgetot.to = v, edg

6、etot.tab = f, edgetot.next = headu, headu = tot; tot+; edgetot.from = v, edgetot.to = u, edgetot.tab = 0, edgetot.next = headv, headv = tot;int min(int a,int b)if(a>b)return b;elsereturn a;int dfs(int x, int low) int a; if (x = t) return low; for (int i = headx; i != -1; i = edgei.next) if (edgei

7、.tab > 0 && distedgei.to = distx + 1 && (a = dfs(edgei.to, min(edgei.tab, low) edgei.tab -= a, edgei1.tab += a; return a; return 0; int bfs() int l, r, k; memset(dist,0xff,sizeof(dist); d0 = 0; d1 = s; l = 0, r = 1; dists = 0; while (l < r) k = d+l; for (int i = headk; i != -1;

8、 i = edgei.next) if (edgei.tab > 0 && distedgei.to < 0) distedgei.to = distk + 1, d+r = edgei.to; if (distt > 0) return 1; else return 0; void dinic() ans = 0; while (bfs() ans += dfs(0,INF); void print() if (ans = 0) printf("No Sulotionn"); return; printf("%dn",

9、ans); for (int i = 0; i <= tot; i += 2) if (edgei.tab = 0 && edgei.from != s && edgei.to != t) printf("%d %dn", edgei.from, edgei.to); int main()FILE *file=NULL;file=fopen("data/air0.in","r"); if(file=NULL)cout<<"don't open the file&quo

10、t;<<endl;exit(0); int x, y,i; memset(head,0xff,sizeof(head); tot = -1; while(fscanf(file,"%d%d",&m,&n)!=EOF) s = 0, t = n + 1; for (i = 1; i <= m; i+) add_edge(0, i, 1); for (i = m+1; i <= n; i+) add_edge(i, t, 1); while (fscanf(file,"%d%d",&x,&y)!=EOF) if (x = -1 && y = -1) break; else add_edge(x, y, 1); dinic(); print(); return 0;五·個(gè)人總結(jié) 在這次課程設(shè)計(jì)的學(xué)習(xí)中,我學(xué)到了很多,也找到了自己身上的不足。感受良多,獲益匪淺。 在課程設(shè)計(jì)的過(guò)程中,經(jīng)歷了奮斗的酸甜苦辣。分享了成功的喜悅。這次的課程設(shè)計(jì)對(duì)我來(lái)說(shuō)是一個(gè)挑戰(zhàn)。課程設(shè)計(jì)中文檔的撰寫(xiě)我從來(lái)就沒(méi)有擔(dān)心過(guò),就是代

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論