離散空間上并行搜索單目標(biāo)的最優(yōu)算法.pdf

1、離散空間上的搜索理論是搜索論中的一個(gè)新的熱點(diǎn)研究領(lǐng)域.這一理論的本質(zhì)是基于可靠或未必可靠的信息建立可靠的結(jié)果，因此它在眾多的自然科學(xué)和社會(huì)科學(xué)領(lǐng)域有著廣泛的應(yīng)用.本文主要研究了離散空間上搜索理論中的一個(gè)重要搜索模型：在n個(gè)硬幣組成的集合中有一個(gè)較重的硬幣，其余的n-1個(gè)硬幣是具有相同重量的好幣.在一定的條件下，尋找一種用盡可能少的稱重次數(shù)識(shí)別出這個(gè)假幣的最優(yōu)算法.本文共分三章. 第一章主要介紹了本文的研究意義，所研究的模型，與此

2、模型有關(guān)的一些定義以及此模型的研究現(xiàn)狀. 第二章討論了用b-天平作為稱量工具，并且只允許對(duì)可疑的硬幣進(jìn)行稱重來(lái)搜索那個(gè)較重的硬幣.我們給出了具有最壞情況下的最少稱重次數(shù)的序列算法和平均情況下的最少稱重次數(shù)的序列算法.并且還確定出了最壞情況下的最少稱重次數(shù)和平均最少稱重次數(shù)的精確表達(dá)式.當(dāng)b=1時(shí)，即為M.Aigner在文獻(xiàn)[1]考慮的情況.所以，本章的主要內(nèi)容推廣了MAigner在文獻(xiàn)[1]中得到的結(jié)果.同時(shí)，我們也證明了在所有

3、的概率分布中，均勻概率分布條件下所求得的平均最少稱重次數(shù)最大. 第三章考慮了采用b-天平作為試驗(yàn)裝置，至多允許一次試驗(yàn)結(jié)果出錯(cuò)的條件下，從n個(gè)硬幣中搜索那個(gè)較重的硬幣.我們給出了最壞情況下的最優(yōu)算法，并且對(duì)于任意的整數(shù)n≥2和b≥1，確定出了最壞情況下的最少試驗(yàn)次數(shù).Pelc[39]研究了用一個(gè)天平，至多允許一次試驗(yàn)結(jié)果出錯(cuò)的條件下，從n個(gè)硬幣中搜索那個(gè)較重的硬幣所用的最壞情況下的最少試驗(yàn)次數(shù).故本章的主要結(jié)論是對(duì)Pelc[39