常見算法及問題場景—

最短路徑

現實場景

1、一批貨從北京到廣州的的最快，或最省錢的走法。?
把路線中各城市當作圖的頂點，各城市之間的花費時間，或金錢當作邊的權重，求兩點之間的最短路徑。?
2、在城市群中建一個倉儲基地，建在什么位置可以讓各個城市的送貨速度都比較快。?
同1，把各城市間的送貨速度當作邊的權重，求倉儲基地到各城市間的最短路徑。

算法

1、Dijkstra，單源最短路徑。?
2、Floyd，兩點最短路徑。?
參考鏈接：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

社區發現

現實場景

用于社交網絡中的社區（或話題）發現，基本特點是，社區之間聯系稀疏，社區內部聯系緊密。如，給定新浪微博的用戶關系數據，找出其中的的社區，以及核心節點。

算法

標簽傳播、主要特征向量、多層模塊度、隨機游走、邊介數等幾個系列算法。

各算法的優劣，有一個評價體系，即計算其 Modularity Measure(模塊化度量值）。?
具體的算法介紹，及Modularity Measure值計算，可以參考這里：http://blog.csdn.net/itplus/article/details/9286905?
關于Fast Unfolding更詳細的介紹，可以參考這里：http://blog.csdn.net/google19890102/article/details/48660239

網絡評價

現實場景

現實中存在各種的網絡：社區聚集、好友關系、電力網、交通網等，網絡特點各不相同，計算機科學上，把這些現實網絡劃分為隨機網絡、小世界網絡、規則網絡、無標度網絡等多種抽象的網絡模型，用網絡模型去解釋現實網絡。并定義了一套可量化的標準特征來描述各種網絡模型。

概念

1、平均路徑長度。路徑長度，是指網絡中任意兩節點之間的最短路徑。平均路徑長度是指所有節點之間的平均最短距離。?
2、網絡直徑。網絡中所有節點之間的最大路徑長度。?
3、度分布。度，是指網絡結構中與某節點相連接的邊的數目為該節點的度。社交網絡中度數較多的節點通常是公眾人物。?
網絡中各個的節點度的分布情況就為度分布，如泊松分布、二項分布等。?
4、介數。節點的介數，指經過該節點的最短路徑占整個網絡所有最短路徑的比例。如，社交網絡中的某些關鍵人物。?
5、接近中心度。一個節點通過最短路徑到達其它節點的難易程度。對于網絡中的邊緣節點，其接近中心度會比較小。如，偏遠城市，社交網絡中的非主流人物。?
6、Clustering coefficient（聚集系數）。主要衡量一個節點的鄰節點之間的連接情況，鄰節點之間連接越多，聚集系數越大。?
7、網絡密度。網絡中節點固定情況下，邊數量越多，則密度越大，即節點之間聯系更緊密。?
8、互惠指數。即有向網絡中的無向程度。

K-Core

現實場景

社交網絡中，有一批KOL存在，他們的影響力遠超普通大眾。

算法

關于K-Core的詳細解釋，及其算法實現，可以參考這里：網絡節點度、H指數與核數之間的優美關系（http://blog.sciencenet.cn/blog-3075-950475.html）

二分圖匹配

現實場景

1、通過數代人的努力，你終于趕上了剩男剩女的大潮，假設你是一位光榮的新世紀媒人，在你的手上有N個剩男，M個剩女，每個人都可能對多名異性有好感，請為他們兩兩配對，最大程度減少剩男剩女個數。?
2、有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？

算法

1、匈牙利算法?
2、任務分配問題一般可以在多項式時間內轉化成最大流量問題（Maximum Flow Problem）

匈牙利算法參考文章：http://blog.csdn.net/dark_scope/article/details/8880547

二分圖匹配問題轉最大流問題的方法可參考這里：?
http://blog.csdn.net/caipeichao2/article/details/35306659

最小費用、最大流

現實場景

1、從城市A到城市B之間運輸一批貨物，中間路過多個城市，有多條路線可供選擇，兩兩城市之間的運輸費用不等，找出一條費用最小的路線。?
2、把一批快遞經由鐵路由城市A運到城市B，中間路過多個城市。在做任意兩個城市間的鐵路線上可運送的物資數量是有限的，我們要考慮使鐵路線承載量最大，不讓鐵路資源閑置，同時讓快遞運輸時經過更多的城市，以承攬更多快遞業務。如果把鐵路網上的車站看作是圖的頂點，兩個車站間的鐵路線看作是圖的邊，把任意兩城市間的鐵路線上的允許最大運送量稱為容量。這就是一個經典的求網絡最大流問題。

概念

1、邊權重的意義。不同場景下，每條邊的值有不同的意義，問題1中，邊的權重為費用，問題2中，邊的權重為剩余容量。?
2、增廣路徑。在圖中，可能存在多條從源點到目標點的可行路徑，每一條都是一條增廣路徑。最小費用、最大流問題就是找到多條增廣路徑中滿足最小費用、最大流條件的一條。

算法

1、最小費用問題可轉化為求最短路徑問題。?
2、Edmond-Karp算法。?
可參考文檔：http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html?
3、Ford-Fulkerson算法。?
可參考文檔：http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117636.html

最大連通子圖

現實場景

1、計算機網絡中的病毒通常會基于一種病毒存在多種變種病毒，變種病毒與原病毒之間大部分代碼相似。因此，把兩種病毒之間的函數調用關系用圖表示出來，分析其最大連通子圖是否相似，就可以判斷是否變種病毒。?
2、圖像分割中，尋找圖像的最大連通域。

概念

最大連通子圖。是指把圖劃分為N個子圖后，子圖內所有節點相連，子圖間沒有節點相連。這N個子圖就是原圖的最大連通子圖。

歐拉回路

現實場景

1、七橋問題。?
2、去北京動物園瀏覽，能否設計一條這樣的路線：既可以游遍所有景點，又不走重復路。

概念

1、歐拉回路。是指，通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點的通路(回路)稱為歐拉通路(回路)。?
2、滿足特定條件的圖才能稱為歐拉圖。

算法

Fleury算法

哈密頓回路

現實場景

導游帶團北京一日游遍，需要設計一條路線，可以走遍所有景點，且只走一次。

概念

1、哈密頓回路。在一個圖中，由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。?
2、哈密頓回路并不一定存在。?
3、屬NP完全問題，難以在有效時間內找到解決方案。

最小生成樹

現實場景

1、在電路設計中，常常需要把一些電子元件的插腳用電線連接起來。如果每根電線連接兩個插腳，把所有n個插腳連接起來，只要用n-1根電線就可以了。在所有的連接方案中，我們通常對電線總長度最小的連接方案感興趣。?
2、要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，找出一條使用最短的光纖連通這些城市的鋪設方法。

算法

1、Prim算法?
2、Kruskal算法

拓撲排序

現實場景

1、一個大工程，通常由多個任務組成，這些子工程之間有的有依賴關系，有的沒有，假設同時只能做一個任務，請排出一個順序來。?
2、一個計算機專業的學生必須完成一系列課程才能畢業。如學習《數據結構》課程就必須安排在學完它的兩門先修課程《離散數學》和《算法語言》之后。學習《高等數學》課程則可以隨時安排，因為它是基礎課程，沒有先修課。