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）。