精华内容
下载资源
问答
  • 一维装箱问题的解决

    2015-03-04 13:58:39
    利用遗传算法解决一维装箱问题,并利用matlab实现
  • 一维装箱问题

    2021-02-17 17:08:47
    问题描述 二、 算法介绍及实现 注:(1)以下的文字表达中,桶 == 箱子, 空间 == 容量; (2)每个算法对应的程序默认读取所有测试文件并计算结果与耗时; () 直接法 按照给定物品的顺序,判断当前桶能否...

    Bin Packing Problem

    一、 问题描述

    在这里插入图片描述
    在这里插入图片描述

    二、 算法介绍及实现

    注:(1)以下的文字表达中,桶 == 箱子, 空间 == 容量;
    (2)每个算法对应的程序默认读取所有测试文件并计算结果与耗时;

    (一) 直接法
    按照给定物品的顺序,判断当前桶能否装下当前物品,如果不能,则新开一个桶并将物品放入该桶中,接着便从该桶开始判断能否装下下一个物品(不再回头看前面的桶)。
    这个算法是最简单也是最快的方法,但基本上对问题没有什么优化,效果不佳。

    时间复杂度:O(n)
    代码实现:

    //算法一   
    #include<stdio.h>  
    #include<vector>  
    #include<ctime>  
    using namespace std;  
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);  
            vector<int> items(numItems);  
            int numBuckets = 1, remain = capacity;  
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &items[i]);  
                if (remain > items[i]) remain -= items[i];  
                else {  
                    numBuckets++;  
                    remain = capacity - items[i];  
                }  
            }  
            end = clock();  
            printf("test file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    
    

    (二) First Fit
    按照给出物品的顺序,维护一个桶的数组(用vector实现),每次从列表头开始依次向后遍历每一个桶,直到找到一个可以存放当前物品的桶,如果所有桶都不能满足,则新开一个桶并加到列表中去,并将当前物品放在这个桶中。
    可以证明First Fit算法的结果不会超过最优结果的两倍。证明如下:
    在这里插入图片描述

    时间复杂度:O(n*log(n))

    代码实现:

    //算法二  
    #include<stdio.h>  
    #include<vector>  
    #include<ctime>  
    using namespace std;  
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);  
            vector<int> items(numItems);   
            vector<int> buckets{capacity};//动态增长的桶数组   
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &items[i]);  
                int j = 0;  
                for (; j < buckets.size(); ++j) {  
                    if (buckets[j] > items[i]) {  
                        buckets[j] -= items[i];  
                        break;  
                    }  
                }   
                if (j == buckets.size()) buckets.push_back(capacity - items[i]);  
            }  
            end = clock();  
            printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    

    (三) 排序+First Fit
    将物品按照重量(Wj)从大到小排序,然后按First Fit算法的做法放入物品。
    从最大的物品开始放的好处是最大化的利用空间。假设这样一种情况:桶的容量c是10,有三个物品的重量分别为4、1、6,如果按照物品这样的顺序将它们放入桶中,那么第一个桶会装下前两个物品,剩余容量5,第二个桶会装下最后一个物品,剩余容量4,;而如果先排序再放,那么第一个桶可以放下6和4,剩余容量0,第二个桶会放下1,剩余容量9。显然排序后的放法使得空间的利用率更大,如果这时要放第四个物品,只要物品重量超过5,第一种放法就要开第三个桶,而只有物品重量超过9第二种放法才需要开第三个桶。
    另一个直观的理解是:先放大的物品,之后小的物品更有机会可以放到之前已经放有物品的桶中,也更有机会将桶填满或几乎填满;反过来,如果小的物品放在同一个桶中,剩余的大的物品又不能共同放入一个桶中,只能各开一个桶了,这就会产生很多剩有空间的桶,而这时可能已经没有小的物品可以用来填充了。

    但这种算法不是最优的。还是举个例子,假设桶的容量还是10,现在有两个桶,分别存放了重量和为6、7的物品(注意每个桶中可能不止一件物品),然后接下来还有三个重量依次为3、2、2的物品要放入桶中,按照这个算法,最终会变成三个桶,分别是9、9、2,而最优放法应该是两个桶分别为10、10的。由于在放一个物品时无法考虑到后面的情况,只是找到第一个合适的位置便放,所以这个算法不是最优的。

    时间复杂度:O(n*log(n))
    代码实现:

    //算法三   
    #include<stdio.h>  
    #include<vector>  
    #include<ctime>  
    #include<algorithm>   
    using namespace std;  
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);  
            vector<int> items(numItems);   
            vector<int> buckets{capacity};//动态增长的桶数组   
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &items[i]);  
            }  
            sort(items.begin(), items.end(), [](int a, int b) {  
                return a > b;  
            });  
            for (int i = 0; i < numItems; ++i) {  
                int j = 0;  
                for (; j < buckets.size(); ++j) {  
                    if (buckets[j] > items[i]) {  
                        buckets[j] -= items[i];  
                        break;  
                    }  
                }   
                if (j == buckets.size()) buckets.push_back(capacity - items[i]);  
            }  
            end = clock();  
            printf("Ttest_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    

    (四) 元启发式算法(Greedy)
    还是先将物品按重量从大到小排序,也还是维护一个桶的数组,不过这次不用First Fit,而是遍历所有桶,找到最合适的桶将物品放入。如果所有桶都不能满足,则新开一个桶并加到列表中去,并将当前物品放在这个桶中。
    这种算法属于元启发式中的greedy范畴,一开始结果集合是空的,通过一步步构造来获得一个可行解。
    这里需要定义什么是“最合适的桶”,最合适的桶需要满足以下条件:

    1. 该桶有剩余的空间存放当前的物品
    2. 与其他满足条件1的桶相比,该桶放入该物品后剩余的空间最小
      简述以下条件2的合理性:选择放入该物品后剩余的空间最小的桶,从直观上讲,放入的那个桶的利用率是较高的;另一方面,没有被选择放入该物品的其他满足条件1的桶的剩余空间相比被选择的桶在放入物品之前的剩余空间要大,这使得接下来的物品能被放入已有的桶中的可能性较大。

    时间复杂度:O(n2)
    代码实现:

    //算法四   
    #include<stdio.h>  
    #include<vector>  
    #include<ctime>  
    #include<algorithm>   
    using namespace std;  
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);  
            vector<int> items(numItems);   
            vector<int> buckets{capacity};//动态增长的桶数组   
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &items[i]);  
            }  
            sort(items.begin(), items.end(), [](int a, int b) {  
                return a > b;  
            });  
            for (int i = 0; i < numItems; ++i) {  
                int j = 0, choose = -1;  
                for (; j < buckets.size(); ++j) {  
                    if (buckets[j] > items[i] && (choose == -1 || buckets[j] < buckets[choose]))   
                        choose = j;  
                }   
                if (choose == -1) buckets.push_back(capacity - items[i]);  
                else buckets[choose] -= items[i];  
            }  
            end = clock();  
            printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    

    (五) 遍历物品依次装填箱子1
    还是现将物品按重量从大到小排序,不过不同于前面算法,前面的算法都是对每一个物品遍历所有桶直到找到合适的桶,这个算法反过来,对每一个桶遍历所有物品,遇到重量小于桶的剩余容量的物品则将其装入桶中,直到桶不能再放下任何其他一个物品为止。每一轮装填一个桶,直到所有物品都被装入桶中为止。
    前面的算法中存放物品的数据结构一般用数组即可,而在这个算法中,物品不再按照顺序被取出,可能会取出列表中某一个位置的物品,所以用数组的话当数据量比较大时删除的开销较大,用链表list会比较合适。
    这个算法中由于只需考虑当前的桶,所以无需再维护一个桶的动态数组。
    同样的,先装大的物品有利于提高空间利用率,而提高空间利用率往往也意味着需要用到更少的桶。

    时间复杂度:O(n*log(n))
    代码实现:

    //算法五   
    #include<stdio.h>    
    #include<vector>   
    #include<ctime>    
    #include<algorithm>  
    #include<list>    
    using namespace std;    
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {    
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;    
            start = clock();    
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);    
            list<int> items;    
            int item;  
            int remain, numBuckets = 0; //当前桶剩余的容量,桶的总个数   
            for (int i = 0; i < numItems; ++i) {    
                fscanf(file, "%d", &item);   
                items.push_back(item);  
            }    
            items.sort([](int a, int b) {    
                return a > b;    
            });    
            list<int>::iterator it;  
            while(!items.empty()) {  
                remain = capacity;  
                for (it = items.begin(); it != items.end(); ) {  
                    if (*it < remain) {  
                        remain -= *it;   
                        if (remain < items.back()) break;//如果桶连最小的物品都放不下,那么就没有可以继续放下的物品了  
                        it = items.erase(it);   
                    }  
                    else ++it;  
                }  
                numBuckets++;  
            }  
            end = clock();    
            printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);    
        }     
    }  
    
    

    (六) 遍历物品依次装填箱子2(大小搭配/双指针)
    如果物品们的重量由大到小分布较为均匀的话,可以尝试使用这个算法。
    依然是遍历物品装填箱子,对于每一个待装填的箱子,我们不再是从头遍历所有物品,而是先取出当前列表中最大的物品,接着取出当前列表中最小的物品,将它们放在同一个箱子中,然后由小到大判断这个箱子是否还能装下其它物品。
    使用这样的装箱方法是有原因的,就像高斯在计算1加到100时运用的两端分别相加的方法一样,我们可以期望大和小的搭配可以使得每个箱子都达到或接近被填满。

    时间复杂度:O(n*log(n))
    代码实现:

    //算法六   
    #include<stdio.h>  
    #include<vector>  
    #include<ctime>  
    #include<algorithm>   
    using namespace std;  
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int main() {  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            int numItems, capacity;  
            fscanf(file, "%d%d", &numItems, &capacity);  
            vector<int> items(numItems);   
            int remain, numBuckets = 0; //当前桶剩余的容量,桶的总个数   
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &items[i]);  
            }  
            sort(items.begin(), items.end(), [](int a, int b) {  
                return a > b;  
            });  
            int left = 0, right = items.size() - 1;  
            while (left <= right) {  
                remain = capacity;  
                remain -= items[left++];  
                while(left <= right && remain > items[right]) remain -= items[right--];  
                numBuckets++;  
            }  
            end = clock();  
            printf("test_file: %s, used %d bucket, running time: %lf seconds\n", path[t], numBuckets, ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    

    (七) 模拟退火
    不同于算法四中的贪心算法,模拟退火是一个迭代的元启发式算法。简单地说,模拟退火是针对在Local Search中可能产生的局部优化作了修改,不像Local Search只选择更好的值作为下一个状态,模拟退火在高温时会有比较大的可能接受比当前值差的值,直到低温时才逐渐趋于稳定。这样就有效避免了看不见“一山更比一山高”的情况。
    首先要有一个初始的状态,即每个物品分别被放到哪个桶中。可以用直接法的结果作为初始状态,选这个的原因是它比较简单,而且比较有优化的空间。
    然后问题就来了,如何由当前状态产生下一个状态?如何判断当前状态与下一个状态哪个比较好?
    如果目标函数是根据当前状态计算桶的个数,会有很多种状态计算的结果相同,这些状态之间又该如何比较?
    简单起见,状态的比较可以考虑以下四种方案:

    1. 目标函数是根据当前状态计算桶的个数,如果有相同的结果,随机选择一个
    2. 结合广度搜索,目标函数是根据当前状态计算桶的个数,如果有相同的结果,按比例随机选择几个进行递归,取最好的结果。
    3. 目标函数分为两部分,分别计算当前状态对应的桶的个数,以及物品的分布均匀程度。比较两种状态时先比较桶的个数,如果桶的个数相同,则选择分布比较不均匀的一种状态。因为分布比较不均匀代表着有的桶装得多有的桶装得少,那么这些桶之间可能就可以合并。
    4. 与(3)差不多,不过桶个数相同时选择分布比较均匀的状态。

    状态的切换则考虑以下两种方案:

    1. 选择一个桶,将其中的一个物品放到另一个桶中
    2. 选择两个桶,彼此间交换一个物品

    综上,确定这样一个算法:

    1. 使用直接法的结果作为初始状态
    2. 每次迭代中随机选择一个桶,将其中的一个物品放到另一个合适的桶中(物品的放置采用First Fit),作几次这样的操作,选择其中最好的状态与当前状态比较。如果其中最好的状态比当前状态差,且概率上没有被选择,这样的情况连续出现多次则结束迭代,当前状态为最终结果。
    3. 状态间的比较采用第三种方案,计算分布均匀程度可以通过先计算每个桶存放物品的重量与平均桶存放物品的重量的差的绝对值,然后求所有桶的这个值的平均数来表示。这个平均数越大则说明分布越不均匀。
    4. 对不好的状态是否采用根据温度来判断,采用的概率为
      e-t/T
      t是一个预先定义好的常数。(控制采用的概率在0.01~0.4之间)
    5. 温度在每次迭代时乘以一个小于1的系数,当温度低于某个值时结束迭代

    代码实现:

    #include<stdio.h>  
    #include<vector>  
    #include<time.h>  
    #include<stdlib.h>   
    #include<numeric>  
    #include<math.h>  
    #include<numeric>  
    #define NEIGHBOUR_COUNT 20  
    #define MAX_NO_CHANGE 10  
    using namespace std;  
      
    const double T = 500, T_min = 100, dec_rate = 0.999;//初始温度,最低温度和下降的乘系数  
    const double divider = 450.0;   
    const char path[17][30] = {"Data/Waescher_TEST0005.txt", "Data/Waescher_TEST0014.txt", "Data/Waescher_TEST0022.txt", "Data/Waescher_TEST0030.txt", "Data/Waescher_TEST0044.txt", "Data/Waescher_TEST0049.txt", "Data/Waescher_TEST0054.txt", "Data/Waescher_TEST0055A.txt", "Data/Waescher_TEST0055B.txt", "Data/Waescher_TEST0058.txt", "Data/Waescher_TEST0065.txt", "Data/Waescher_TEST0068.txt", "Data/Waescher_TEST0075.txt", "Data/Waescher_TEST0082.txt", "Data/Waescher_TEST0084.txt", "Data/Waescher_TEST0095.txt","Data/Waescher_TEST0097.txt"} ;   
    int sum;//物品重量和  
    int numItems, capacity;//物品数量,桶容量   
    //计算当前状态对应的桶的均匀分布程度
    double get_avg(vector<vector<int>>& buckets) {  
        double aavg = (double)sum / buckets.size();  
        double temp = 0;  
        for (vector<int> bucket : buckets) {  
            temp += abs(accumulate(bucket.begin(), bucket.end(), 0) - aavg);  
        }  
        return temp / buckets.size();  
    }  
    //将下标为from的桶中某一个元素移动到其他桶中,产生邻居状态
    vector<vector<int>> do_change(vector<vector<int>> buckets, int from) {  
        int random = rand() % buckets[from].size();  
        int j = 0;  
        for (; j < buckets.size(); ++j) if (j != from){  
            if (capacity - accumulate(buckets[j].begin(), buckets[j].end(), 0) > buckets[from][random]) {  
                //printf("from %d's %d ", from, buckets[from][random]);  
                //printf("to %d\n", j);  
                buckets[j].push_back(buckets[from][random]);  
                break;  
            }  
        }   
        if (j != buckets.size()) {//物品顺利地放到其它桶中   
            buckets[from].erase(buckets[from].begin() + random);  
            if (buckets[from].empty()) buckets.erase(buckets.begin() + from);  
        }  
        return buckets;  
    }  
    int main() {  
        srand((int)time(NULL));  
        for (int t = 0; t < 17; ++t) {  
            clock_t start, end;  
            start = clock();  
            FILE* file = fopen(path[t], "r");  
            fscanf(file, "%d%d", &numItems, &capacity);  
            int item;//临时的item变量   
            vector<vector<int>> buckets{{}};  
            int remain = capacity;   
            //按照直接法得到初始状态   
            sum = 0;  
            for (int i = 0; i < numItems; ++i) {  
                fscanf(file, "%d", &item);  
                sum += item;  
                if (remain > item) {  
                    remain -= item;  
                    buckets.back().push_back(item);  
                }  
                else {  
                    remain = capacity - item;  
                    buckets.push_back({item});  
                }  
            }  
            //初始状态已经存在buckets里  
            //开始迭代    
            double temperature = T;  
            int count = 0;  
            int no_change = 0;  
            while(temperature > T_min) {//达到最低温即退出   
                count++;  
                int bucket_count = buckets.size();  
                double average = get_avg(buckets);  
                vector<vector<int>> next_best;//选择最好的下一个状态   
                for (int i = 0; i < NEIGHBOUR_COUNT; ++i) {  
                    int next_best_count = next_best.size();  
                    double next_best_average = get_avg(next_best);  
                    int from = rand() % buckets.size();  
                    vector<vector<int>> res = do_change(buckets, from);  
                    //计算修改后的状态对应的桶的个数、分布均匀程度  
                    int count = res.size();  
                    if (i == 0 || count < next_best_count || count == next_best_count && get_avg(res) > next_best_average) {  
                        next_best = res;  
                    }  
                      
                }  
                //将最好的下一个状态与当前状态比较  
                int next_best_count = next_best.size();  
                if (next_best_count < bucket_count ||   
                    next_best_count == bucket_count && get_avg(next_best) > average) {  
                        no_change = 0;  
                        buckets = next_best;  
                    }  
                      
                //如果最好的下一个状态比当前状态差,则根据概率决定是否选择下一个状态  
                else {  
                    double rate = exp(-divider / temperature);  
                    int random = rand() % 100;  
                    if (random < rate * 100) {  
                        buckets = next_best;  
                        no_change = 0;  
                    }  
                    else if (++no_change > MAX_NO_CHANGE) break;  
                }  
                temperature *= dec_rate;  
                  
                   
            }   
            end = clock();  
            printf("iteration count: %d, temperature: %f\n", count, temperature);  
    //      for (vector<int>& vec : buckets) {  
    //          count += vec.size();  
    //          for (int it : vec) printf("%d ", it);  
    //          printf("\n");  
    //      }  
              
            printf("test file: %s, used %d buckets, running time: %lf seconds\n", path[t], buckets.size(), ((double)end - start) / CLK_TCK);  
        }  
    }  
    
    

    三、 算法结果分析与比较

    在这里插入图片描述

    从总体上看,这些数据有点太弱,导致除了模拟退火算法其它算法的运行时间都没有达到1毫秒,所以时间上没法怎么比较,唯一的办法可能就是对同一数据重复计算10次、100次取其时间和,这里就不做了。
    而且由于给出的数据中物品重量默认是从大到小排好序的,所以排序与否对结果没有什么影响。
    主要作以下几组比较:
    (一) 算法一与算法二
    可以发现,First Fit算法显然是优于直接法的,这与预期相符,因为First Fit充分利用了前面已经装填过物品的桶的剩余空间。

    (二) 算法二和算法三
    如前面所说,由于给出的数据本身就是排好序的,所以这两个算法的结果相同。
    (三) 算法三与算法四
    在所有测试用例中两种算法的结果都相同,这与预期不太相同,我们预期中算法四是要更优于算法三的,因为它选择能放下物品的剩余容量最小的桶,提高了利用率。不过可能是给出的数据没有出现在算法三中讨论到的情况,所以体现不出算法四的优势。

    (四) 算法三与算法五
    这两个算法分别从不同的角度切入问题,算法三是按物品的顺序放的,而算法五是按桶的顺序放的,两者各有千秋,不过从给定数据的结果来看,算法三似乎比算法五略好一些。

    (五) 算法五与算法六
    同样是按桶的顺序放置物品,不同的地方是算法五只有一个指针从左往右扫描物品,算法六则有两个指针分别从两端向中间扫描。
    从时间复杂度上看显然是算法六更好的,因为它是线性复杂度。
    从给定数据的运行结果上看,大多数时候是算法五更好,但也有算法六比较好的情况(在图中用黄色背景标出的部分)。

    (六) 算法七与其他算法
    从结果上看,算法七(模拟退火)的结果与算法二相同。
    模拟退火在迭代次数较少时结果具有不确定性,我通过增加每次迭代的可选邻居状态数量和减少温度下降的速率来增加迭代次数,发现最终的结果会趋于一个稳定值,不再随参数的改变而改变,这个值与算法二产生的值相同。所以我估计算法二对于这些测例产生的结果应该是很接近于最优解的。
    因为多次迭代以及许多函数调用,所以算法七运行时间会比其他算法长。

    另外,由于对算法七中比较两个状态好坏时用均匀分布程度为依据只是直接地推论,并没有严密的证明,所以我专门做了一个对比实验。分别在桶个数相同的情况下选择均匀分布程度较高和较低的状态,两种情况作比较,结果发现选择均匀分布情况较低的状态的算法最终产生的结果是比较好的,这也在某种程度上证明了算法七的正确性。

    展开全文
  • 回复: 求一维装箱问题的 MATLAB算法 没人回复,还是我自己来吧用MATLAB的话,循环会比较慢,还是考虑c++以下是我参考别人的一段代码,希望对大家有帮助,也是我们做数模时使用的代码# include # include typedef ...

    icon1.gif 回复: 求一维装箱问题的 MATLAB算法

    没人回复,还是我自己来吧

    用MATLAB的话,循环会比较慢,还是考虑c++

    以下是我参考别人的一段代码,希望对大家有帮助,也是我们做数模时使用的代码

    # include

    # include

    typedef struct ele

    { int vno;

    struct ele *link;

    } ELE;

    typedef struct hnode

    { int remainder;

    ELE *head;

    Struct int hnode *next;

    } HNODE;

    void main()

    { int n, i, disk_count, disk_volume, *a;

    HNODE *disk_h, *disk_t, *j;

    ELE *p, *q;

    Printf("输入软盘容量\n");

    Scanf("%d",&disk_volume);

    Printf("输入文件个数\n");

    Scanf("%d",&n);

    A=(int *)malloc(sizeof(int)*n);

    Printf("请按文件大小从大到小顺序输入各文件的文件大小:");

    For (i=0;i

    Disk_h=disk_t=NULL;

    Disk_count=0;

    For (i=0;i

    { p=(ELE *)malloc(sizeof(ELE));

    p->vno=i;

    for (j=disk_h;j!=NULL;j=j->next)

    if (j->remainder>=a[i]) break;

    if (j==NULL)

    { j=(HNODE *)malloc(sizeof(HNODE));

    j->remainder=disk_volume-a[i];

    j->head=NULL;

    if (disk_h==NULL) disk_h=disk_t=j;

    else disk_t=boix_t->next=j;

    j->next=NULL;

    disk_count++;

    } 4

    else j->remainder-=a[i];

    for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);

    if (q==NULL)

    { p->link=j->head;

    j->head=p;

    }

    else

    { p->link=NULL;

    q->link=p;

    }

    }

    printf("共使用了%d个软盘",disk_count);

    printf("各软盘装文件情况如下:");

    for (j=disk_h,i=1;j!=NULL;j=j->next,i++)

    { printf("第%2d个软盘,还剩余容量%4d,所装文件有;\n",I,j->remainder);

    for (p=j->head;p!=NULL;p=p->link)

    printf("%4d",p->vno+1);

    printf("\n");

    }

    }

    __________________

    :水榭焚香听琴事,浪荡江湖不系舟:

    smile.gif

    感谢请点thanks

    展开全文
  • 一维装箱问题的多种解法(含源码)

    千次阅读 2020-09-03 11:42:20
    实验总结与心得 best-fit不是最优解,一维装箱不具有”最优子结构”,局部最优之和不等于全局最优;worst-fit也不是最差解,反而在小物品较多的装箱问题中有着更好地表现,以前是被名字误导,没有窥探其中的本质 ...

    源码网址
    普通算法(ascend算法一般不常用,原因见下写在前面)

    • First-fit、First-fit-descend、First-fit-ascend
    • Best-fit、Best-fit-descend、Best-fit-ascend
    • Worst-fit、Worst -fit-descend、Worst -fit-ascend
    • Next-fit、Next -fit-descend、Next -fit-ascend
    • DP

    元启发式算法

    写在前面
    descend/ascend就是对应先把物品进行降序/升序的排序再进行装箱,下文不再赘述。

    其中ascend有个优点是下一个物品不需要遍历每个箱子,只需要检查存放上一个物品的箱子是否有足够的空间(之前的箱子连上一个较小的物品都放不下,所以不用考虑)即可,这样执行效率会比较高,但是结果出来发现需要的箱子较多,经过测试思考后发现descend算法是后面的物品有更高的概率把之前的箱子填满(也不一定要填满,就是更可能放入之前的箱子),空间利用率较高,而FFA算法后来的箱子一般都放不进原来的箱子,所以导致空间利用率低。比较适合箱子容量较大,而物品普遍较小的情况。

    对上述解释没有概念的同学可以试试15 14 9 9 8 8 7 7 6 6 55 6 6 7 7 8 8 9 9 14 15两种顺序的装箱(箱子容量为20)

    普通算法

    1. First-fit、First-fit-descend、First-fit-ascend
      对每个物品遍历当前箱子,把物品放入第一个能放下该物品的箱子,都放不下则新开一个箱子。

    2. Best-fit、Best-fit-descend、Best-fit-ascend
      对每个物品遍历当前箱子,把物品放入最合适放下该物品的箱子(即min(箱子容量-物品体积)),都放不下则新开一个箱子。

    3. Worst-fit、Worst -fit-descend、Worst -fit-ascend
      对每个物品遍历当前箱子,把物品放入最不合适放下该物品的箱子(即max(箱子容量-物品体积)),都放不下则新开一个箱子。

    4. Next-fit、Next -fit-descend、Next -fit-ascend
      查资料时发现的一个算法,原理为当处理一个物品的时候,检查当前箱子容量是否足够;如果足够,就将物品放入当前箱子,如果不足,就重新开辟一个新的箱子。

    5. DP
      把装箱问题看作背包问题,其中cost和value都是每个物品的体积(或质量),对每个背包尽可能地装满,然后记录装过地物品并去掉,直到所有物品装完。

    元启发式算法

    1. Simulated Annealing
      模拟退火是一种Greedy算法,但是它的搜索过程引入了随机因素rand(注意加入时间种子保证随机性)。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出局部的最优解,达到全局的最优解。

    2. Tabu Search
      为了找到全局最优解,禁忌搜索标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程,从而或得更多的搜索区域。

    3. Genetic Algorithm
      遗传算法是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

    结果及分析

    算法时间复杂度分析
    First-fit、First-fit-descend、First-fit-ascendO(nlogn)比较符合人的思维习惯,效果也较为良好,适合处理一般的中小型数据集
    Best-fit、Best-fit-descend、Best-fit-ascendO(nlogn)对比BF和WF,其实BF和WF都是FF的变种,没有太大的优劣之分,BF就是把剩余空间从小到大排序,WF就是把剩余空间从大到小排序。
    Worst-fit、Worst-fit-descend、Worst-fit-ascendO(nlogn)总体而言,BF较适合大物品比较多的任务(因为小任务多时经常不能填满),而WF适合小物品比较多的任务
    Next-fit/Next-fit-descend、Next-fit-ascendO(n)/O(nlogn)最直接的方法,虽然效率较高但是效果较差,像上述算法一样随便做点优化都能在稍微牺牲效率的情况下获得较好的结果提升,所以一般不常用。
    DPO(nlogn)纯属一个突然的思维拓展,想到用01背包的处理方法将一个背包尽可能地装满后再装下一个,其实上述算法除了NF之外都是这样的思想,不过是换了一种方法实现,虽然结果尚可,但是效率太低,不适用于解决装箱问题(应该有更好的实现暂时还没有想到)
    算法分析
    Simulated-Annealing自定义参数较多,对参数控制不熟悉且程序引入随机数,本身具有一定随机性,多次调整参数并尝试后才得到跳出局部最优的一个优于普通算法的result,由于需要自控制迭代次数,迭代次数一般都设置较大,所以时间效率方面一般
    Tabu Search也有些自定义参数和随机性,不知道是不是参数设置的原因,比起模拟退火更容易跳出局部最优得到优于一般算法的解,时间效率方面也优于模拟退火
    Genetic-Algorithm是本实验中结果表现最优的算法,由于是基于种群的启发式算法,所以遗传和选择时处理的数据量较大导致时间效率一般,但是由于其丰富的遗传规则和较大的测试数量所以更容易跳出局部最优

    五. 实验总结与心得

    1. best-fit不是最优解,一维装箱不具有”最优子结构”,局部最优之和不等于全局最优;worst-fit也不是最差解,反而在小物品较多的装箱问题中有着更好地表现,以前是被名字误导,没有窥探其中的本质

    2. 升序排序是自己突然想到的,一考虑时间效率还以为是什么灵感大爆发,真正结果出来才知道原来降序是为了在填充过程中尽可能地塞满每个箱子,而升序则没有这种原理地体现,还是自己欠考虑了,包括DP也是,果然对于这种研究了几十上百年的问题老前辈们把能想的基本都想到了,难怪都看不到升序算法,再一次体会到了求学之路上的”任重而道远”

    3. 对于元启发式算法,都是具有一定的随机性的筛选,具体计算还是要结合普通算法。对于模拟退火和禁忌搜索等有较多自定义参数的要多尝试才能得出较好结果。在查找资料时发现一个很形象的总结摘录如下:

    为了找出地球上最高的山,一群有志气的兔子们开始想办法:

    • 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法,它不能保证局部最优值就是全局最优值。
    • 兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火
    • 兔子们知道一个兔的力量是渺小的。他们互相转告着,哪里的山已经找过,并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索
    • 兔子们吃了失忆药片,并被发射到太空,然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子,多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法
    展开全文
  • BRKGA解决一维装箱问题 用于一维箱装箱问题的有偏随机密钥遗传算法(BRKGA)的实现。 使用的BRKGA框架是由Toso,RF和Resende,MG(2012)开发的。 用于有偏随机密钥遗传算法的C ++应用程序编程接口。 技术报告,AT...
  • 问题描述We have a number of bins each with a capacity of 1, and we have a set of objects all with different sizes, s1,s2,…,sn between 0 and 1. What is the fewest number of bins that would be needed ...

    问题描述

    We have a number of bins each with a capacity of 1, and we have a set of objects all with different sizes, s1,s2,…,sn between 0 and 1. What is the fewest number of bins that would be needed to store all of the objects?

    Instance: 0.5, 0.7, 0.3, 0.9, 0.6, 0.8, 0.1, 0.4, 0.2, 0.5

    一维装箱问题只考虑一个因素,比如重量、体积、长度等。


    思路一

    要求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子信息。
    我们先将物品由大到小进行排序,每次拿出一个物品从第一个箱子开始遍历:如果可以放下,那么重新拿出一个物品在从第一个开始遍历;如果放不下,就开一个新箱子,将这个物品放在里面。


    思路二

    还是先将物品由大到小进行排序,每次拿出一个箱子遍历物品,遍历完一次物品就表示一个箱子装满了,然后再开下一个箱子,直到所有的物品装完为止。对于上述题目,既然只需要求出所需箱子的数量,个人认为就没必要用更复杂的数据结构了。
    初学算法,这个完全是自己写的,感觉还有待优化,思路一的代码也会尽快完成,出现问题望指正。

    //箱子类
    class Box {
        static int MAX_SIZE = 10;
        int id = 0;
        int size;
        int[] store;//记录箱子里装入的物品
    
        Box(int n) {
            store = new int[n];
        }
    }
    
    
    public class BinPacking {
    
        private int[] goods;
    
        private BinPacking(int[] goods) {
            this.goods = goods;
        }
    
    
    //    将Good按照size由大到小排序
        private void sort(int[] goods) {
            for (int i = 0; i < goods.length; i++) {
                for (int j = 1; j < goods.length - i; j++) {
                    if (goods[j - 1] < goods[j]) {
                        int temp = goods[j];
                        goods[j] = goods[j - 1];
                        goods[j - 1] = temp;
                    }
                }
            }
        }
    
    
    //    用于判断是否全部物品已经装完
        private int sum(int[] goods) {
            int sum = 0;
            for (int good : goods) {
                sum += good;
            }
            return sum;
        }
    
    
    //    装箱过程
        private void binPacking() {
            sort(goods);
    
            Box box = new Box(goods.length);
    
            while (sum(goods) != 0) {
                box.id++;//箱子id从1开始
                box.size = Box.MAX_SIZE;
                for (int j = 0; j < goods.length; j++) {
                    box.store[j] = 0;
                }//存储清零,相当于开一个新箱子
    
                for (int i = 0; i < goods.length; i++) {
                    while (goods[i] == 0) {
                        if (i == goods.length - 1)
                            break;
                        i++;
                    }//跳过已经装入的物品
    
                    if (goods[i] <= box.size) {
                        box.size -= goods[i];
                        box.store[i] = goods[i];//将已装入的物品存在Box类的store[]中
                        goods[i] = 0;
                        if (box.size == 0)
                            break;
                    }
                }
    
    //            一次遍历结束,打印结果
                System.out.println("第" + box.id + "个箱子装入质量为:");
                for (int j = 0; j < goods.length; j++) {
                    if (box.store[j] != 0) {
                        System.out.print(box.store[j] + " ");
                    }
                }
                System.out.println();
    
            }
            System.out.println("最少需要" + box.id + "个箱子");
        }
    
    
        public static void main(String[] args) {
            int[] goods = {5,  7,  3,  9,  6,  8,  1,  4,  2,  5};
            BinPacking b = new BinPacking(goods);
            b.binPacking();
        }
    
    }
    展开全文
  • 《多目标一维装箱问题模型算法研究》 计算机应用研究/2020 1 一维装箱问题模型 2 模型求解算法设计 在经典的一维装箱问题中,由于假设箱子的容量(或体积)相 同,所以在目前所采用的算法中绝大多数都是...
  • 维装箱问题程序

    2019-01-27 00:48:38
    作为三维装箱问题种工程应用,集装箱装载问题(Container Loading Problem,CLP)通常是指如何将一些小尺寸货物按照某种方式装入集装箱中。集装 箱装载质量的好坏,直接影响着企业运输成本的高低。如何给出个...
  • 有一些物品,需要将这些物品装到箱子中,求装箱情况,那么我们应该思考如何装箱装箱时要遵循什么样的准则。
  • 2018华为软件挑战赛赛题中装箱部分的解答代码,可以作为尺寸成倍数关系的一维装箱问题解决方式的参考
  • 30代表需要装箱物品的个数,即A列表数字的个数。A列表的数字代表每个物品的体积。 ; margin-right:0pt">  <ol><li>将Excel A列表中的数在Python中读取(代码中需要用到M)后,按照从大到...
  • This project originates from my bachelor thesis in computer science at the University of Paderborn. It deals with a library for two dimensional packing problems (which arise for example in leather cut...
  • 针对梯形箱子的三维装箱问题,提出了种基于空间分割的构造性启发式算法,根据梯形箱子三维装箱问题的特点,设计了相应的空间分割策略、空间合并策略与空间重组策略,在此基础上加入遗传算法,提高算法局部与全局...
  • 27、一维装箱

    2019-06-06 20:29:30
    from pyscipopt import Model, quicksum from vtk import * import vtk ...#BFD(Best fit decreasing):区别于FFD,能装下则找个合适的,合适的定义可以是装完后的那个箱子装载率最高 def BFD(boxs, ...
  • 有无限多个箱子,每个箱子容量为V,有N件物品,每件体积分别为v1, v2 ,…, vn (0≤V),求能容纳这个N件物品的最少箱数。
  • 装箱问题,贪心算法求近似最优解import java.util.Arrays;import java.util.Comparator;//装箱问题,贪心算法public class Enchase {public void test1() {Integer[] boxs={34,6,40,2,23,12,12};int boxCaptation=40...
  • 问题的定义装箱问题(Bin packing problem),又称集装优化,是个利用运筹学去解决实际生活的的经典问题。在维基百科的定义如下:In the bin packing problem, items of different volumes must be packed into a ...
  • 基于matlab求解三维装箱优化问题 二、源代码 close all; clear; clc; %% set data Dbox = [10, 10, 10]; Dobj = [1, 1.5, 1; 1, 1.5, 1]; PobjI = [7, 5, 5, 0, 0, 0; 3, 5, 5, 0, 0, 0]; PobjD = [3, 3, -3, 0...
  • 维装箱问题是具有广泛应用背景的类组合优化问题 ,这类问题是 NP难问题 ,很难得到精确解 。将二维装箱问题表示为个非线性规划模型 ,用变分分析中切锥的概念建立了这优化问题的一阶最优性条件 。给出了求解这...
  • 基于改进粒子群算法的三维装箱优化研究,杨志强,牛占文,本文提出种适用于求解三维装箱问题的改进粒子群优化算法。该算法在简化粒子群优化算法的基础上,引入小生境技术实现初始种群的
  • 恰好最近领导指派设计款类似库房管理的软件,其中涉及到零售商库房商品打包出库的部分,刚好碰到商品装箱问题。将思路和大家分享,如有不妥,望及时指正,可联系QQ或者直接留言。(二) 背景及业务叙述顾客下完订单...
  • 题目描述有个箱子容量为V(正整数0≤V≤20000),同时有n个物品(0要求nn个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。输入输出格式输入格式:1个整数,表示箱子容量1个整数,表示有n个物品接下来n行,...
  • 种二维装箱问题的建模方法

    千次阅读 2020-08-27 15:06:18
    模型参数 参数 说明 I I I 物件的集合 W W W 箱子的宽度 H H H 箱子的高度 w i w_i wi​ 物件 i i i 的长边 h i h_i hi​ 物件 i i i 的短边 决策变量 变量 类型 说明 p i p_i pi​ 0-1 物件 i i i 是否被装箱 x i x...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,012
精华内容 3,204
关键字:

一维装箱问题