如何使用算法解决问题
计算复杂问题关于是不是难解的边界问题,可以从上图我们可以知道算法大概包含三个主要内容,以及一些概念。下面说一下,如何使用算法求解的流程。
算法解决问题思路
这里举一个例子:
调度的问题
从这问题中,通过直觉感觉到耗时少的放到前面可以达到最优,这样是一种贪心的策略
然后,我们可以找到规律,一个任务执行多次与它所在的位置有关系(下面的目标函数构建)。接下来对抽象的问题建模。
接下来如何验证我们的假设对不对呢
我们举了两个情况,一个时间长的任务放到前面,另一个时间长的任务放到后面,比较他们的大小。跟我们直觉相一致。
但有时候直觉不一定可靠,如下面的问题:
这里仍然使用贪心的方法去解
我们找到了反例也就是另一种最优解。可以理解,重量与价值,不一定具有相关性,所以这种贪心的策略不对。
通过上例,可以总结出如何设计算法:
投资问题(组合优化的问题)
建模设置一个向量记录选用项目的金额,目标函数当然让效益最大啦,当然也要让对项目投资金额小于总钱数。
下面以穷举为例计算一下复杂度:
可行解(也就是上面说的记录选用项目的金额的向量),比如我们选择金额<1,2,3,1>,依次是第1,2,3,1的项目;将金额使用0、1表示这样使可行解序列化,也就是说1的个数相加始终为7(总金额),使用3个0来拆分1,这样可以确定选择了4个项目的金额(比如<1,2,3,1>,0不能位于首尾,要不然拆分的不是4个项目。。)
m个1,n-1个0所以有m+n-1个位置。我们把m个位置放1,也就是求它的组合数。epsilon>0,所以是指数函数,复杂度高。