大肉棒导航,日韩电影AV

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

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

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

背包問(wèn)題

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

物品表

貪婪算法

對(duì)于這個(gè)問(wèn)題，找出近似解的最簡(jiǎn)單方法就是貪婪算法。竊賊會(huì)首先選擇最好的物品，然后是次好的，這樣繼續(xù)下去，直到將背包裝滿。當(dāng)然，在此之前，竊賊必須確定什么是“最好”的。最好的物品是價(jià)值最高的，重量最輕的？還是具有最高價(jià)值/重量比值的呢？如果選擇價(jià)值最高的物品，就應(yīng)該只帶電腦離開(kāi)，這樣可以得到200美元。如果選擇重量最輕的，那么應(yīng)該依次帶走書(shū)、花瓶、收音機(jī)和油畫(huà)，一共價(jià)值170美元。最后，如果確定“最好”的含義是價(jià)值/重量比值最高，那么應(yīng)當(dāng)首先拿走花瓶和鐘。然后有三種物品的價(jià)值/重量比值都是10，但背包里只能放下書(shū)了。拿走書(shū)之后，他還可以拿走收音機(jī)。這樣，所有贓物的價(jià)值是255美元。

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

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

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

每個(gè)物品都可以用一個(gè)值對(duì)<價(jià)值, 重量>表示；
背包能夠容納的物品總重量不能超過(guò)w；
長(zhǎng)度為n的向量I表示一個(gè)可用的物品集合，向量中的每個(gè)元素都代表一個(gè)物品；
長(zhǎng)度為n的向量V表示物品是否被竊賊帶走。如果V[i] = 1，則物品I[i]被帶走；如果V[i] = 0，
則物品I[i]沒(méi)有被帶走；
目標(biāo)是找到一個(gè)V，使得：
$\sum_{i=0}^{n-1} V[i] * I[i].value$
的值最大，并滿足約束條件：
$\sum_{i=0}^{n-1} V[i] * I[i].weight ≤ w$
我們看看如何簡(jiǎn)單直接地解決這個(gè)問(wèn)題。
(1) 枚舉所有可能的物品組合。也就是說(shuō)，生成物品集合的所有子集，即物品集合的冪集。
(2) 去掉所有超過(guò)背包允許重量的物品組合。
(3) 在余下的物品組合中，選出任意一個(gè)價(jià)值最大的組合。
這種方法一定可以找到一個(gè)最優(yōu)解。但如果初始物品集合很大，就需要運(yùn)行很長(zhǎng)時(shí)間。原因是隨著物品數(shù)量的增長(zhǎng)，子集數(shù)量呈現(xiàn)指數(shù)型增長(zhǎng)。

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

一些典型圖論問(wèn)題

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

最短路徑：對(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í)，就是在解決這種問(wèn)題。
最大團(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è)程序來(lái)回答這個(gè)問(wèn)題。

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

令G為表示朋友關(guān)系的無(wú)向圖；
對(duì)于G，找到一個(gè)最短的節(jié)點(diǎn)序列[你，……，米克·賈格爾]，使得：如果 $n_i$ 和 $n_{i+1}$ 是路徑中兩個(gè)連續(xù)的節(jié)點(diǎn)，那么G中有一條邊連接 $n_i$ 和 $n_{i+1}$ 。

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)先搜索算法開(kāi)始時(shí)，會(huì)先選擇起始節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)，然后再選擇這個(gè)子節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)，以此類(lèi)推，直到到達(dá)目標(biāo)節(jié)點(diǎn)或者一個(gè)沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。然后，搜索開(kāi)始回溯，返回到最近一個(gè)沒(méi)有訪問(wèn)過(guò)的帶有子節(jié)點(diǎn)的節(jié)點(diǎn)。遍歷所有路徑之后，算法就可以選擇一個(gè)從起點(diǎn)到終點(diǎn)的最短路徑（如果有）。

除了深度優(yōu)先之外，還有其他方式對(duì)圖進(jìn)行遍歷。另一種常用的方法稱(chēng)為廣度優(yōu)先搜索。廣度優(yōu)先搜索會(huì)先訪問(wèn)起始節(jié)點(diǎn)的所有子節(jié)點(diǎn)，如果這些子節(jié)點(diǎn)都不是最終節(jié)點(diǎn)，就繼續(xù)訪問(wèn)每個(gè)子節(jié)點(diǎn)的所有子節(jié)點(diǎn)，以此類(lèi)推。深度優(yōu)先搜索經(jīng)常使用遞歸實(shí)現(xiàn)，廣度優(yōu)先搜索則不同，它一般使用迭代來(lái)實(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)樗谝淮握业降穆窂骄鸵欢ㄊ沁@樣的路徑。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

python編程導(dǎo)論_第十三課

python編程導(dǎo)論_第十三課