學(xué)習(xí)安排（8月16日-8月20日）
1.主要學(xué)習(xí)視頻Week6
鏈接（http://www.xuetangx.com/courses/MITx/6_00_2x/2014_T2/courseware/d39541ec36564a88af34d319a2f16bd7/）
2.參考書第十二章--背包與圖的最優(yōu)化問題

解決問題時(shí)，如果涉及求最大怔蚌、最小、最多幅聘、最少窖贤、最快怎囚、最低價(jià)格等情況捉撮，那么你就非常有可能將這個(gè)問題轉(zhuǎn)換為一個(gè)典型的最優(yōu)化問題灾梦，從而使用已知的計(jì)算方法進(jìn)行解決。最優(yōu)化問題通常包括兩部分：

• 目標(biāo)函數(shù)：需要最大化或最小化的值槐雾。例如夭委，波士頓和伊斯坦布爾之間的飛機(jī)票價(jià)。
• 約束條件集合（可以為空）：必須滿足的條件集合募强。例如旅行時(shí)間的上界株灸。

背包問題

假設(shè)竊賊有一個(gè)背包，最多能裝20磅贓物钻注，他闖入一戶人家蚂且，發(fā)現(xiàn)圖1中的物品。很顯然幅恋，他不能把所有物品都裝進(jìn)背包，所以必須確定拿走哪些物品泵肄，留下哪些物品捆交。他需要找出一組能夠帶走的價(jià)值最高的東西淑翼。

物品表

貪婪算法

對(duì)于這個(gè)問題，找出近似解的最簡(jiǎn)單方法就是貪婪算法品追。竊賊會(huì)首先選擇最好的物品玄括，然后是次好的，這樣繼續(xù)下去肉瓦，直到將背包裝滿遭京。當(dāng)然，在此之前泞莉，竊賊必須確定什么是“最好”的哪雕。最好的物品是價(jià)值最高的，重量最輕的鲫趁？還是具有最高價(jià)值/重量比值的呢斯嚎？如果選擇價(jià)值最高的物品，就應(yīng)該只帶電腦離開挨厚，這樣可以得到200美元堡僻。如果選擇重量最輕的，那么應(yīng)該依次帶走書疫剃、花瓶钉疫、收音機(jī)和油畫，一共價(jià)值170美元巢价。最后陌选，如果確定“最好”的含義是價(jià)值/重量比值最高，那么應(yīng)當(dāng)首先拿走花瓶和鐘蹄溉。然后有三種物品的價(jià)值/重量比值都是10咨油，但背包里只能放下書了。拿走書之后柒爵，他還可以拿走收音機(jī)役电。這樣，所有贓物的價(jià)值是255美元棉胀。

對(duì)于這個(gè)數(shù)據(jù)集法瑟，盡管按照密度（價(jià)值與重量的比值）進(jìn)行貪婪恰好得到了最優(yōu)結(jié)果，但相對(duì)于按照重量或價(jià)值進(jìn)行貪婪的算法來說唁奢，我們不能保證按照密度貪婪的算法一直能得到更好的解霎挟。更普遍地說，對(duì)于這種背包問題麻掸，無法確保使用貪婪算法找出的解是最優(yōu)解酥夭。

0/1背包問題的最優(yōu)解

假設(shè)我們認(rèn)為近似解還不夠好，那就需要找出這個(gè)問題的最優(yōu)解。竊賊面臨的問題恰好就是一種典型的最優(yōu)化問題熬北，稱為0/1背包問題疙描。 0/1背包問題可以定義如下。

• 每個(gè)物品都可以用一個(gè)值對(duì)<價(jià)值, 重量>表示讶隐；
• 背包能夠容納的物品總重量不能超過w起胰；
• 長(zhǎng)度為n的向量I表示一個(gè)可用的物品集合，向量中的每個(gè)元素都代表一個(gè)物品巫延；
• 長(zhǎng)度為n的向量V表示物品是否被竊賊帶走效五。如果V[i] = 1，則物品I[i]被帶走炉峰；如果V[i] = 0畏妖，
  則物品I[i]沒有被帶走；
• 目標(biāo)是找到一個(gè)V讲冠，使得：
  
  的值最大瓜客，并滿足約束條件：
  
  我們看看如何簡(jiǎn)單直接地解決這個(gè)問題。
  (1) 枚舉所有可能的物品組合竿开。也就是說谱仪，生成物品集合的所有子集，即物品集合的冪集否彩。
  (2) 去掉所有超過背包允許重量的物品組合疯攒。
  (3) 在余下的物品組合中，選出任意一個(gè)價(jià)值最大的組合列荔。
  這種方法一定可以找到一個(gè)最優(yōu)解敬尺。但如果初始物品集合很大，就需要運(yùn)行很長(zhǎng)時(shí)間贴浙。原因是隨著物品數(shù)量的增長(zhǎng)砂吞，子集數(shù)量呈現(xiàn)指數(shù)型增長(zhǎng)。

圖的最優(yōu)化問題

一些典型圖論問題

有很多著名的算法可以用來解決圖的最優(yōu)化問題崎溃，這是使用圖論表示和解決問題的一個(gè)優(yōu)勢(shì)蜻直。以下是一些最著名的圖的最優(yōu)化問題。

• 最短路徑：對(duì)于兩個(gè)節(jié)點(diǎn)n1和n2袁串，找到邊<s___n___, d___n___>（源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)）的最短序列概而，使得：
  （1）第一條邊的源節(jié)點(diǎn)是n1；
  （2）最后一條邊的目標(biāo)節(jié)點(diǎn)是n2囱修；
  （3）對(duì)于序列中任意的邊e1和e2赎瑰，如果e2在序列中緊跟在e1后面，那么e2的源節(jié)點(diǎn)是e1的目標(biāo)節(jié)點(diǎn)破镰。
• 最短加權(quán)路徑：與最短路徑非常相似餐曼，但它的目標(biāo)不是找出連接兩個(gè)節(jié)點(diǎn)的最短的邊的序列压储。對(duì)于序列中邊的權(quán)重，我們會(huì)定義某種函數(shù)（比如權(quán)重的和）晋辆，并使這個(gè)函數(shù)的值最小化渠脉。 Google Maps計(jì)算兩點(diǎn)之間的最短駕駛距離時(shí)宇整，就是在解決這種問題瓶佳。
• 最大團(tuán)： 團(tuán)是一個(gè)節(jié)點(diǎn)集合，集合中每?jī)蓚€(gè)節(jié)點(diǎn)之間都有一條邊鳞青。 最大團(tuán)是一個(gè)圖中規(guī)模最大的團(tuán)霸饲。
• 最小割：在一個(gè)圖中，給定兩個(gè)節(jié)點(diǎn)集合臂拓， 割就是一個(gè)邊的集合厚脉。去掉這組邊之后，一個(gè)節(jié)點(diǎn)集合中的每個(gè)節(jié)點(diǎn)和另一個(gè)節(jié)點(diǎn)集合中的每個(gè)節(jié)點(diǎn)之間都不存在任何相連的路徑胶惰。最小割就是這樣一個(gè)最小的邊的集合傻工。

最短路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索

Facebook上具有“朋友”關(guān)系的兩個(gè)人之間的距離。例如孵滞，你
會(huì)很想知道中捆，你是否有這樣一個(gè)朋友，他的朋友的朋友的朋友是米克·賈格爾坊饶。我們可以設(shè)計(jì)一個(gè)程序來回答這個(gè)問題泄伪。

朋友關(guān)系（至少在Facebook上）是對(duì)稱的，例如匿级，如果斯蒂芬妮是安德烈婭的朋友蟋滴，那么安德烈婭也是斯蒂芬妮的朋友。因此痘绎，我們會(huì)使用Graph類型實(shí)現(xiàn)這個(gè)社交網(wǎng)絡(luò)津函。然后可以定義尋找你和米克·賈格爾之間的最短連接的問題，如下所示孤页。

• 令G為表示朋友關(guān)系的無向圖尔苦；
• 對(duì)于G，找到一個(gè)最短的節(jié)點(diǎn)序列[你散庶，……蕉堰，米克·賈格爾]，使得：如果和是路徑中兩個(gè)連續(xù)的節(jié)點(diǎn)悲龟，那么G中有一條邊連接和屋讶。

from graph import *

def printPath(path):
    """假設(shè)path是節(jié)點(diǎn)列表"""
    result = ''
    for i in range(len(path)):
        result = result + str(path[i])
        if i != len(path) - 1:
            result = result + '->'
    return result

def DFS(graph, start, end, path = [], shortest = None):
    #assumes graph is a Digraph
    #assumes start and end are nodes in graph
    path = path + [start]
    print 'Current dfs path:', printPath(path)
    if start == end:
        return path
    for node in graph.childrenOf(start):
        if node not in path: #avoid cycles
            newPath = DFS(graph,node,end,path,shortest)
            if newPath != None:
                return newPath

def DFSShortest(graph, start, end, path = [], shortest = None):
    #assumes graph is a Digraph
    #assumes start and end are nodes in graph
    path = path + [start]
    print 'Current dfs path:', printPath(path)
    if start == end:
        return path
    for node in graph.childrenOf(start):
        if node not in path: #avoid cycles
            if shortest == None or len(path)<len(shortest):
                newPath = DFSShortest(graph,node,end,path,shortest)
                if newPath != None:
                    shortest = newPath
    return shortest


def testSP():
    nodes = []
    for name in range(6):
        nodes.append(Node(str(name)))
    g = Digraph()
    for n in nodes:
        g.addNode(n)
    g.addEdge(Edge(nodes[0],nodes[1]))
    g.addEdge(Edge(nodes[1],nodes[2]))
    g.addEdge(Edge(nodes[2],nodes[3]))
    g.addEdge(Edge(nodes[2],nodes[4]))
    g.addEdge(Edge(nodes[3],nodes[4]))
    g.addEdge(Edge(nodes[3],nodes[5]))
    g.addEdge(Edge(nodes[0],nodes[2]))
    g.addEdge(Edge(nodes[1],nodes[0]))
    g.addEdge(Edge(nodes[3],nodes[1]))
    g.addEdge(Edge(nodes[4],nodes[0]))
    sp = DFS(g, nodes[0], nodes[5])
    print 'Shortest path found by DFS:', printPath(sp)


def BFS(graph, start, end, q = []):
    initPath = [start]
    q.append(initPath)
    while len(q) != 0:
        tmpPath = q.pop(0)
        lastNode = tmpPath[len(tmpPath) - 1]
        print 'Current dequeued path:', printPath(tmpPath)
        if lastNode == end:
            return tmpPath
        for linkNode in graph.childrenOf(lastNode):
            if linkNode not in tmpPath:
                newPath = tmpPath + [linkNode]
                q.append(newPath)
    return None

DFS函數(shù)實(shí)現(xiàn)的算法是遞歸形式的深度優(yōu)先搜索算法。一般地须教，深度優(yōu)先搜索算法開始時(shí)皿渗，會(huì)先選擇起始節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)斩芭，然后再選擇這個(gè)子節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)，以此類推乐疆，直到到達(dá)目標(biāo)節(jié)點(diǎn)或者一個(gè)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)划乖。然后，搜索開始回溯挤土，返回到最近一個(gè)沒有訪問過的帶有子節(jié)點(diǎn)的節(jié)點(diǎn)琴庵。遍歷所有路徑之后，算法就可以選擇一個(gè)從起點(diǎn)到終點(diǎn)的最短路徑（如果有）仰美。

除了深度優(yōu)先之外迷殿，還有其他方式對(duì)圖進(jìn)行遍歷。另一種常用的方法稱為廣度優(yōu)先搜索咖杂。廣度優(yōu)先搜索會(huì)先訪問起始節(jié)點(diǎn)的所有子節(jié)點(diǎn)庆寺，如果這些子節(jié)點(diǎn)都不是最終節(jié)點(diǎn)，就繼續(xù)訪問每個(gè)子節(jié)點(diǎn)的所有子節(jié)點(diǎn)诉字，以此類推懦尝。深度優(yōu)先搜索經(jīng)常使用遞歸實(shí)現(xiàn)，廣度優(yōu)先搜索則不同壤圃，它一般使用迭代來實(shí)現(xiàn)陵霉。 BFS會(huì)同時(shí)探索多條路徑，每次迭代向每條路徑添加一個(gè)節(jié)點(diǎn)埃唯。由于算法生成路徑時(shí)是按照長(zhǎng)度升序進(jìn)行的撩匕，所以第一次找到的最終節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)的路徑一定具有最少數(shù)量的邊

在本例中，兩種算法找出的是同樣的路徑墨叛。但如果圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑不止一條止毕，那么DFS和BFS就不一定會(huì)找出同樣的
最短路徑。如上所述漠趁，如果要找出一條邊數(shù)最少的路徑扁凛，那么BFS更方便，因?yàn)樗谝淮握业降穆窂骄鸵欢ㄊ沁@樣的路徑闯传。