计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2012年
8期
2168-2171,2175
,共5页
多维多选择背包问题%核%分支定界%整数线性规划%组合优化
多維多選擇揹包問題%覈%分支定界%整數線性規劃%組閤優化
다유다선택배포문제%핵%분지정계%정수선성규화%조합우화
针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核.首先论述了如何在一般背包问题中获得核；接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并利用三种备选方案得出MMKP的核,亦即子空间.第一种方案是基于观察数据E[lc]和E[d∞]比较小来得到核；第二种方案基于基本解和最优解的曼哈顿距离不算太远来实施；第三种方案是为所有元素定义一个全序并取第一组k元素作为核.比较了这三种方案的不同与优劣,结果表明:第一种方案比其他两种方案无论从定义子空间的精度和枚举时间平均值上,性能都更优越,利用该方案定义的核能高效解决MMKP.
針對目前尚無多維多選擇揹包問題(MMKP)高效覈算法的現狀,提齣用多種方法來構造處理這種類型揹包的覈.首先論述瞭如何在一般揹包問題中穫得覈；接著根據事先設定的度量指標詳細討論瞭MMKP的基本解和兩種排序關繫,併利用三種備選方案得齣MMKP的覈,亦即子空間.第一種方案是基于觀察數據E[lc]和E[d∞]比較小來得到覈；第二種方案基于基本解和最優解的曼哈頓距離不算太遠來實施；第三種方案是為所有元素定義一箇全序併取第一組k元素作為覈.比較瞭這三種方案的不同與優劣,結果錶明:第一種方案比其他兩種方案無論從定義子空間的精度和枚舉時間平均值上,性能都更優越,利用該方案定義的覈能高效解決MMKP.
침대목전상무다유다선택배포문제(MMKP)고효핵산법적현상,제출용다충방법래구조처리저충류형배포적핵.수선논술료여하재일반배포문제중획득핵；접착근거사선설정적도량지표상세토론료MMKP적기본해화량충배서관계,병이용삼충비선방안득출MMKP적핵,역즉자공간.제일충방안시기우관찰수거E[lc]화E[d∞]비교소래득도핵；제이충방안기우기본해화최우해적만합돈거리불산태원래실시；제삼충방안시위소유원소정의일개전서병취제일조k원소작위핵.비교료저삼충방안적불동여우렬,결과표명:제일충방안비기타량충방안무론종정의자공간적정도화매거시간평균치상,성능도경우월,이용해방안정의적핵능고효해결MMKP.
