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

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

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

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