最佳適應算法

最佳適應算法(Best Fit)它從全部空閒區中找出能滿足作業要求的、且大小最小的空閒分區,這種方法能使碎片儘量小。為適應此算法,空閒分區表(空閒區鏈)中的空閒分區要按從小到大進行排序,自表頭開始查找到第一個滿足要求的自由分區分配。該算法保留大的空閒區,但造成許多小的空閒區。


Best fit算法等價於裝箱問題,舉例如下:
裝箱問題:有體積為V的箱子N個,體積為Vi的物品M個,求使得物品全部能夠裝入箱子,箱子數量的最小值。
假設 V=6 M=10,V1,V2,...,V10分別為:3 4 4 3 5 1 2 5 3 1。計算過程如下:
第一步按物品體積降序排序:5 5 4 4 3 3 3 2 1 1
第二步:取未裝箱的最大值5裝入第一個箱子。
第三步:判斷第一個箱子是否已滿,不滿且剩餘空間為1,搜尋剩下體積小於等於1的物品填入箱子1,箱子1填滿。
第四步:重複第二,第三步,直到所有物品裝入箱子為止,得到箱子數量為6.
6即時本例N的最小值。

相關詞條

相關搜尋

熱門詞條

聯絡我們