问题描述
这是我研究生课程的一道题，暂时还没有思路，请各位前辈集思广益，先谢过了。如果x,y属于{0,n}^n,thenrecallthatDist(x,y)denotestheHammingdistance（汉明距离）betweenxandy.Anon-linearcodeoflengthnandminimumdistancedisasubsetC{0,1}^nsuchthatDist(x,y)大于等于dforallx,yinC.DenotebyA(n,d)themaximumnumberofn-tuplesinalength-nnon-linearcodeofminimumdistanced.(a)给出一种回溯法来计算A(n,d)(写出伪码）ImplementyouralgorithmandcomputeA(n,4)for4<n<8.ThecorrectvaluesforA(n,d)forsmallvaluesofnanddcanbefoundonthefollowingwebpage:http://www.win.tue.nl/~aeb/codes/binary-1.htmlForeachofyourtests,reporttheinputvalues,thefinalanswer,thenumberofbacktrackingnodesvisitedandCPUtime.Efficiencyandclaritycount.(b)ShowapseudocodeandgiveaprogramforKnuth'sAlgorithmtoestimatethesizeofthebacktrackingtreeforyouralgorithm.Usethismethodtoestimatethesizeofthebacktrackingtreefor4<n<11.Foreachvalueofn,chooseasuitablylargenumberPofprobesandshowtheestimateforatleast5valuesofnumberofprobesequallyspacedwithin[10,P].Doesthisestimateapproximateswellthenumberofnodesyoufoundinthepreviousquestion?(Ifnot,youmayhavetocheckcorrectnessofthecomputationsthereoryourestimationhere).(c)ShowapseudocodeandgiveaprogramforKnuth'sgeneralizedmethodtoestimatethesizeofA(n,4)forn=4,...,16.Theexactvaluescanbefoundonthewebsitegiveninparta.