科学技术与工程
科學技術與工程
과학기술여공정
SCIENCE TECHNOLOGY AND ENGINEERING
2014年
17期
150-154
,共5页
BWC问题%启发式算法%局部搜索%禁忌表
BWC問題%啟髮式算法%跼部搜索%禁忌錶
BWC문제%계발식산법%국부수색%금기표
BWC problem%heuristic algorithms%local sarch algorithms%tabu list
无向图的BWC着色问题是给定两个正整数b和w,判断是否存在这样的着色方案:对b个顶点着黑色,对w个顶点着白色,其它顶点不着色,着黑色顶点集合与着白色顶点集合之间没有任何边相连.BWC的最优化问题,是找出一种最优化着色方案,使得与所有黑色顶点不相连接的着白色顶点数最大.该问题被证明是NP-完全问题.提出了一种基于禁忌表和局部搜索机制的混合启发式算法(BTLSBWC),通过对部分网络图进行测试,结果达到了现有文献计算出的最好值.
無嚮圖的BWC著色問題是給定兩箇正整數b和w,判斷是否存在這樣的著色方案:對b箇頂點著黑色,對w箇頂點著白色,其它頂點不著色,著黑色頂點集閤與著白色頂點集閤之間沒有任何邊相連.BWC的最優化問題,是找齣一種最優化著色方案,使得與所有黑色頂點不相連接的著白色頂點數最大.該問題被證明是NP-完全問題.提齣瞭一種基于禁忌錶和跼部搜索機製的混閤啟髮式算法(BTLSBWC),通過對部分網絡圖進行測試,結果達到瞭現有文獻計算齣的最好值.
무향도적BWC착색문제시급정량개정정수b화w,판단시부존재저양적착색방안:대b개정점착흑색,대w개정점착백색,기타정점불착색,착흑색정점집합여착백색정점집합지간몰유임하변상련.BWC적최우화문제,시조출일충최우화착색방안,사득여소유흑색정점불상련접적착백색정점수최대.해문제피증명시NP-완전문제.제출료일충기우금기표화국부수색궤제적혼합계발식산법(BTLSBWC),통과대부분망락도진행측시,결과체도료현유문헌계산출적최호치.
