加權(quán)分治技術(shù)在Set Packing問題中的應(yīng)用與研究.pdf

1、NP-完全理論是算法研究方面的重要的基本理論，它在計(jì)算機(jī)、電氣工程和運(yùn)籌學(xué)方面都有重要的地位。本文主要以算法技巧為著眼點(diǎn)來研究此類問題，希望在解決方式上有新的突破。 加權(quán)分治技術(shù)由F.V.fomin首先提出，是在分析算法中產(chǎn)生的一項(xiàng)新技術(shù)，該方法基于選擇不同的量來描述分支子問題的大小，以求從中得到在最差情況下最好的時(shí)間復(fù)雜度。在加權(quán)分治技術(shù)中采用偽凸規(guī)劃技術(shù)對(duì)回溯算法來確定各個(gè)權(quán)值，使得時(shí)間復(fù)雜度最小。我們也給出了一種新方法，通

2、過進(jìn)化算法求解賦權(quán)函數(shù)以求得最小上界，同樣可以來確定權(quán)值，且比前種方法更加簡(jiǎn)單。 根據(jù)加權(quán)分治技術(shù)的應(yīng)用范圍選定Set Packing問題進(jìn)行深入研究，依據(jù)所研究問題的差異，將Set Packing問題分成5類，并給出了具體的定義。在此基礎(chǔ)上，分別介紹了求解這5類問題的相關(guān)算法，著重分析和比較了參數(shù)算法中所運(yùn)用的各項(xiàng)技術(shù)，并提出了該問題算法研究的發(fā)展方向。 對(duì)于GSP問題本文給出了一個(gè)簡(jiǎn)單的遞歸算法，并利用加權(quán)分治技術(shù)深