離散空間上的多維容錯(cuò)搜索問(wèn)題的探究.pdf

1、本文研究了下面的“q-維e-容錯(cuò)搜索”模型：游戲雙方提問(wèn)者(Paul)和回答者(carole)事先約定了三個(gè)整數(shù)n≥1，e≥0和q≥2，回答者在搜索空間S={1，2，…，n}中選取了一個(gè)秘密數(shù)x<'*>，提問(wèn)者通過(guò)提出一系列提問(wèn)由回答者作答從而設(shè)法找出數(shù)x<'*>，在整個(gè)游戲過(guò)程中允許回答者撒謊至多e次．研究這類模型的中心任務(wù)是找到提問(wèn)者能夠搜索成功的具有最小提問(wèn)次數(shù)的算法．本文所獲得的主要研究成果如下： 針對(duì)單目標(biāo)q-維1-容

2、錯(cuò)對(duì)偶模型，通過(guò)引入“典型狀態(tài)”以及“狀態(tài)特征”等概念，建立了將具有較大特征的典型狀態(tài)轉(zhuǎn)變?yōu)榫哂休^小特征的典型狀態(tài)的遞歸算法，得到了提問(wèn)者制勝的充分條件；通過(guò)精心設(shè)計(jì)第一次提問(wèn)并證明其最優(yōu)性，得到了提問(wèn)者制勝的必要條件．在此基礎(chǔ)上，對(duì)于n≥q<'q-1>，我們給出了提問(wèn)者制勝的最優(yōu)算法，對(duì)于n，我們給出了提問(wèn)者制勝的次最優(yōu)的算法并舉例說(shuō)明了最優(yōu)算法并不總是能夠得到的． 徹底解決了q-維1-容錯(cuò)雙區(qū)間提問(wèn)搜索模型．