離散空間上的多維容錯搜索問題的探究.pdf

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

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