《2022年2022年购物单问题的回溯搜索算法分析与研究 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年购物单问题的回溯搜索算法分析与研究 .pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、购物单问题的回溯搜索算法分析与研究李绵梁（陕西师范大学，西安，710062）摘要：购物单问题是一个典型的0-1 背包问题。而 0-1 背包问题是算法分析设计中的经典问题， 本文通过回溯搜索算法来解决购物单问题，并对该算法时间复杂度进行理论上和实际上的分析比较。关键词：购物单问题0-1 背包回溯搜索一、问题描述：小明被评为省级三好学生， 妈妈决定奖励他N元。小明就开始做预算， 但是他想买的东西太多了， 肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 15表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元） 。他希望在不超过N元的前提下，使每
2、件物品的价格和重要度的乘积的总和最大。设第 j 件物品的价格为 vj，重要度为 wj ，共选中了 k 件物品，编号依次为 j1 ，J2, ,jk,则所求总和为 :Vj1*wj1+vj2*wj2+vjk*wjk 请你帮小明设计一个满足要求的购物单。二、算法分析与数学建模：假设：所买的东西都是独立的，即没有相互间的依赖关系。则对于每一件物品而言， 只有买或不买两种情况， 而物体本身也不可分， 并且所买物体总数受总钱数所限，目标为所求重要性1尽可能大。因此，该问题是一个典型的 0/1 背包问题！推广到一般，对于n 件物品，假设对其进行依次编号1，2，3， n，不妨将第i件物品购买状况记为fi(fi=
3、0,1),即将购买第i件物品记为fi=1，不购买记为 fi=0，则通过分析不难得出，该问题的数学模型为：1. 重要性：本文定义为物体重要度与价格的乘积。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 从算法复杂性理论来看，该问题是一个NP 问题。而目前，对该类问题的解决方法也是非常多的，主要包括分支限界法、群举法、图论法、贪心算法、蚁群算法等。本文作者用回溯搜索算法对问题进行求解与分析讨论。在题目约束条件（总价格不超过N 元）的
4、前提下，对问题解空间构成的树进行回溯搜索。在遍历过程中，只有当前物品需要购买时（值为1） ，才需要进行购买后价格是否超过总N 元的判断，若不超过，才需要进行更深的搜索；若判断购买后总价格大于N 元，则无需进行更深的搜索。三、算法实现在算法实现过程中需要增加辅助变量如下：记录物品重要性、价格分别为数组w 、v ；记录总钱数为 tm。在每次搜索过程中， 记录当前搜索结果的当前最大重要性、当前花费钱数分别为 cmax、total，当前最大重要性下对物品的取舍情况t；记录每次搜索对物品的取舍状态数组sign；设计回溯搜索的核心算法如下：void www(int i) / 从第 i 层开始 ; int
5、j; float sum=0; / 当前分支重要性总和if (i=n+1) / 到达叶结点 for (j=0;jcmax) cmax=sum; / 更改重要性for (j=0;jn;j+) tj=signj; return; ),2, 1( 1 ,0wMax11kiifNifivifivikiki，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - signi-1=0; / 未到叶节点，不买第i 件物品时 ; www(i+1); i
6、f (total+vi-1=tm) / 可买第 i 件物品的情况; signi-1=1; total+=vi-1; www(i+1); signi-1=0; total-=vi-1; / 回溯之前清理现场; 四、算法复杂度分析1.理论分析在搜索过程中，对于不同的N，算法进行搜索的情况都不同。但该算法需要搜索的问题解空间共有2n 个分支，因此，算法时间复杂度为O(2n)。2.实际分析对实验进行统计，其统计结果如表一所示：表一：实际实验时间复杂度数量 n2345678时间 t11.85877 1.88387 2.16217 2.44537 3.15822 5.59405 7.94152 时间 t2
7、1.69044 1.81702 2.10872 2.37360 3.12712 5.56921 8.35889 时间 t31.64233 1.88512 2.11097 2.22727 3.15479 5.61848 7.82389 时间 t41.64858 2.00136 2.03537 2.32861 3.14016 5.61588 7.76655 时间 t51.68078 1.92825 2.04190 2.33903 3.037 5.76224 7.79614 平均时间 1.70418 1.903124 2.091826 2.342686 3.123458 5.631972 7.937
8、398 3.理论与实际的比较对理论情况与实际实验情况的结果进行对比，其时间复杂度图一所示。图一：理论与实际时间复杂度对比图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 由以上图示可以看出， 实验理论时间复杂度与实际复杂度结果近似相似，因此可以说明该算法是正确的。五、结论0/1 背包问题有许多算法，本文作者只是用回溯搜索算法对问题进行解决，并根据实际实验复杂度与理论实验复杂度进行详细比较，来判断讨论出实际算法的正确性。本文只是用一种算法对问题进行解决是很局限的，也未能够通过对不同算法时间复杂度的比较而得出更进一步的结论，在今后的学习研究中， 这点将会得到解决。【参考文献】1. 吕国英 . 算法设计与分析（第二版）. 清华大学出版社2. 王晓东 . 算法设计与分析 . 清华大学出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -