加權分治技術在Set Packing問題中的應用與研究.pdf

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

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