布局知識圖矩形檢測與加權(quán)圓集裝填的啟發(fā)式搜索算法研究.pdf

1、容器裝填問題是將若干裝填物互不沖突地放進一個容器中，要求容器的利用率最優(yōu)且滿足給定的約束。該問題的應(yīng)用背景包括：建筑設(shè)計、服裝行業(yè)、電子工業(yè)、航空航天、交通運輸、機械制造、城市規(guī)劃等諸多領(lǐng)域。裝填方案的好壞直接影響著它們的生產(chǎn)效率、經(jīng)濟效益和系統(tǒng)的安全性等性能指標。
　　容器裝填問題是眾多的裝填問題當中最典型的一類，基于知識的求解方法是目前研究的熱點。本文討論布局知識的獲取與基于知識的帶性能約束裝填問題的求解方法。它具體包括：(i

2、)以印刷電路板的設(shè)計為背景討論圓形容器加權(quán)圓集裝填問題；(ii)以衛(wèi)星艙布局問題為背景討論圓容器布局知識圖的矩形檢測問題。對于(i)，由于其NP-hard屬性，難以在多項式時間內(nèi)求解。許多學(xué)者基于該問題的模型提出了各自的求解算法，它包括：啟發(fā)式算法、免疫算法、人機交互、演化算法，如遺傳算法、蟻群算法和文化算法及粒子群算法等、混合算法等。目前的研究熱點是基于知識的求解算法。對于(ii)，目前的檢測方法包括：基于線段檢測的方法，窗口Houg

3、h變換方法和鏈碼檢測方法。但如何利用矩形的特征有效而快速檢測出矩形，特別是殘缺矩形，仍然需要進一步研究。本文在國家自然科學(xué)基金項目、湖南省教育廳重點科學(xué)研究項目的資助下，分別對上述問題(i)和(ii)進行了許多探索，并取得了一些研究成果。
　　其創(chuàng)新點如下：
　　(1)針對布局知識解參數(shù)計算問題，本文提出一種布局知識解的多個矩形檢測方法。它先隨機采樣兩個圖像點，并在以此兩點間的線段為直徑的圓周上搜索第3個圖像點來確定侯選矩形

4、，然后快速的確認該候選矩形是否為真矩形。在隨機獲取兩個圖像點時，通過縮小樣本大小（剔除孤立、半連續(xù)噪聲）減少無效采樣；在確定矩形時，利用矩形的特征確定它的另外兩個頂點，并給出了確認侯選矩形為真矩形的方法，該方法快速有效能夠減少大量的無效計算。數(shù)值實驗結(jié)果表明：本文提出的算法能快速檢測多矩形，對帶殘缺邊和對角的矩形檢測也非常有效。
　　(2)針對啟發(fā)算法搜索效率問題，本文提出一種加權(quán)圓集裝填的知識啟發(fā)式搜索算法。它以權(quán)矩陣各行和的絕