大型科技會議議程安排問題-資料下載頁
2025-03-25 12:50本頁面
【正文】 人物同時出現(xiàn)，那么議程的時間安排是容易的。我們用點表示會議分組和關(guān)鍵人物。由于沒有兩個關(guān)鍵人物在同一個場次出現(xiàn)，由此可以用分組和關(guān)鍵人物之間的連線表示一個場次。如果一個場次沒有關(guān)鍵人物，可以指定主持人為關(guān)鍵人物。這樣就形成一個2部分圖。議程的時間安排就是將這個2部分圖化分為k個匹配。由定理三知，當(dāng)k≥Δ時，這個劃分是可以實現(xiàn)的，并且在會場需求方面能保持一定的平衡。相應(yīng)的算法是這樣的：算法二：（1） 用匈牙利算法計算圖中包含所有最大度點的一個最大匹配M。（可行性參見③,第255頁，）（2） 從圖中去掉匹配M中的所有邊，形成新圖。（3） 如果圖中已經(jīng)不存在邊，則結(jié)束，否則轉(zhuǎn)（1）?？梢宰C明，對于圖G＝（V,E）,|V|=n,|E|=m,這個算法的時間復(fù)雜度是O(kmn)五、結(jié)論（一）議程能夠安排成功的幾個必要條件： 足夠的時間和會場： n≦mk 每個分組的會議場次不超過總的時間片數(shù)k。 每個關(guān)鍵人物參加的場次不超過總的時間片數(shù)k。 有序沖突中不能隱含回路。 不存在長度大于k的有向鏈。 沖突圖中不含階大于k的完全子圖。（二）降低問題復(fù)雜度的方法 減少不同分組的場次之間的次序限定。 避免多個關(guān)鍵人物在同一個場次出現(xiàn)的情況。 使“非平凡”的場次盡量少或結(jié)構(gòu)比較整齊。 可以按類型對場次分類，將不同類型的場次安排在不同時間片進行，使問題的規(guī)模降低。致謝首先感謝我的指導(dǎo)教師王鳴老師，是他給我提出研究內(nèi)容，并在方法上給了我許多有用的指導(dǎo)。其次要感謝中科院數(shù)學(xué)所的金雅芳老師、北大數(shù)學(xué)學(xué)院的彭立中老師和柳彬老師，他們曾經(jīng)提供過寶貴的資料和建議。當(dāng)然還要感謝李政道和秦惠先生給我提供了一個寶貴的參加科研的機會。參考文獻（或注）① 盧開澄 《圖論及其應(yīng)用》 清華大學(xué)出版社，1981② B233。la Bollob225。s Modern Graph Theory SpringerVerlag , 1998③ 徐俊明 《圖論及其應(yīng)用》 中國科學(xué)技術(shù)大學(xué)出版社，1998④ 謝金星、邢文訓(xùn) 《網(wǎng)絡(luò)優(yōu)化》 清華大學(xué)出版社，2000⑤ 張立昂 《可計算性與計算復(fù)雜性導(dǎo)論》 北京大學(xué)出版社，1996⑥ 王祜民、趙致格 《時間表問題中的定額匹配算法》 清華大學(xué)學(xué)報，1998年，38卷⑦ 王祜民 《排課表中的分組優(yōu)化決策算法》 控制與決策，作者簡介：于海軍，山東萊西人。自幼喜愛數(shù)學(xué)，一九九五年考入北師大附屬實驗中學(xué)的全國理科試驗班學(xué)習(xí)，一九九八年免試保送北京大學(xué)數(shù)學(xué)科學(xué)學(xué)院。2000年10月獲“華為”獎學(xué)金。業(yè)余愛好：計算機應(yīng)用、書法、球類運動、游泳。特點：對自己要求頗為嚴(yán)格，但標(biāo)準(zhǔn)飄忽不定，經(jīng)常徘徊在完美主義與實用主義之間。雖然喜好結(jié)交朋友，但不善言詞，喜歡獨處。理想:學(xué)以致用，在學(xué)習(xí)和實踐中實現(xiàn)自己的價值。感悟與寄語：能夠在本科階段進行科學(xué)研究的嘗試，對我來說是一件非常重要的事情。在實際的學(xué)習(xí)和研究中，我拓寬了知識面，增長了見識，學(xué)到了進行科學(xué)研究的基本方法和思路。我衷心的祝愿“政基金”越辦越好，希望更多的同學(xué)通過本科階段參與科學(xué)研究而培養(yǎng)良好的科研素質(zhì)！指導(dǎo)教師簡介：王鳴，男，遼寧沈陽人，北京大學(xué)數(shù)學(xué)學(xué)院副教授。主要研究方向：微分方程數(shù)值方法、計算機軟件設(shè)計等。參與和主持的研究項目有：有限元的數(shù)學(xué)理論（國家自然科學(xué)基金），有限元方法的 L∞ 收斂性（國家自然科學(xué)基金），非線性偏微分方程奇性解與微觀結(jié)構(gòu)的數(shù)值解法（國家自然科學(xué)基金），攀登計劃預(yù)選項目《大規(guī)?？茖W(xué)與工程計算的方法和理論》等等。 374 /
法律信息相關(guān)推薦
鄂ICP備17016276號-1