離散空間上的區(qū)間型容錯搜索.pdf

1、Y1105425河南衙缸大哮碩士學(xué)位論文離散空間上的區(qū)問型容錯搜索學(xué)科、專業(yè)研究方向申請學(xué)位類別申請人指導(dǎo)教師概率論與數(shù)理統(tǒng)計隨機模型理學(xué)碩士邢淑敏劉文安教授oo七年四月AbstractTheoryofsearch塒therrorsondiscretespaceisanewhotfieldofsearchtheoryThenatureofthistheoryisestablishingthereliableresultsbasedonu

2、nreliableinformation，soithasvariousapplicationsinmanyfieldsofnaturalandsocialsciencesInthispaper，weresearchtheproblemoffindingaunknownelementoutofasetofnelementsbybiintervalquestionsorintervalquestionsItisaclassicalprobl

3、emintheCombinatorialSearchTheoryTheaimoftheproblemistofindtheunknownelementusingtheleastpossiblequestionswitheliesWeintroducetheresearchbackgroundofthispaperandalsothepreliminariesinChapter1Chapter2andChapter3givethemain

4、theoreticalresultsofthisthesisbelow：(1)Theproblemofsearch謝th1errorandsingleintervalqueriesiscompletelysolvedTherelationb6t；weensingleintervalqueriesandyesnoqueriesisobtainedbydefiningtheconceptsof。arc。and。wellshaped。anda

5、recursivealgorithmofchoosingthesingleintervalqueryofwellshapedsimplestateisgiven，then，itisprovedthattheminimalnumberoftestsisequaltothesmallestpossiblenumberusingyesnoquerieswithonelieandthecorrespondingoptimalalgorithmi

6、spresented(2)Theproblemofsearchwith2erromandbiintervalqueriesiscompletelysolvedWeintroducetheconceptsof。arc’。wellshaped。and。typicalstate。andconstructcarefurythefirsttwobiintervalqueries；Moreover，thegivenfirsttwobiinterva

7、lqueriesarealsostrictlyprovedtobeoptimal；Arecursiveaigofithmofchoosingthetestsctsofwellshapedtypicalstateisdesigned，itturnsoutallresultingstatesarestilltypicalonesofsmallercharacterAftercompletingabovesteps，thenlainresul

8、tisobtained：Foroh(＆，口，口)≥25，theminimalnumberoftestsisequalt0thesmallestpossiblenumberusingyesnoquerieswithtwolieandthecorrespondingoptimalalgorithmi8presented(3)Guzickihasgiventheoptimalstrategyforthemodelofsearchwith2er