0%

上节回顾

线性可分情况下,支持向量机寻找最佳超平面的优化问题可以表示为:

线性不可分情况

如果训练样本集是线性不可分的,那么以上优化问题的解,是什么呢?

image-20220117215519369

在稍微思考下,以上的问题,是没有解的。

即:不存在 $ \omega \ 和 \ b$ 满足上面所有的 $ N $ 个限制条件。

对于线性不可分的情况,我们要适当的放松限制条件。使上面的最优化问题变得有解。

阅读全文 »

0-1背包问题-动态规划

一、问题描述

image-20211228120109039

给定n种物品和一个背包。物品i 的重量是 w_i ,其价值是v_i ,背包的容量为c 。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

阅读全文 »

活动安排问题-贪心

一、贪心

贪心算法是通过一系列的选择来得到一个问题的解,而它所做的每一次选择都是当前状态下的最好选择,即贪心选择。

即希望通过问题的局部最优解来求出整个问题的最优解。

阅读全文 »

查找第K小问题-分治

选择问题(select problem)是指在n个元素的集合中,选出某个元素值大小在集合中处于第k位的元素,即所谓的求第k小元素问题(kth-smallest)。

当k=1时,是求最小元素;而当k=n时,就是求最大元素;当k=(n+1)/2时,称为中位数。

阅读全文 »

最长公共子序列问题-动态规划

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X={x1,x2,…,xm},则另一序列Z={z1, z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1, i2,…, ik}使得对于所有j=1,2,…, k,有: zj=xij。例如,序列Z={B,C, D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。

给定两个序列X和Y,当另一个序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。

阅读全文 »