近似算法
- 優(yōu)先級(jí)k-中心問題的FPT近似算法
大多考慮使用近似算法求解優(yōu)先級(jí)k-中心問題。雖然近似算法得到的可行解不是最優(yōu)的，其與最優(yōu)解之間存在一定誤差，但可以保證誤差在一定范圍內(nèi)。近似比是衡量近似解和最優(yōu)解之間差距的指標(biāo)，其值越小表示算法求出的近似解與最優(yōu)解越接近，算法效果越好。因此，近似算法的設(shè)計(jì)目標(biāo)是給出盡可能小的近似比。目前，對(duì)于優(yōu)先級(jí)k-中心問題，GORTZ等[24]給出了近似比為2的近似算法，并且2-近似也是該問題的近似下界[9]。固定參數(shù)可解(fixed-parameter tracta
- 一般圖中的最小概要表示集問題*
提出一個(gè)貪心近似算法進(jìn)行求解。2 問題描述2.1 問題定義給定一個(gè)無(wú)向圖G=(V,E)，其中,V表示節(jié)點(diǎn)集，E表示邊集。圖G上的一個(gè)集合函數(shù)s:2V×V→[0,1]是任意2個(gè)節(jié)點(diǎn)的相似度函數(shù)。在圖G中，節(jié)點(diǎn)的個(gè)數(shù)n=|V|，邊的條數(shù)m=|E|。給定一個(gè)代表點(diǎn)組成的集合D，任意節(jié)點(diǎn)v∈V和子集D中任意代表點(diǎn)的最大相似度為maxu∈Ds(v,u)，和子集D中所有代表點(diǎn)的相似度之和為∑u∈Ds(v,u)。 顯然對(duì)于任意節(jié)點(diǎn)v∈V,maxu∈Ds(v,u)和∑u∈
計(jì)算機(jī)工程與科學(xué) 2023年1期2023-02-08
- 基于Contig的單面基因組片段填充問題研究
因組片段填充近似算法是近些年來的討論熱點(diǎn)。依據(jù)基因樣本序列中是否含有重復(fù)基因，將該基因組填充問題分為含重復(fù)基因的基因組片段填充問題和無(wú)重復(fù)基因的基因組片段填充問題；或依據(jù)基因樣本序列不完整數(shù)量，將該基因組填充問題分為單面基因組片段填充和雙面基因組片段填充，其中一條序列完整，另一條序列缺失，稱為單面基因組序列，兩條基因序列均為不完整的，則為雙面基因組序列[15]。該文重點(diǎn)討論單面重復(fù)基因組片段填充問題。Munoz和D. Sankoff等人[12-13]首次提
計(jì)算機(jī)技術(shù)與發(fā)展 2022年11期2022-11-25
- {1,2}-賦權(quán)圖最小最大2-路徑覆蓋問題的近似算法
的情況來設(shè)計(jì)近似算法。2 算法設(shè)計(jì)與分析本文設(shè)計(jì)的近似算法主要基于文獻(xiàn)[4]提出的TSP算法，將其命名為基于TSP的近似算法。首先調(diào)用文獻(xiàn)[4]關(guān)于TSP問題的算法，找到覆蓋G中所有頂點(diǎn)恰好一次的圈C；然后刪除圈C中2條不相鄰的邊，構(gòu)成2條頂點(diǎn)不相交的路徑P1和P2，為了使得其中的最大路徑權(quán)重盡可能小，刪邊時(shí)應(yīng)確保P1和P2的權(quán)重盡量均衡。當(dāng)圈C中的邊權(quán)重均為1時(shí)，刪邊過程是簡(jiǎn)單的；當(dāng)圈C中包含至少1條權(quán)重為2的邊時(shí)，本文算法采取一種貪婪的刪邊方法，具體步
- 大規(guī)模網(wǎng)絡(luò)中k-點(diǎn)連通分量發(fā)現(xiàn)算法研究
概率采樣）的近似算法，可以高效計(jì)算出所有k-VCCs，并且結(jié)合實(shí)驗(yàn)對(duì)誤差進(jìn)行了分析。2 基本概念及相關(guān)定義本節(jié)主要介紹一些基本概念及其符號(hào)表達(dá)，闡述了k-點(diǎn)連通圖的相關(guān)定義，并對(duì)要解決的主要問題給出具體定義。2.1 基本概念本文中給定一個(gè)無(wú)向圖G(V,E)，V 表示圖的頂點(diǎn)集合，E 表示圖的邊集合，n 表示圖的頂點(diǎn)數(shù)即|V|，m 表示圖的邊數(shù)即|E|。定義1 (點(diǎn)割集)：對(duì)于連通圖G，若V'?V 且G[VV']不是連通圖，則V'是圖G 的一個(gè)點(diǎn)割集?；邳c(diǎn)
電子技術(shù)與軟件工程 2022年8期2022-07-08
- 需求不確定的故障共享單車回收PVRP研究
針對(duì)模型設(shè)計(jì)近似算法進(jìn)行求解，分析算法近似比的上下界，通過實(shí)例分析驗(yàn)證了算法和模型的有效性。關(guān)鍵詞：需求不確定；周期性車輛路徑；魯棒優(yōu)化；近似算法中圖分類號(hào)：C934文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2097-0145（2022）05-0073-08doi：10.11847/fj.41.5.73Period Vehicle Routing Problem for Fault-sharing BicycleRecycling with Demand Uncertain
預(yù)測(cè) 2022年5期2022-05-30
- 一種超寬帶隨機(jī)噪聲壓縮感知雷達(dá)成像方法
提出了零延拓近似算法，通過在重建算法的迭代中利用二維FFT和快速小波變換，實(shí)現(xiàn)快速計(jì)算矩陣和向量的乘法。仿真結(jié)果表明，這種近似算法在極大地降低運(yùn)算量和內(nèi)存消耗的同時(shí)，保持著較好的運(yùn)算精度，可以完成對(duì)大尺度場(chǎng)景的成像任務(wù)。1 基本原理1.1 CS 理論CS 理論主要研究稀疏信號(hào)的重建及其可重建條件，稀疏信號(hào)可以通過較少的非自適應(yīng)測(cè)量集準(zhǔn)確重建。其數(shù)學(xué)描述為：∈R為觀測(cè)向量，它與未知稀疏信號(hào)∈R有如下關(guān)系：式中，∈R，為感知矩陣，是對(duì)未知信號(hào)進(jìn)行的線性測(cè)量。當(dāng)
現(xiàn)代電子技術(shù) 2022年9期2022-05-12
- 瞬變電磁虛擬波場(chǎng)二階Born近似成像算法
中，Born近似算法可以解決積分方程解非線性的問題(Cohen and Bleistein，1977，1979；黃聯(lián)捷和楊文采，1991)，在無(wú)初始速度模型的條件下，可以直接得到深度剖面，克服了偏移算法需要事先給定初始速度模型的缺陷(丁科和宋守根，2004)，因此，該方法被廣泛應(yīng)用于地震勘探成像領(lǐng)域.Cohen和Bleistein(1979)、Bleistein和Cohen(1982)、Bleistein等(2001)假定反射波足夠弱，針對(duì)地震反演中的二維
地球物理學(xué)報(bào) 2022年3期2022-03-15
- 線性分式多乘積問題的?-近似算法
(1+?)-近似算法5.計(jì)算復(fù)雜度6.數(shù)值算例給定ε= 0.12,τ= 3,本文計(jì)算結(jié)果:最優(yōu)解為(0.0000;1.3866;7.2004;2.8519;4.6240;0.0000;0.0000;5.6716;0.0923;4.2396;4.5181;5.3483),近似最優(yōu)值0.2687,最優(yōu)值上界為0.2687,運(yùn)算時(shí)間為7.1930秒.給定ε=0.12,τ=3,文[6]計(jì)算結(jié)果:最優(yōu)解為(0.0052;1.3800;7.1955;2.8451;4.
應(yīng)用數(shù)學(xué) 2021年4期2021-10-20
- 邊著色圖上最大弱適當(dāng)樹問題近似算法
適當(dāng)樹問題的近似算法設(shè)計(jì)及其理論分析。1 邊著色圖上最大弱適當(dāng)樹問題定義1設(shè)T是邊著色圖Gc的1個(gè)子圖，將子圖邊著色，使得每個(gè)頂點(diǎn)的鄰邊著不同的顏色。如果子圖為1個(gè)路徑，則稱為適當(dāng)路徑(Proper Path)。定義2如果子圖是1棵樹，即這個(gè)子圖是連通且無(wú)圈子圖，當(dāng)子圖覆蓋Gc的所有頂點(diǎn)則稱樹為Gc的生成樹，在生成樹上固定一個(gè)頂點(diǎn)為樹的根，根到樹的任何葉子都是適當(dāng)路徑，但樹頂點(diǎn)的鄰邊能著相同顏色，則稱為弱適當(dāng)樹。對(duì)于邊著色圖Gc，在圖Gc上找到包含頂點(diǎn)最多
- 基于訂單取消量可預(yù)測(cè)的制造商原材料庫(kù)存優(yōu)化研究
O（np）的近似算法GA求解模型（其中n為原材料的種類數(shù)，p為預(yù)測(cè)訂單取消量的時(shí)段數(shù)），并分析了算法GA的近似比。最后選取XAHL有限公司的庫(kù)存數(shù)據(jù)進(jìn)行實(shí)例分析，驗(yàn)證了模型和算法的有效性，根據(jù)模型計(jì)算結(jié)果給出公司原材料采購(gòu)和庫(kù)存優(yōu)化策略。本文旨在為制造商進(jìn)行原材料采購(gòu)及庫(kù)存決策提供理論依據(jù)。關(guān)鍵詞：預(yù)測(cè);訂單取消量;原材料庫(kù)存;線性回歸;近似算法中圖分類號(hào)：C934文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1003-5192（2021）03-0069-07doi：10.11
預(yù)測(cè) 2021年3期2021-07-12
- 魯棒動(dòng)態(tài)設(shè)施選址問題的近似算法
這類方法稱為近似算法，即，如果算法A所得解的費(fèi)用不超過α倍最優(yōu)值，那么被稱為α-近似算法。UFLP的第一個(gè)常數(shù)近似比是由Shmoys等人[18]通過建立整數(shù)線性規(guī)劃，松弛整數(shù)約束，進(jìn)而利用算法將分?jǐn)?shù)最優(yōu)解舍入為整數(shù)解，給出了3.16-近似算法。后來，許多學(xué)者不斷創(chuàng)造新的技巧得到更好的近似比?？傮w來說，設(shè)施選址問題的近似算法技巧可以分為四類，線性規(guī)劃舍入[18]，原始-對(duì)偶[11]，對(duì)偶-擬合[10]，局部搜索[1]。目前，最好的近似比是Li[15]利用綜合
運(yùn)籌與管理 2020年5期2020-10-24
- 頂點(diǎn)賦權(quán)圖中的連通子圖劃分問題
分相鄰。2 近似算法與算法分析定義2如果V2滿足：(1)V2中存在點(diǎn)u，u與V1之間有邊相連；(2)在V2中，u同時(shí)連接若干個(gè)連通分支C21,C22,…,C2s，且w(C21)≥w(C22)≥…≥w(C2s)；(3)w(V1)本文提出的近似算法(簡(jiǎn)稱：2-GP算法)思想如下：首先找到圖G的一棵生成樹T，再?gòu)腡中任意刪除k-1條邊，產(chǎn)生k個(gè)連通分支V1,V2,…,Vk，w(Vi)表示第i個(gè)連通分支的權(quán)重，循環(huán)運(yùn)用定義1至定義3的操作，逐步減小總權(quán)重最大子集的
- 稀疏高斯過程在短期風(fēng)電功率概率預(yù)測(cè)中的應(yīng)用
ss，PP）近似算法的3種Sparse-GP方法，該方法不僅能給出模型的均值預(yù)測(cè)，而且能獲取模型的預(yù)測(cè)方差，這很好地解釋了模型置信水平。不同的sparse-GP方法在保持常規(guī)GP方法優(yōu)點(diǎn)的同時(shí)，還能解決GP方法隨著訓(xùn)練數(shù)據(jù)增加而產(chǎn)生的矩陣運(yùn)算困難等難題，且計(jì)算效率高。將具有不同協(xié)方差函數(shù)形式的sparse-GP方法應(yīng)用于不同地區(qū)的短期風(fēng)電功率單步與多步預(yù)測(cè)實(shí)例中，在同等條件下還與常規(guī)GP、sVM方法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，sparse-GP方法可以給出較好
電機(jī)與控制學(xué)報(bào) 2019年8期2019-10-31
- 一種最優(yōu)相似度的公共序列研究
公共子序列;近似算法;貪心算法隨著科學(xué)技術(shù)的進(jìn)步，人們利用序列的相似性比較研究各個(gè)方向。例如，生物學(xué)中的親子鑒定、醫(yī)學(xué)中的診斷病基因確定疾病。隨著科學(xué)的進(jìn)步，字符串之間的相似問題也成為研究的重點(diǎn)，同時(shí)，提出了許多類似于上述的序列相似度算法。根據(jù)不同的特征，相似度的計(jì)算方法也不盡相同，主要有方面相似算法、統(tǒng)計(jì)關(guān)聯(lián)算法、相似語(yǔ)義算法等。有人提出結(jié)合3種算法的優(yōu)缺點(diǎn)，建立多層規(guī)劃模型。其中，相似字面主要包括距離編輯和類似的字或者詞語(yǔ)的計(jì)算方法。因此，此研究在各個(gè)
無(wú)線互聯(lián)科技 2019年12期2019-10-11
- 特定材料構(gòu)建支撐樹問題的近似算法研究
計(jì)了一個(gè)2—近似算法，并分析了算法的復(fù)雜性，證明了算法的近似度。關(guān)鍵詞：支撐樹 ?裝箱 ?NP—難 ?近似算法中圖分類號(hào)：TP301.6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1672-3791（2019）06（a）-0228-021 ?問題描述及分析我們可以將該實(shí)際問題抽象成如下數(shù)學(xué)模型。問題1 給定權(quán)重圖和一種長(zhǎng)度為L(zhǎng)的特定材料，其中V表示圖G的頂點(diǎn)集，E表示
科技資訊 2019年16期2019-08-13
- 帶懲罰費(fèi)用的多重任務(wù)排序問題?
，排序問題的近似算法研究都是算法理論領(lǐng)域研究的熱點(diǎn)問題之一。受滑雪板租賃問題的啟發(fā)，Bartal等［1］提出帶懲罰費(fèi)用的平行機(jī)排序問題 P∥Cmax+Σj∈Rwj，其定義如下：給定 m 臺(tái)平行機(jī)和n項(xiàng)任務(wù)，每項(xiàng)任務(wù)的處理時(shí)間為 pj，懲罰費(fèi)用為wj，一項(xiàng)任務(wù)要么被接受并在某臺(tái)機(jī)器上處理，要么被拒絕并產(chǎn)生相應(yīng)的懲罰費(fèi)用。該問題的目標(biāo)是尋找一個(gè)排序方案，使得機(jī)器的最大完工時(shí)間與被拒絕任務(wù)的懲罰費(fèi)用之和最小。Bartal等［1］設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(nlogn
計(jì)算機(jī)與數(shù)字工程 2019年1期2019-03-01
- 衰落相關(guān)信道近似算法及其Massive MIMO系統(tǒng)分析?
信道模型及其近似算法，從而分析Massive MIMO系統(tǒng)性能和算法效能.首先導(dǎo)出在典型PAS下的SFC函數(shù)的閉合表達(dá)式，研究在小角度擴(kuò)展時(shí)的近似算法以及評(píng)估其計(jì)算效能，建立MIMO多天線接收模型和分析其系統(tǒng)性能.研究揭示了其信道特征的諸多關(guān)鍵因素，闡明陣元接收信號(hào)強(qiáng)度變化、陣元衰落信號(hào)相關(guān)性和信道矩陣分布特征.通過理論計(jì)算和仿真實(shí)驗(yàn)得出近似計(jì)算法在特定條件下具有很好的擬合度，定量分析了近似算法在對(duì)MIMO多天線系統(tǒng)分析時(shí)的適用性和計(jì)算效率.通過理論計(jì)算得
- 基于證據(jù)等級(jí)的非主觀近似算法
計(jì)算，因此該近似算法無(wú)法運(yùn)用于實(shí)際計(jì)算中；Voorbraak[11]提出了Bayesian近似方法,這是一種非主觀的近似方法，解決了復(fù)合焦元的融合問題，且在計(jì)算較少焦元時(shí)融合結(jié)果比較準(zhǔn)確，但對(duì)“焦元爆炸”的問題依然無(wú)法很好地解決；Tessem[12]提出的(K,L,X)近似方法和Lowrance[13]提出的Summarization近似算法[13]，本質(zhì)上都屬于主觀的近似算法，基本解決了“焦元爆炸”的問題，但由于這兩種算法都需要通過人為主觀判斷閾值，都不
- Spider圖的[1，2]—支配數(shù)研究
，2]-數(shù)的近似算法.【關(guān)鍵詞】Spider圖；[1，2]-支配數(shù)；近似算法【基金項(xiàng)目】南京工業(yè)大學(xué)浦江學(xué)院科研項(xiàng)目（njpj-2016-2-02）.一、引 言一個(gè)集合SV（G）若被稱為圖G的支配集（Dominating Set）[1]，則有任意的頂點(diǎn)v或者在S中或者與S中的點(diǎn)相鄰接.我們把頂點(diǎn)數(shù)目最少的支配集稱為圖的最小支配集（Minimum Dominating Set），它的頂點(diǎn)數(shù)目稱為圖的支配數(shù)（Dominating Number），記作γ（G）.
數(shù)學(xué)學(xué)習(xí)與研究 2018年10期2018-08-21
- 基于羅特曼透鏡的多波束比幅測(cè)向算法研究
了傳統(tǒng)的高斯近似算法、三角近似算法、三波束算法的優(yōu)劣，并給出了算法具體應(yīng)用時(shí)的技巧。1 系統(tǒng)組成和原理基于羅特曼透鏡的多波束比幅測(cè)向系統(tǒng)由透鏡波束形成網(wǎng)絡(luò)、對(duì)數(shù)視頻放大器(DLVA)幅度檢測(cè)、多通道采樣及角度計(jì)算單元組成[2-3]。以六波束比幅測(cè)向系統(tǒng)為例，其組成框圖如圖1、圖2所示。圖1 羅特曼透鏡六波束測(cè)向系統(tǒng)框圖圖2 多通道采樣及角度計(jì)算單元框圖其基本原理是：六元陣天線及羅特曼透鏡形成不同指向的6個(gè)波束，覆蓋±45°范圍，透鏡波束口將6波束接收信號(hào)送
艦船電子對(duì)抗 2018年2期2018-06-19
- 多材料Terminal Steiner樹拼接問題的近似算法研究
寸裝箱問題的近似算法及算法復(fù)雜度，給出多材料的Terminal Steiner樹拼接問題的一個(gè)近似算法;最后證明算法的近似值及近似算法的時(shí)間復(fù)雜度。關(guān)鍵詞： Terminal Steiner樹; 拼接問題; 變尺寸裝箱; 近似算法; 絕對(duì)近似比; 時(shí)間復(fù)雜度中圖分類號(hào)： TN911?34; TP301.6 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2018）10?0028?03Abs
現(xiàn)代電子技術(shù) 2018年10期2018-05-15
- 基于最小二乘法的電主軸回轉(zhuǎn)精度評(píng)價(jià)*
法、最小二乘近似算法和平均值算法對(duì)信號(hào)進(jìn)行處理與分析，并驗(yàn)證了3種算法的有效性。最后在分析對(duì)比3種算法結(jié)果后，設(shè)計(jì)了一種不同應(yīng)用背景下的電主軸回轉(zhuǎn)精度評(píng)價(jià)策略，并提出了一種兼顧計(jì)算精度和計(jì)算效率的電主軸回轉(zhuǎn)精度快速評(píng)價(jià)算法。1 電主軸幾何誤差建模首先對(duì)電主軸回轉(zhuǎn)幾何誤差進(jìn)行建模，電主軸檢測(cè)裝置如圖1所示，其原理為在電主軸前端安裝標(biāo)準(zhǔn)球，并在球的兩側(cè)安裝兩個(gè)相互垂直的位移傳感器，來采集電主軸徑向運(yùn)動(dòng)信號(hào)。將電主軸旋轉(zhuǎn)運(yùn)動(dòng)進(jìn)行建模，并將電主軸與檢測(cè)裝置沿著回轉(zhuǎn)
制造技術(shù)與機(jī)床 2018年2期2018-03-20
- 基于Visual C++的裝箱問題的BF算法
得到滿意解，近似算法經(jīng)常被使用。常見的算法[2]：NF（Next Fit）近似算法，BF（Best Fit）算法，BFD（Best Fit Deceasing）算法，F(xiàn)F（First Fit）近似算法，F(xiàn)FD（First Fit Decreasing）近似算法等。2 裝箱問題的集中常見算法[3]下次適應(yīng)算法NF（Next Fit）：最簡(jiǎn)單也是最早研究的算法是NF算法。它的特點(diǎn)是至始至終保持一個(gè)當(dāng)前打開的箱子，在要將貨品裝入到箱子時(shí)，查看這個(gè)貨品能不能裝入到
電腦知識(shí)與技術(shù) 2018年36期2018-03-04
- 具有樹和路約束的平行機(jī)排序問題*
固定)的2-近似算法以及關(guān)于P|vertex cover|Cmax問題(機(jī)器數(shù)m不固定)的(2+ε)-近似算法(ε＞0為任意常數(shù))。與此同時(shí)，Nip 等人［5，6］研究在最短路約束下的流水車間調(diào)度問題，即選取工件集的一個(gè)子集使其是給定圖中的一條路，將該工件子集中的工件放在流水車間處理，目標(biāo)是使其最大完工時(shí)間(makespan)盡可能小。對(duì)于具有最短路約束的流水車間調(diào)度問題，當(dāng)機(jī)器數(shù)為2時(shí)(簡(jiǎn)記為F2|shortest path|Cmax)，分別存在近似比為
計(jì)算機(jī)工程與科學(xué) 2018年12期2018-02-26
- 基于Delaunay三角剖分處理二維歐式空間MTSP的近似算法
間MTSP的近似算法壽 濤, 劉朝暉(華東理工大學(xué)數(shù)學(xué)系,上海 200237)考慮了在二維歐式平面內(nèi)的多旅行商問題,通過Delaunay三角剖分的方法,將問題轉(zhuǎn)化為求解多個(gè)旅行商問題。樹分解算法的核心是Delaunay邊的空?qǐng)A性質(zhì)并且可以證明該算法的近似比為2。最后,通過數(shù)值模擬驗(yàn)證了算法的有效性。MTSP; Delaunay三角剖分; 近似算法多旅行商問題(MTSP)是TSP問題的推廣[1]。通常可以把MTSP問題拆分成2個(gè)子問題,即:先確定每個(gè)旅行商訪
- 巡檢線路的排班模型
題；賦權(quán)圖；近似算法；均衡度【基金項(xiàng)目】吉安職業(yè)技術(shù)學(xué)院校級(jí)科研項(xiàng)目（16JY137）資助【中圖分類號(hào)】TQ086.2；TP274.4 【文獻(xiàn)標(biāo)識(shí)碼】B 【文章編號(hào)】2095-3089（2017）17-0292-02一、問題重述某化工廠有26個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，每個(gè)點(diǎn)每次巡檢需要一名工人，巡檢工人的巡檢起始地點(diǎn)在巡檢調(diào)度中心（XJ0022），工人可以按固定時(shí)間上班，也可以錯(cuò)時(shí)上班，在調(diào)度中心得到巡檢任務(wù)后開始巡檢。巡檢線路是指從巡檢調(diào)度中心（X
課程教育研究·新教師教學(xué) 2017年17期2017-12-16
- 環(huán)錠細(xì)紗機(jī)卷繞成形紗長(zhǎng)不同計(jì)算方法的比較和應(yīng)用
升降方式下，近似算法和精確算法產(chǎn)生的繞紗長(zhǎng)度差異，并探討鋼領(lǐng)板上升速度和前羅拉出紗速度與卷繞轉(zhuǎn)角的關(guān)系。指出：近似紗長(zhǎng)總大于精確紗長(zhǎng)，且卷繞齒輪副ZF/ZG的近似值總比精確計(jì)算的小，不利于成形和高速絡(luò)筒，故電子升降應(yīng)采用精確算法；通過分析鋼領(lǐng)板在上升狀態(tài)時(shí)的瞬時(shí)速度和卷繞轉(zhuǎn)角的關(guān)系式，可計(jì)算伺服電機(jī)的瞬時(shí)轉(zhuǎn)速。環(huán)錠紡；卷繞成形；機(jī)械升降；電子升降；紗長(zhǎng)；近似計(jì)算；精確計(jì)算0 引言隨著環(huán)錠細(xì)紗機(jī)和絡(luò)筒機(jī)速度的不斷提高，為防止毛羽、斷頭、脫圈等指標(biāo)惡化，對(duì)細(xì)紗
紡織器材 2017年4期2017-08-22
- 三臺(tái)可拒絕平行機(jī)在線排序問題的近似算法
線排序問題的近似算法榮建華1, 侯麗英2(1.石家莊鐵道大學(xué) 四方學(xué)院 ，河北 石家莊 051132;2.南京農(nóng)業(yè)大學(xué) 理學(xué)院，江蘇 南京 210095)同型機(jī)； 拒絕費(fèi)用；中斷加工 ； 運(yùn)籌學(xué)；在線排序；競(jìng)爭(zhēng)比0 引言在經(jīng)典的排序文獻(xiàn)中，所有的工件都不允許被拒絕，換言之，任何工件都必須被安排到機(jī)器上進(jìn)行加工。然而在工廠實(shí)際生產(chǎn)過程中，生產(chǎn)決策者們并非總是如此。在現(xiàn)有的生產(chǎn)資源有限的前提下，為了使企業(yè)獲得更多的利潤(rùn)，生產(chǎn)廠家有時(shí)不得不拒絕一些資源耗費(fèi)較多但
- 透鏡式薄壁CFRP管壓扁力分析
，建立壓扁力近似算法1；假設(shè)給出截面局部接觸變形函數(shù)，建立壓扁力近似算法2。綜合試驗(yàn)、數(shù)值模擬與兩種近似算法的結(jié)果，發(fā)現(xiàn)壓扁過程中壓扁力與截面變形均表現(xiàn)出較強(qiáng)的非線性特性，可用近似算法2估算壓扁力。透鏡式薄壁管；CFRP復(fù)合材料；試驗(yàn)研究；數(shù)值模擬；近似算法；壓扁力0 引 言透鏡式薄壁纖維增強(qiáng)聚合物(Carbon fiber reinforced polymer,CFRP)管作為一種空間支撐結(jié)構(gòu)，具有材料高比強(qiáng)、韌性好、熱膨脹系數(shù)小等優(yōu)點(diǎn)。其由上下兩近似“
宇航學(xué)報(bào) 2017年5期2017-06-15
- 哈密爾頓圖在快遞送貨中的應(yīng)用
加權(quán)圖給出了近似算法、最小生成樹算法和遺傳算法三種方法，求解最佳圈，即最優(yōu)快遞送貨策略。關(guān)鍵詞：哈密爾頓圈；最佳推銷員回路；近似算法；最小生成樹算法；遺傳算法近年來，我國(guó)快遞業(yè)發(fā)展迅速，企業(yè)數(shù)量大幅增加，業(yè)務(wù)規(guī)模持續(xù)擴(kuò)大，服務(wù)水平不斷提升，在降低流通成本、支撐電子商務(wù)、服務(wù)生產(chǎn)生活、擴(kuò)大就業(yè)渠道等方面發(fā)揮了積極作用。國(guó)務(wù)院也在2015年印發(fā)了《關(guān)于促進(jìn)快遞業(yè)發(fā)展的若干意見》，快遞業(yè)已經(jīng)成為現(xiàn)代服務(wù)業(yè)的重要組成部分，是推動(dòng)流通方式轉(zhuǎn)型、促進(jìn)消費(fèi)升級(jí)的現(xiàn)代化先
科學(xué)與財(cái)富 2017年9期2017-06-09
- 鐵路平車裝載問題模型及算法
st Fit近似算法、First Fit近似算法和Next Fit近似算法分別求解并比較分析，得出分析結(jié)果。平車裝載；算法；優(yōu)化1 引言鐵路運(yùn)輸具有運(yùn)量大、速度快、不易受天候和季節(jié)的影響,適合遠(yuǎn)距離運(yùn)輸?shù)葍?yōu)點(diǎn),在現(xiàn)代物流中承擔(dān)著重要的運(yùn)輸任務(wù),同時(shí)也是部隊(duì)兵力機(jī)動(dòng)采用的機(jī)動(dòng)方式之一。研究鐵路輸送中的列車裝載問題模型與算法，并運(yùn)用于相應(yīng)的軍事輔助決策系統(tǒng)，是適應(yīng)未來戰(zhàn)場(chǎng)、提高指揮效能的客觀需要。在鐵路運(yùn)輸中經(jīng)常會(huì)遇到輪式（履帶式）車輛裝備的運(yùn)輸裝載問題,為了
物流技術(shù) 2017年4期2017-06-05
- 兩臺(tái)不同速碼頭起重機(jī)調(diào)度問題的改進(jìn)分析
重機(jī)；調(diào)度；近似算法；最壞情況分析0 引 言1 符號(hào)說明及近似算法引理1[4]C*≥T/(s+1).算法A[4]在以下兩個(gè)調(diào)度方案中選取較好的一個(gè)輸出并終止：方案一：將全部船艙都分配給QC2處理.方案二：從船頭到船尾將船艙分為兩部分使得左側(cè)部分船艙總耗時(shí)為T/(s+1)，右側(cè)部分船艙總耗時(shí)為Ts/(s+1)：1)若不存在兩側(cè)公用的船艙(稱為交叉船艙)，則將左、右兩側(cè)的船艙分別分配給QC1和QC2處理.(1)此時(shí)若L≥R/s，則將前i個(gè)船艙分配給QC1，其余
- 求投影深度最深點(diǎn)的近似算法
深度最深點(diǎn)的近似算法，并給出了該算法的復(fù)雜度，通過模擬可以看出該算法精確度較高，所需時(shí)間短。關(guān)鍵詞： 投影深度 算法 模擬4.結(jié)語(yǔ)模擬證明以上算法精確度較高，復(fù)雜度較低。當(dāng)數(shù)據(jù)集的大小和維數(shù)較高時(shí)，仍然可以較快地得到令人滿意的結(jié)果。參考文獻(xiàn)：[1]Schapire，R.E.Improved boosting algorithms using confidence-rated predictions.Machine Learning，2003，37（3）：1
考試周刊 2016年88期2016-11-24
- 機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問題
個(gè)多項(xiàng)式時(shí)間近似算法，并證明了該算法的最壞情況界不大于5/3。單臺(tái)機(jī)；維護(hù)時(shí)段；不可恢復(fù)；近似算法0 引 言機(jī)器帶維護(hù)時(shí)段的排序問題和加工與運(yùn)輸協(xié)同的排序問題是兩類重要的排序問題。由于這兩類排序問題在生產(chǎn)制造及供應(yīng)鏈管理中具有廣闊的應(yīng)用前景，所以近年來得到了廣泛的研究。而機(jī)器帶維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同的排序問題，是這兩類排序問題的結(jié)合，同樣具有重要的應(yīng)用價(jià)值并得到了一定的關(guān)注和研究。機(jī)器帶維護(hù)時(shí)段的排序問題，根據(jù)機(jī)器上維護(hù)時(shí)段的個(gè)數(shù)可分為單維護(hù)時(shí)段排序問題
- 帶有到達(dá)時(shí)間和拒絕費(fèi)用工件的同類機(jī)排序問題
致力于研究其近似算法，通常用競(jìng)爭(zhēng)比ρA來衡量算法A的優(yōu)劣.設(shè)ZA(I)為用算法A安排實(shí)例I所得的目標(biāo)值，Z*(I)為離線排序下的最優(yōu)值，則定義ρA=inf{l|ZA(I)≤lZ*(I),?I}.一個(gè)排序問題具有下界ρL是指其競(jìng)爭(zhēng)比嚴(yán)格小于ρL的算法A不存在.如果某算法A的競(jìng)爭(zhēng)比與其相應(yīng)的下界相等，即ρA=ρL，則稱該算法為最優(yōu)近似算法.1 Qm|rj∈{0,r},online|W的算法設(shè)計(jì)令S為工件集，表1為文中所涉及的符號(hào).表1 符號(hào)及含義證明當(dāng)△=0時(shí)
浙江大學(xué)學(xué)報(bào)（理學(xué)版） 2016年5期2016-09-16
- lp范數(shù)下具有等級(jí)約束的負(fù)載均衡問題*
：負(fù)載均衡；近似算法；全范數(shù)1 引言自20世紀(jì)60年代起，以最小化最大機(jī)器負(fù)載[1-2]為目標(biāo)的負(fù)載均衡問題因其在工業(yè)生產(chǎn)、并行計(jì)算和網(wǎng)絡(luò)資源分配等領(lǐng)域的廣泛應(yīng)用，成為理論計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)等領(lǐng)域研究的重點(diǎn)內(nèi)容之一。注意到，機(jī)器的最大負(fù)載在數(shù)學(xué)上相當(dāng)于機(jī)器負(fù)載向量的l∞范數(shù)。由于最小化最大機(jī)器負(fù)載側(cè)重于刻畫最大機(jī)器完工時(shí)間，并不適用于描述機(jī)器完工時(shí)間的平均情況，其廣義形式即最小化機(jī)器負(fù)載向量的lp范數(shù)成為近十年來的研究熱點(diǎn)之一。方便起見，稱此類問題為廣義的
計(jì)算機(jī)與生活 2016年8期2016-08-31
- 電力物資復(fù)合泊松需求下的最優(yōu)訂貨量
閉式算法； 近似算法電力生產(chǎn)具有高度連續(xù)性，生產(chǎn)與消費(fèi)同步意味著電力故障會(huì)對(duì)社會(huì)產(chǎn)生瞬時(shí)危害,而電力物資是電力生產(chǎn)運(yùn)行的保障。但是，電力企業(yè)物資管理普遍存在著匱乏和積壓的雙重現(xiàn)象：一方面，企業(yè)因物資儲(chǔ)備不足而無(wú)法確保需求發(fā)生時(shí)的及時(shí)供應(yīng)，產(chǎn)生高額缺貨成本和社會(huì)經(jīng)濟(jì)損失；另一方面，企業(yè)因物資儲(chǔ)備過量而導(dǎo)致積壓與腐蝕，造成大量資金浪費(fèi)。因此，電力物資的庫(kù)存控制對(duì)電力企業(yè)至關(guān)重要。然而，大多數(shù)電力物資呈間斷需求特性，即需求是隨機(jī)的且需求數(shù)據(jù)中存在著大量零值，這些
工業(yè)工程 2016年3期2016-07-14
- 社會(huì)網(wǎng)絡(luò)中弱關(guān)系團(tuán)隊(duì)形成問題研究*
確算法、α-近似算法，每類算法有各自的特點(diǎn)與適用范圍。利用ACM和DBLP兩類真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，綜合評(píng)估了各類算法的效率與求解質(zhì)量，證明了提出算法的有效性。關(guān)鍵詞：社會(huì)網(wǎng)絡(luò)；團(tuán)隊(duì)形成；弱關(guān)系；貪心算法；精確算法；近似算法ISSN 1673-9418CODEN JKYTA8Journal of Frontiers of Computer Science and Technology1673-9418/2016/10(06)-0773-13E-mail:f
計(jì)算機(jī)與生活 2016年6期2016-05-28
- 無(wú)線傳感器網(wǎng)絡(luò)虛擬骨干近似算法綜述
網(wǎng)絡(luò)虛擬骨干近似算法綜述張昭(浙江師范大學(xué)浙江金華321004)(hxhzz@sina.com)Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor NetworkZhang Zhao(ZhejiangNormalUniversity,Jinhua,Zhejiang321004)AbstractUsing virtual backbone in wireless s
計(jì)算機(jī)研究與發(fā)展 2016年1期2016-04-28
- 社會(huì)網(wǎng)絡(luò)中影響力傳播的魯棒抑制方法
小極大原理；近似算法；次模函數(shù)近年來，許多學(xué)者針對(duì)面向多信息源發(fā)布的信息全局傳播機(jī)制及其預(yù)測(cè)模型，以影響力傳播范圍及傳播速度最大化為目標(biāo)的關(guān)鍵結(jié)點(diǎn)集選取等問題開展了積極探索，并取得了一系列成果，極大地促進(jìn)了社會(huì)網(wǎng)絡(luò)影響力傳播機(jī)制問題的研究[1-7].然而，由于社會(huì)網(wǎng)絡(luò)本身具有開放性和虛擬性，各種不良、虛假信息、反動(dòng)言論可以跨地域、跨國(guó)界地散布和傳播，嚴(yán)重危害社會(huì)穩(wěn)定及國(guó)家安全.因此，為有效抑制萬(wàn)維網(wǎng)環(huán)境下社會(huì)網(wǎng)絡(luò)負(fù)面影響傳播，影響力傳播抑制問題也引起了學(xué)術(shù)
計(jì)算機(jī)研究與發(fā)展 2016年3期2016-04-27
- 具有多個(gè)受限制可用時(shí)間段的單機(jī)供應(yīng)鏈排序問題
并提出了2-近似算法。關(guān)鍵詞:可用時(shí)間段;供應(yīng)鏈排序;強(qiáng)NP-難;近似算法0 引言供應(yīng)鏈排序是把生產(chǎn)、分批和發(fā)送三者集成在一起,研究集成優(yōu)化的模型及其算法[1]。實(shí)際上,供應(yīng)鏈排序就是在排序決策范疇內(nèi)研究供應(yīng)鏈管理,是排序論在供應(yīng)鏈管理中的應(yīng)用。供應(yīng)鏈排序的第一篇論文是由Potts[2]于1980年發(fā)表的。2003年Hall和Potts[3]在論文中系統(tǒng)地提出了供應(yīng)鏈排序模型。此后,學(xué)者們對(duì)于供應(yīng)鏈排序問題的研究就越來越多了。本文研究的是兩階段供應(yīng)鏈排序問
上海第二工業(yè)大學(xué)學(xué)報(bào) 2016年1期2016-04-20
- 機(jī)器帶故障的三臺(tái)機(jī)排序問題的兩個(gè)近似算法
序問題的兩個(gè)近似算法葉賽英,徐弼軍(浙江科技學(xué)院 理學(xué)院，杭州 310023)摘要:機(jī)器帶故障的m臺(tái)機(jī)的目標(biāo)函數(shù)為最小化誤工工件數(shù)的排序問題，在m≥2時(shí)是NP(nondeterministic polynomial)困難的問題，對(duì)m=3，當(dāng)工件轉(zhuǎn)移時(shí)間t=0和t≠0兩種情況，提出了和的近似算法，以及對(duì)應(yīng)的漸進(jìn)性能比，且證明了其界是緊的。關(guān)鍵詞:排序；性能比；最小化誤工工件數(shù)；機(jī)器帶故障中斷；近似算法在經(jīng)典的平行機(jī)排序問題中，通常要求多臺(tái)機(jī)器性能完全相同，給
浙江科技學(xué)院學(xué)報(bào) 2016年1期2016-04-14
- 不確定數(shù)據(jù)的項(xiàng)集頻繁概率近似算法
項(xiàng)集頻繁概率近似算法陳鳳娟(遼寧對(duì)外經(jīng)貿(mào)學(xué)院 基礎(chǔ)課教研部,遼寧 大連 116052)研究在不確定事務(wù)數(shù)據(jù)庫(kù)中挖掘概率頻繁項(xiàng)集的問題，探討使用近似算法在不確定數(shù)據(jù)中的挖掘概率頻繁項(xiàng)集的方法.首先分析不確定數(shù)據(jù)庫(kù)與可能世界語(yǔ)言，然后介紹頻繁概率的概念，最后分析如何使用近似算法挖掘不確定數(shù)據(jù)庫(kù)中的概率頻繁項(xiàng)集. 從而降低運(yùn)行時(shí)間，提高算法效率.近似算法;不確定性;概率頻繁項(xiàng)集關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘重要的研究領(lǐng)域之一，它經(jīng)常應(yīng)用于購(gòu)物籃數(shù)據(jù)庫(kù)分析，從而發(fā)現(xiàn)顧客購(gòu)
許昌學(xué)院學(xué)報(bào) 2016年2期2016-04-14
- 無(wú)線傳感器網(wǎng)絡(luò)中的線段覆蓋問題
的多項(xiàng)式時(shí)間近似算法，并在理論上證明了該近似算法的性能比為18。關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；線段覆蓋；近似算法；性能比0引言無(wú)線傳感器網(wǎng)絡(luò)通過大量的廉價(jià)微型傳感器節(jié)點(diǎn)，采集并處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對(duì)象的信息，從而實(shí)現(xiàn)信息傳送的功能?；谖C(jī)電系統(tǒng)的微傳感技術(shù)和無(wú)線聯(lián)網(wǎng)技術(shù)為無(wú)線傳感器網(wǎng)絡(luò)賦予了廣闊的應(yīng)用前景，目前的應(yīng)用領(lǐng)域主要包括環(huán)境檢測(cè)、目標(biāo)跟蹤、醫(yī)療護(hù)理及軍事領(lǐng)域等。覆蓋問題是無(wú)線傳感器網(wǎng)絡(luò)中一類重要問題，在區(qū)域監(jiān)控和環(huán)境檢測(cè)等領(lǐng)域均有廣泛應(yīng)用[1]。區(qū)
- 一類新型網(wǎng)絡(luò)構(gòu)建問題的算法設(shè)計(jì)與分析
兩種情形時(shí)的近似算法，并證明算法的最壞情況界分別為和3。關(guān)鍵詞：網(wǎng)絡(luò)構(gòu)建；近似算法；最壞情況界；裝箱問題0引言1近似算法設(shè)計(jì)與分析1.1 CDP問題首先考慮CDP問題，即在有向圖D中尋找一條s-t有向路，使構(gòu)建該有向路所用的資源盡可能少。在算法中調(diào)用裝箱問題[3]的經(jīng)典算法——FFD作為子過程。對(duì)FFD算法，文獻(xiàn)[4]給出了如下性質(zhì)。針對(duì)CDP問題，設(shè)計(jì)了算法A1，算法A1的具體描述如下：1)利用Dijkstra算法[5]在網(wǎng)絡(luò)D中找到一條總權(quán)重最小的s-
- 旅行售貨員問題TSP的模擬退火算法
TSP問題的近似算法。關(guān)鍵詞： 旅行售貨員問題 NP-C 近似算法 模擬退火法 遺傳算法1.旅行售貨員問題（Traveling salesman problem）旅行售貨員問題（TSP）或稱為貨郎擔(dān)問題，可描述為：設(shè)有n個(gè)城市及表示城市i到城市j的距離D=|d■|，其中d■>0，d■=d■，并有d■+d■≥d■，且d■=0（i，j=1，2，3，…，n），一個(gè)貨郎從一個(gè)城市出發(fā)，不重復(fù)地遍歷所有城市并回到起點(diǎn)，求一條路程最短的路徑。這個(gè)問題已被證明是一個(gè)NP
考試周刊 2015年11期2015-09-10
- 一種大地坐標(biāo)變換近似算法
大地坐標(biāo)變換近似算法馬 娟，倪世道，任小葉(中國(guó)電子科技集團(tuán)公司第38研究所，合肥 230031)機(jī)載雷達(dá)數(shù)據(jù)處理系統(tǒng)需要頻繁使用大地坐標(biāo)變換算法將測(cè)量數(shù)據(jù)轉(zhuǎn)換到公共參考坐標(biāo)系下。針對(duì)精度要求相對(duì)較低但計(jì)算負(fù)載大的機(jī)載預(yù)警雷達(dá)系統(tǒng)，提出一種近似大地坐標(biāo)變換算法以解決常規(guī)算法計(jì)算復(fù)雜度大、需要迭代實(shí)現(xiàn)等問題。數(shù)值計(jì)算結(jié)果表明：文中所提算法精度損失較小，計(jì)算復(fù)雜度低。大地坐標(biāo)變換；近似算法；計(jì)算復(fù)雜度；精度0 引 言機(jī)載雷達(dá)系統(tǒng)中，載機(jī)處于運(yùn)動(dòng)狀態(tài)，雷達(dá)測(cè)量值
艦船電子對(duì)抗 2015年4期2015-03-25
- 計(jì)算樹的[1,2]-數(shù)的算法研究
]-數(shù)的兩個(gè)近似算法.最后,分析了兩個(gè)近似算法的計(jì)算復(fù)雜度和性能.[1,2]-數(shù);0-1規(guī)劃;貪婪策略;近似算法一個(gè)集合S?V(G)被稱為圖G的支配集(Dominating Set)[1],如果其滿足下面的條件:對(duì)圖G的任意的頂點(diǎn)v,或者屬于S或者與S中的頂點(diǎn)相鄰接.我們把頂點(diǎn)數(shù)目最少的支配集稱為圖的最小支配集(Minimum Dominating Set),它的頂點(diǎn)數(shù)目稱為圖的支配數(shù)(Dominating Number),記作γ(G).對(duì)于支配集S,若有
中國(guó)計(jì)量大學(xué)學(xué)報(bào) 2015年2期2015-03-23
- 自適應(yīng)交叉近似算法的核外計(jì)算方法
)自適應(yīng)交叉近似算法的核外計(jì)算方法吳君輝1,梁昌洪2,袁浩波2,曹祥玉3(1.空軍西安飛行學(xué)院,陜西西安 710300;2.西安電子科技大學(xué)天線與微波技術(shù)重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071;3.空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西西安 710077)為解決矩量法在計(jì)算電大目標(biāo)電磁特性時(shí)受計(jì)算機(jī)物理內(nèi)存限制的問題,設(shè)計(jì)了一種核外自適應(yīng)交叉近似算法.使用自適應(yīng)交叉近似算法有效地壓縮了阻抗矩陣,降低了所需存儲(chǔ)空間和計(jì)算量;并結(jié)合核外技術(shù),進(jìn)一步節(jié)省了內(nèi)存空間,提升了
西安電子科技大學(xué)學(xué)報(bào) 2014年5期2014-07-25
- 擬陣交構(gòu)約束的下模函數(shù)最大值問題的近似算法及其分析＊
立.2 給出近似算法及其性能保證OPT＝max｛f（S），S∈F｝，其中（E，F(xiàn)）是由m個(gè)擬陣的交構(gòu)成的獨(dú)立系統(tǒng).給出近似算法及其近似度分析，求解fS｜F的近似算法示意［5］如下：第1步 令i＝1，S0＝?，E0＝E；第2步 若Ei－1＝?，則停止計(jì)算；第3步 求ei∈Ei－1，使其滿足α·ρeij（Si－1）≥maxe∈Ei－1ρe（Si－1），α＞0；第4步 判斷Si－1∪ ｛ei｝是否屬于F；第5步 若Si－1∪ ｛ei｝不屬于F，則令Ei－1＝Ei
- 一種適于高光譜圖像壓縮的相關(guān)系數(shù)矩陣近似計(jì)算算法
相關(guān)系數(shù)矩陣近似算法由式（1）可知，相關(guān)系數(shù)矩陣的計(jì)算量巨大。對(duì)于一幅長(zhǎng)、寬和波段數(shù)分別為M、N 和K 的高光譜圖像，利用相關(guān)系數(shù)矩陣的對(duì)稱性減少一半的計(jì)算量之后，直接計(jì)算仍然需要5MNK2/2 次加法，3MNK2/2 次乘法，K2/2 次除法和K2/2 次開方運(yùn)算，難以滿足實(shí)時(shí)性的要求。首先考慮高光譜圖像空間分辨率較高時(shí)的情況。當(dāng)空間分辨率較高時(shí)，圖像中的一個(gè)像素與周圍像素會(huì)有著較強(qiáng)的相關(guān)性，也即意味著這些相似的像素對(duì)圖像相關(guān)系數(shù)矩陣的影響也是相似的。因
電子設(shè)計(jì)工程 2013年12期2013-10-21
- 多維背包約束下單調(diào)非減下模函數(shù)最大值的貪婪算法
的比較有效的近似算法。在求解組合最優(yōu)化問題的各種近似算法中，貪婪算法是最簡(jiǎn)單且最為有效的算法.Nemhauseretal 考慮了單背包約束下ci=1(i∈I)的特殊情形，給出了一種簡(jiǎn)單貪婪算法并證明了性能保證為1 - e-1。M.Suiridenko結(jié)合部分窮舉法與貪婪算法，給出了一般情形下單背包約束問題的一種改進(jìn)的貪婪算法，并證明了其性能保證為1 -e-1。在此將這種情況中的思想推廣到多維背包約束的情形，給出求解問題(1)的貪婪算法，并證明了所給算法的性
兵器裝備工程學(xué)報(bào) 2012年12期2012-07-09
- 旅行商問題圖論近似算法有效性分析
行商問題圖論近似算法有效性分析林農(nóng)(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)給出旅行商問題四種圖論近似算法及有效性分析，改進(jìn)第一種近似算法證明，修正第二、三、四種近似算法有效性的上界。旅行商問題;NP難題;圖論;近似算法;算法有效性旅行商問題是組合數(shù)學(xué)中著名的NP難題［1，2］，它在實(shí)際中有著廣泛而深入的應(yīng)用，在超大規(guī)模集成電路設(shè)計(jì)和路徑規(guī)劃都有重要應(yīng)用價(jià)值，它的計(jì)算復(fù)雜性研究在形成NP完全理論中起到奠基作用［3］。因而這幾年對(duì)它的研究一直是熱點(diǎn)
東莞理工學(xué)院學(xué)報(bào) 2012年1期2012-06-04
- 求解0－1背包問題的兩種方法的分析與比較
于貪心策略的近似算法求解KP問題，比較它們?cè)谇蠼馑俣扰c求解質(zhì)量方面的優(yōu)劣。在第2節(jié)中，給出0－1KP問題的數(shù)學(xué)模型，并介紹了一種可快速求解的2－近似算法；在第3節(jié)給出了利用動(dòng)態(tài)規(guī)劃法求解KP問題的完整算法描述，討論了其復(fù)雜度；隨后，通過仿真計(jì)算和復(fù)雜度分析對(duì)兩種方法進(jìn)行了比較，并利用3個(gè)較大規(guī)模實(shí)例與文獻(xiàn)［7］中的GDPSO進(jìn)行比較。最后，總結(jié)全文并展望下一步的工作。2 0－1KP問題及其近似算法背包問題的數(shù)學(xué)描述［1，5］為：設(shè)n個(gè)物品的價(jià)值集為C＝ ｛
河北省科學(xué)院學(xué)報(bào) 2012年3期2012-05-08
- 濃縮回收鈾的M級(jí)聯(lián)的近似算法
收鈾M級(jí)聯(lián)的近似算法。1 帶附加供料的M級(jí)聯(lián)的數(shù)學(xué)模型帶附加供料的M級(jí)聯(lián)（圖1）的外參量有主供料流F、附加供料流E、精料流P及貧料流W，相應(yīng)的組分豐度分別為CiF、CiE、CiP、CiW（i＝1，…，m，m為待分離同位素混合物的組分?jǐn)?shù)），級(jí)聯(lián)總級(jí)數(shù)為N。精料從第N級(jí)取料，貧料從第1級(jí)取料。此外，主供料從第f級(jí)供入，而附加供料從第l級(jí)供入。上述參量之間存在以下關(guān)系［7－8］：級(jí)聯(lián)總相對(duì)流量可通過下列關(guān)系式來計(jì)算［7－8］：式（1）～（5）中的gi是第i組分的
原子能科學(xué)技術(shù) 2011年12期2011-09-18