search算法

⑴ 线性规划(LP)基本概念和搜索算法

可以用一个符号描述一系列类似的数量值

一个方程，如果他是关于决策变量的常熟加权求和形式，则该方程式 线性方程(liner) ，佛则该方程为 非线性方程(non-linear)

目标函数 以及约束方程 中均为关于决策变量的线性方程，则该优化模型为 线性规划(linear program, LP) ，其中目标函数可以为满足约束的任意整数或者分数

目标函数 以及约束方程 中存在关于决策变量的线性方程，则该优化模型为 非线性规划(nonlinear program, LP) ，其中目标函数可以为满足约束的任意整数或者分数

一个优化模型，如果他的决策变量中存在离散变量，则该优化模型位 整数规划(integer program, IP) ，如果整数规划的所有决策变量均为离散变量，则该整数规划为 纯整数规划(pure integer program) ；否则为 混合整数规划(mixed integer program) 。

搜索算法(improving search) 通过检查邻域来寻找比当前更好地解，若有改进则替换当前解，继续迭代，直到邻域中没有更好的解为止。搜索算法又称为 局部改进(local improvement) ， 爬山算法(hillclimbing) ， 局部搜索(local search) 或 邻域搜索(neighborhood search)

倘若一组可行解周围足够小的的邻域内没有优于该解的可行点，则称为 局部最优解(local optimum) ，最小化(最大化)问题存在 局部最小(最大)解 。

如果在全局范围内不存在目标值优于某可行解的其他可行点，则称为 全局最优解(global optimum) ，最小化(最大化)问题存在 全局最小(最大)解

搜索算法沿 由当前点 向下一个搜索点 移动，其中 是当前点 处的 搜索方向(move direction) ， 是沿该方向前进的 步长 ， 。

对于所有足够小的 都有 ,则称 是当前解的一个 改进方向(improving direction) ,如果满足所有约束条件，则为 可行改进方向 。

如果优化模型的目标函数 是光滑的(所有决策变量都是可微的)，那么，当 是一个n维向量的函数，当它有一个一阶片倒数，这些导数组成的n维向量称为 梯度

导数(derivative) ，描述函数随参数的变化率，可以看做斜率。 偏导数(partial derivative) ，是保持其他变量恒定时，关于其中一个变量的导数

对于最大化目标函数 ,若 ，搜索方向 是 处的可改进方向，若 ，搜索方向 不是 处的可改进方向。

对于最小化目标函数 ,若 ，搜索方向 是 处的可改进方向，若 ，搜索方向 不是 处的可改进方向。

当目标函数梯度 ，是最大化目标 的一个改进方向， 是最小化目标函数 的一个改进方向

如果可行域内任意两点的连线都在可行域内，则称该可行域为 凸集 。

离散的可行集总是非凸集

若优化模型的可行集是凸集，那么对任意可行解始终存在指向另一个解的可行方向，意味着，只要存在最优解，可能性不会阻碍局部最优解发展为全局最优解。

线性约束的可行集又称为多面体集。

如果优化模型的所有约束都是线性的，那么该模型的可行域是凸集

两阶段法

大M法

⑵ 常见的搜索算法有哪几种

• 广度优先搜索（BFS）

• 深度优先搜索（DFS）

• 爬山法（Hill Climbing）

• 最佳优先算法（Best-first search strategy）

• 回溯法 （Backtracking）

• 分支限界算法（Branch-and-bound Search Algorithm）

⑶ 二分搜索算法是利用什么实现的算法

二分搜索算法是利用排除剩余元素中一半的元素实现的算法。

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索算法原理：

1、如果待查序列为空，那么就返回－1，并退出算法；这表示查找不到目标元素。如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。如果不相等，就再比较这两个元素的大小。

2、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

3、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

⑷ A*算法 和 最佳优先搜索算法（Best-First-Search）

最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。 BFS算法不能保证找到的路径是一条最短路径，但是其计算过程相对于Dijkstra
算法会快很多 。

最佳优先搜索是一种启发式搜索算法。广度优先搜索和深度优先搜索都属于穷举类型的搜索，需要依次遍历所有的节点，当空间非常大的时候，这种方式的效率就会非常差。而启发式的搜索是对状态控件中的每个点进行评估，然后选出最好的位置。

启发估价函数公式为：

n表示当前的点，g(n)为从起始点到点n的实际代价，h(n)为从点n到目标点的估价。

（图片来源于网络）

A*算法将BFS算法和Dijkstra算法结合在一起，结合两算法的优点，既可以查找最短路径的，有拥有和BFS差不多的效率。

（图片来源于网络）

A*算法详解

模拟寻路的地址

⑸ 选择性搜索算法 （Selective Search)

计算机视觉领域有几个基本的任务：

object detection 的基础是 object recognition，只不过要先将图片进行分割，对每个分割之后的子图区域 region （也称为 patch） 进行 object recognition.

由于事先并不知道物体在图片的哪个位置，为了避免漏检，我们应该对图片中尽量多的 region 进行搜索。理论上来说，可以有无穷多个 region。这里就需要一种 region proposal 的算法，以比较高效的方式提出图片划分 region 的方式，从而加速整个 object detection 的过程并且提高准确率。

本文将要介绍的 selective search 算法 ，是比较经典的，也是 R-CNN 中使用的 region proposal 算法。

参考文献：

为了避免蛮力搜索，selective search 算法首先需要一个基于像素的图像分割。这里用的是 Felzenszwalb and Huttenlocher 算法 （因为是当时速度最快的算法，而且是公开的），得到一个 oversegmented 的图像分割。例如：

这里之所以用 oversegmented 图像，是为了得到尽可能细分的区域，再以此为基础逐步合并，形成更大的区域。

image segmentation 可以用作 region proposal 的基础，每个分割的区域都可以看作一个潜在的 region，但是一个 object 往往包含了多个分割的区域，例如盛有咖啡的杯子，咖啡和杯子应该作为一个整体来看待。因此，还要根据某种相似性原则进行分割区域的合并，得到更大范围的 region。

Selective search 算法考虑了 4 种相似性度量，取值都在 [0,1] 之间，越大越相似。

最终的相似性度量是上述四个度量的组合：

其中 取 0 或 1.

总结起来，selective search 的算法步骤非常简单：

环境配置：

具体程序：

最后效果如下：

显示的 100 个 region 已经包含了我们感兴趣的待检测区域，说明了 selective search 算法的高效。

⑹ 使用STL通用算法remove()从list中删除元素

一些字符在STL容器中很好处理，让我们看一看一个难处理的字符序列。我们将定义一个list来放字符。
list<char>
Characters;
现在我们有了一个字符序列，它不用任何帮助就知道然后管理内存。它知道它是从哪里开始、到哪里结束。
它非常有用。我不知道我是否说过以null结尾的字符数组。
让我们加入一些我们喜欢的字符到这个list中：
Characters.push_back('\0');
Characters.push_back('\0');
Characters.push_back('1');
Characters.push_back('2');
我们将得到多少个空字符呢？
int
NumberOfNullCharacters(0);
count(Characters.begin(),
Characters.end(),
'\0',
NumberOfNullCharacters);
cout
<<
"We
have
"
<<
NumberOfNullCharacters
<<
endl;
MSDN中count()的用法稍微不一样.
这个是MSDN中count的定义
template<class
InIt,
class
T>
size_t
count(InIt
first,
InIt
last,
const
T&
val);
让我们找字符'1'
list<char>::iterator
Iter;
Iter
=
find(Characters.begin(),
Characters.end(),
'1');
cout
<<
"We
found
"
<<
*Iter
<<
endl;
这个例子演示了STL容器允许你以更标准的方法来处理空字符。现在让我们用STL的search算法来搜索容器中
的两个null。
就象你猜的一样，STL通用算法search()用来搜索一个容器，但是是搜索一个元素串，不象find()和find_if()
只搜索单个的元素。
/*
||
How
to
use
the
search
algorithm
in
an
STL
list
*/
#include
<string>
#include
<list>
#include
<algorithm>

int
main
(
void){

list<char>
TargetCharacters;
list<char>
ListOfCharacters;

TargetCharacters.push_back('\0');
TargetCharacters.push_back('\0');

ListOfCharacters.push_back('1');
ListOfCharacters.push_back('2');
ListOfCharacters.push_back('\0');
ListOfCharacters.push_back('\0');

list<char>::iterator
PositionOfNulls
=
search(ListOfCharacters.begin(),
ListOfCharacters.end(),
TargetCharacters.begin(),
TargetCharacters.end());

if
(PositionOfNulls!=ListOfCharacters.end())
cout
<<
"We
found
the
nulls"
<<
endl;
}
The
output
of
the
program
will
be
这是程序的输出：
We
found
the
nulls
search算法在一个序列中找另一个序列的第一次出现的位置。在这个例子里我们在ListOfCharacters中
找TargetCharacters这个序列的第一次出现，TargetCharacters是包含两个null字符的序列。
search的参数是两个指着查找目标的iterator和两个指着搜索范围的iterators。
因此我们我们在整个的ListOfCharacters的范围内查找TargetCharacters这个list的整个序列。
如果TargetCharacters被发现，search就会返回一个指着ListOfCharacters中序列匹配的第一个
字符的iterator。如果没有找到匹配项，search返回ListOfCharacters.end()的值。

⑺ 算法-二分搜索算法

算法：二分搜索算法（折半查找算法）
时间复杂度：

二分搜索算法，也称折半查找算法，即在一个有序数组中查找某一个特定元素。整个搜索过程从中间开始，如果要查找的元素即中间元素，那么搜索过程结束；反之根据中间元素与要查找元素的关系在数组对应的那一半查找，例如查找元素大于中间元素，则在整个数组较大元素的那一半查找，反复进行这个过程，直到找到元素，或者数组为空，查找不到元素。

给定一个数组 A_0,A_1...A_{n-1} ， A_0 \le A_1 \le \cdot \le A_{n - 1} ，待查找元素为 searchnum ：

BINARY-SEARCH-WHILE(A, searchnum, left, right)

BINARY-SEARCH-RECURSION(A, searchnum, left, right)

外部定义全局变量：

⑻ 【search】概述搜索排序算法的评价指标MAP,NDCG,MRR

【原文地址已失效，故粘贴于此】

By Eletva, eletva.com

我们知道，每个算法都有其评估的手段，借此用以指导当前算法模型的好坏，搜索rank是一个相对而言比较常见又比较特殊的场景，因为最后我们需要评估的是一个序列的好坏，是各个个体的相互关系，而不是大部分机器学习算法那样评估的是每个个体的处理好坏。因此，要深入了解搜索rank的机制，那么首先要知道我们是怎样来评估一种排序算法是好的算法，而另一种是不好的。本文中提到了三种评估的方式，都是有各自的试用场景。

因为搜索的意思形态不一样，可能采取的评估指标也可能会随之变化，以下提到的评估手段都可能是当用或者复用，要适当变之。。。

1. MAP（mean average precision）：

MAP的衡量标准比较单一，q(query，搜索词)与d(doc，检索到的doc)的关系非0即1，核心是利用q对应的相关的d出现的位置来进行排序算法准确性的评估，比如q1对应相关的d排名是1，2，5，7（假设q1有4个相关d），那么对于q1的ap（average precision）的计算就是（1/1+2/2+3/5+4/7）/4=ap1，对于q2的排序结果结果中与之相关的d的排名是2，3，6（假设q2有5个相关d），那么对于q2的ap就是（1/2+2/3+3/6+0+0）/5=ap2，那么这个排序算法的MAP就是（ap1+ap2）/2

MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就应该越高。如果系统没有返回相关文档，则准确率默认为0。

这里注意的是，在利用MAP的评估的时候，需要知道：1. 每个q有多少个相关的d; 2. 排序结果中这些d的位置 3. 相关的定义

延展：或许这个MAP可以进行部分改进，相关定义的部分可以考虑用0-1之间的系数来确定，而到实际使用中可以用ctr，gmv这些指标进行替换

2. 对于NDCG(Normalized Discounted Cumulative Gain)的理解

N指的是归一化，D指的是衰减率，C指的累加，G指的是熵，其实这个公式的关键就是就是熵，再多了三个形容词：归一化的，带有衰减函数的，再带有累加的熵即是了

仔细看一下上面的公司，停顿两分钟就可以体会其中的含义了

1）公式中最核心的Gain用一个指数函数来表示了，这与一般的信息熵的概念有些不一样，可能指代表着一个信息量的关系的变化，也许这说明熵是可以以任意形式出现的，anyway，这个还要再研究一下

2）那么接下去就是带有衰减因子的G，也就是DG了，用来表示与位置的衰减关系，因为排名越往后，那么说明越被点击的可能越小，因此越往后的衰减因子越小，实际操作中有很多衰减因子的定义函数，比如C*1/log(1+j)，上式子是指C为1的特殊形式， 其中C一般还会取值log2之类的一些经验值，这个都可以根据实际情况来进行变化（不过，我们应该清楚的认识到因为）

3）接着，就是累加，将带有衰减因子的熵进行累加，每个排名处进行累加

4）最后，是归一化，用当前的CDG/MAX，MAX即是理想状态下的CDG，那么就进行了归一化处理

总结：这里的相关性体现在Gain的计算处，r将相关性分成了多个档位，这里可以用实际操作中需要的指标去代替

3. MRR（mean reciprocal rank），倒数排序法

这个是最简单的一个，因为他的评估假设是基于唯一的一个相关结果，比如q1的最相关是排在第3位，q2的最相关是在第4位，那么MRR=(1/3+1/4)/2，MRR方法主要用于寻址类检索（Navigational Search）或问答类检索（Question Answering）

--------------------------------------------------------------------------------------------

另外谈到两个常见的算法指标的一些比较本质的东西，一个是Precision（准确率）与Recall（召回率）的关系，另一个是F-Measure，一个用来衡量P与R的指标

P与R之间的关系有些符合其齐夫定律，召回率和准确率分别反映了检索系统的两个最重要的侧面，而这两个侧面又相互制约。因为大规模数据集合中，如果期望检索到更多相关的文档，必然需要“放宽”检索标准，因此会导致一些不相关结果混进来，从而使准确率受到影响。类似的，期望提高准确率，将不相关文档尽量去除时，务必要执行更“严格”的检索策略，这样也会使一些相关的文档被排除在外，使召回率下降。

F-Measure：公式是基于P与R的调和平均数，1/[（1-lamda）*1/p+lamda*1/r), 一般lamda会取0.5，表示p与r的平衡，这里使用调和平均数而不是通常的几何平均或算术平均，原因是调和平均数强调较小数值的重要性，能敏感的反映小数字的变化，因此更适合用来反映算法效果。因为常常，一个指标比多个指标能够方便快捷的定位好坏。

⑼ 最佳优先搜索算法（Best-First-Search）

最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。BFS算法不能保证找到的路径是一条最短路径，但是其计算过程相对于Dijkstra算法会快很多。

n表示当前的点，g(n)为从起始点到点n的实际代价，h(n)为从点n到目标点的估价。

（1）BFS没有障碍物时的寻路

（2）BFS遇到障碍物时的寻路

结论：
（1）BFS算法通过估价函数，会将探测快速的导向目标点的方向，其不能够保证寻找到一条最短路径的点，但是其搜索的效率上相对于Dijestra算法会快上很多。
（2）在地图上有障碍物的情况，BFS寻找的路径一般都不是最短路径，在寻路过程中可以尝试配合其他的方法，对寻路进行修正。

⑽ 搜索算法的运算原理

搜索算法实际上是根据初始条件和扩展规则构造一棵“解答树”并寻找符合目标状态的节点的过程。所有的搜索算法从最终的算法实现上来看，都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。
由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。