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

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

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

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