查詢結果分析
來源資料
相關文獻
- A New Algorithm for the Minimax/Maximin Cut
- 層級分析法的圖形一致性與目標規劃法
- 以加入圖形一致性限制的對數最小平方法求解AHP權重
- Pairwise Interchange for Scheduling Dependent Data
- Applying Hashing Search and Fuzzy Fault-Tolerant Algorithms for the Fast Recognition of Multi-Font Printed Chinese Characters
- 海上搜索與救難
- 具互動功能的使用者操作介面GUI
- 對電腦資訊之搜索與扣押
- 「國內歷史學學術期刊排序計畫」簡介
- 應用高階相關法於表格文件之辨識
頁籤選單縮合
題 名 | A New Algorithm for the Minimax/Maximin Cut=Minimax/Maximin切割之新演算法 |
---|---|
作 者 | 葉維彰; | 書刊名 | 逢甲學報 |
卷 期 | 38 2000.12[民89.12] |
頁 次 | 頁95-103 |
分類號 | 440.11 |
關鍵詞 | 圖形; Minimax/maximin切割; 排序; 搜索; Graph; Min-cut/max-flow; Maximin/minimax cut; Search; Sort; |
語 文 | 英文(English) |
中文摘要 | 原始Minimax/Maximin切割問題係求一切割集,使得此一邊子集合中之最大/小權值最小/大化。於本研究中,我們不僅尋找Minimax/Maximin割集,同時更進一步要求此一割集之總權值為最小,故先描述現存方法如何求解此一問題,接著結合排序、二元搜索與圖形 搜索以開發新的解法。本演算法與由Corley所提出且為目前最佳之演算法相比較,不但較有效率,而且更為簡易。同時,若要求Minimax/Maximin割集之總權值為最小時,則本法時間複雜度,亦僅與目前用於求解另一著名且為圖論之基本問題:Max-flow/Min-cut問題之最佳演算法相同。最後將以兩個範例說明本演算法之可行性與效率性。 |
英文摘要 | The original minimax/maximin cut problem is to find a cutset to minimize/maximize the maximal/minimal weight edge in this cutset. In this paper, we first introduce a stronger definition of the minimax/maximin cut problem such that the total weight in the minimax/maximin cut is also minimized, and describe how an existing method solves this problem. A more efficient algorithm that combines sorting, binary search and graph search is then presented to find the minimax/maximin cut. The time complexity of this algorithm is better than those realized by the existing best known algorithms which is proposed by Corley. Moreover, if the total weight should be minimized, the the complexity of our algorithm is as good as the best known algorithm for the min-cut/max-flow problem. Finally, two examples are given to demonstrate this new algorithm. |
本系統中英文摘要資訊取自各篇刊載內容。