1、南陽理工學(xué)院算法設(shè)計(jì)與分析報(bào)告冊開課學(xué)院:計(jì)算機(jī)與信息工程學(xué)院 實(shí)驗(yàn)項(xiàng)目：分支限界法實(shí)驗(yàn) 實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)地點(diǎn)：指導(dǎo)教師：學(xué)生姓名：學(xué)生學(xué)號： 1806905030專業(yè)班級：18大數(shù)據(jù)2019-2020學(xué)年第2學(xué)期一、實(shí)驗(yàn)?zāi)康牧私夥种藿绶ㄋ枷牒皖愋驼莆帐褂梅种藿绶ㄇ蠼鈫栴}的一般步驟能夠針對實(shí)際問題，分析正確問題的解空間、解空間的組織結(jié)構(gòu)、搜索的約束條件、限界條件，優(yōu)先級。能夠正確使用隊(duì)列、優(yōu)先隊(duì)列正確編碼。能夠正確分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度二、實(shí)驗(yàn)平臺Windows操作系統(tǒng)或Linux操作系統(tǒng)Python3.xpyCharm 或 sublime 或 jupyter notebook三、

2、實(shí)驗(yàn)內(nèi)容旅行售貨員問題四、算法設(shè)計(jì)問題分析一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要 經(jīng)過所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。問題建模該問題實(shí)質(zhì)是在一個帶權(quán)完全無向圖中，找一個權(quán)值最小的Hamilton回路。 由于該問題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會產(chǎn)生組合爆炸， 它是一個NP完全問題。算法描述找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函 數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。五、算法源碼import math from heapq import * n = 4x = 1, 2, 3, 4#定義

3、圖的字典形式G = 1:2:15, 3: 3, 4: 2,2:1:15, 3: 2.5, 4: 5,3:1:3, 2: 2.5, 4: 10,4:1:2, 2: 5, 3: 10#定義圖的數(shù)組形式 graph =0, 15, 3, 2,15, 0, 2.5, 5,3, 2.5, 0, 10,2, 5, 10, 0bestcost = math.infnowcost = 0 #全局變量,現(xiàn)在的花費(fèi)#設(shè)置節(jié)點(diǎn)美class Node:#構(gòu)造函數(shù),現(xiàn)在的花費(fèi),到目前的路徑def _init_(self, w=math.inf, route=, cost=0): self.weight = w self.route = route self.cost = cost#重載比較，用于堆的排序def _lt_(self, other): return int(self.weight) = bestcost:continue#如果到了最后一個點(diǎn),加上回去的路，并計(jì)算最小值if len(node.route) = 4: wholecost = graphnode.route1s + node.cost if wholecost i MvnMiEEJE* 、*八、實(shí)驗(yàn)總結(jié)了解了分支限界法思想和類型，掌握了如何使用分支限界法求解問題的一 般步驟，能夠針對實(shí)際問題，分析正確問題的解空間、解空間的組