組合算法中的彩色編碼技術研究.pdf

1、彩色編碼(color-coding)是目前算法中重要的參數(shù)化技術之一。該技術已經在許多領域如k-PATH、子圖同構、matching和packing等許多領域得到了應用。從這個意義上說，color-coding是算法領域中一個基礎性問題：它的改進將帶來算法在不同領域中一系列突破性進展。而在應用彩色編碼時，所使用著色數(shù)目極大影響著問題求解性能，因此在應用該技術的時候算法應當盡可能地減少使用的著色數(shù)目。其中隨機算法使用規(guī)模為O(e<'k>)

2、的著色集合可以得到相對可靠的解；而確定算法則需要使用相對更大的著色方案。目前主流著色方案構造算法均基于完全散列函數(shù)和小參數(shù)理論，該技術近年發(fā)展迅速，其中J.Chen等人的算法可在O<'*>(6.1<'k>)時間內將彩色編碼確定化。 在詳細分析彩色編碼技術的原理和應用的基礎上，作者提出了一種基于劃分的著色方案構造算法(PBCC)，解決了目前小參數(shù)算法在n≤2k的情況下效率低下的問題。作者也通過比較PBCC產生方案的規(guī)模漸近上界，在

3、n≤2k下方案規(guī)模的漸近下界，以及窮舉算法復雜度的下界，從理論上證明了PBCC算法的有效性。繼而，在分治思想的框架上，基于PBCC算法和完全散列函數(shù)的思想，綜合各種技術的優(yōu)點，作者進一步提出了混合結構著色算法(HABCC)，將算法的應用范圍由n≤2k擴展到任意的參數(shù)(n，k)組合。經實驗檢驗，在實際條件下綜合各算法優(yōu)勢的HABCC算法產生的方案規(guī)模遠遠小于原有小參數(shù)算法所產生的方案規(guī)模。此外，作者還推導了彩色編碼問題中的一些理論界限，這