算法設(shè)計(jì)分支界限法實(shí)驗(yàn)

1、南陽(yáng)理工學(xué)院算法設(shè)計(jì)與分析報(bào)告冊(cè)開(kāi)課學(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é)號(hào)： 1806905030專(zhuān)業(yè)班級(jí)：18大數(shù)據(jù)2019-2020學(xué)年第2學(xué)期一、實(shí)驗(yàn)?zāi)康牧私夥种藿绶ㄋ枷牒皖?lèi)型掌握使用分支限界法求解問(wèn)題的一般步驟能夠針對(duì)實(shí)際問(wèn)題，分析正確問(wèn)題的解空間、解空間的組織結(jié)構(gòu)、搜索的約束條件、限界條件，優(yōu)先級(jí)。能夠正確使用隊(duì)列、優(yōu)先隊(duì)列正確編碼。能夠正確分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度二、實(shí)驗(yàn)平臺(tái)Windows操作系統(tǒng)或Linux操作系統(tǒng)Python3.xpyCharm 或 sublime 或 jupyter notebook三、

2、實(shí)驗(yàn)內(nèi)容旅行售貨員問(wèn)題四、算法設(shè)計(jì)問(wèn)題分析一個(gè)商品推銷(xiāo)員要去若干個(gè)城市推銷(xiāo)商品，該推銷(xiāo)員從一個(gè)城市出發(fā)，需要 經(jīng)過(guò)所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線(xiàn)，以使總的行程最短。問(wèn)題建模該問(wèn)題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無(wú)向圖中，找一個(gè)權(quán)值最小的Hamilton回路。 由于該問(wèn)題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會(huì)產(chǎn)生組合爆炸， 它是一個(gè)NP完全問(wèn)題。算法描述找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(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#如果到了最后一個(gè)點(diǎn),加上回去的路，并計(jì)算最小值if len(node.route) = 4: wholecost = graphnode.route1s + node.cost if wholecost i MvnMiEEJE* 、*八、實(shí)驗(yàn)總結(jié)了解了分支限界法思想和類(lèi)型，掌握了如何使用分支限界法求解問(wèn)題的一 般步驟，能夠針對(duì)實(shí)際問(wèn)題，分析正確問(wèn)題的解空間、解空間的組