Уақытты бағалау үшін ең жақсы көздерді таңдау алгоритмі

Кіріспе

Уақытты бағалау үшін ең жақсы көздерді таңдау алгоритмі. Кесісу алгоритмі – бұл көптеген қате уақыт көздерінен дәл уақытты бағалауға арналған көздерді таңдау үшін қолданылатын келісім алгоритмі. Ол қазіргі заманғы Желілік уақыт протоколының құрамдас бөлігі болып табылады. Бұл Марзулло алгоритмінің өңделген түрі. Марзулло алгоритмі көздердің ең көп санымен сәйкес келетін ең кіші интервалды қайтарады, бірақ қайтарылған интервал міндетті түрде кесісудегі барлық көздердің орталық нүктесін (есептелген қателік) қамтымайды. Кесісу алгоритмі Марзулло алгоритмі қайтаратын интервалды қайтарады, бірақ ол орталық нүктелерді қамтитындықтан үлкенірек болуы мүмкін. Бұл үлкен интервал қосымша статистикалық деректерді пайдаланып интервал ішіндегі нүктені таңдауға мүмкіндік береді, соның арқасында қайталап орындау кезінде тербеліс азаяды.

Әдіс

M c ± r түріндегі интервалдарды (бұл [c−r, c+r] дегенді білдіреді) ескере отырып, алгоритм M−f көздері бар интервалды табуға тырысады. f мәні қателік бар дереккөздердің саны ретінде көрсетіледі (нақты мән сенімділік диапазонынан тыс). Ең жақсы бағалау – ең аз қателік белгілерін (f) қамтитын интервал. Нәтижелер f < M/2 болса жарамды деп есептеледі, әйтпесе алгоритм интервалдың орнына қате (FAILED) қайтарады. Киылысу алгоритмі <оффсет, тип> түйірлер тізімін жасаудан басталады. Әрбір интервал үшін үш жазба болады: төменгі нүкте, ортаңғы нүкте және жоғарғы нүкте, тиісінше -1, 0 және +1 типтерімен белгіленеді. Осылайша, c ± r интервалы <c−r,−1>, <c,0> және <c+r,+1> жазбаларын тудырады. Бұл жазбалар оффсет бойынша сұрыпталады. Айтмалылар: Бұл алгоритмде f – жалған тікелейлердің саны, endcount және midcount – бүтін сандар. Lower және upper – оффсет мәндері. [ең жақсы f-ті инициализациялау] f=0-ден бастаңыз, барлық кіріс интервалдары жарамды деп есептелінеді. Егер интервал табылмайтын болса, f мәні f ≥ M/2 болғанға дейін немесе интервал табылғанға дейін әр ретте 1-ге арттырылады. [инициализациялау] endcount=0 және midcount=0. [төменгі нүктені табу] Тізімнің басынан (ең төменгі оффсеттен) бастап, әрбір түйірді ретімен қарастырыңыз. endcount = endcount - тип. Егер endcount ≥ M−f болса, онда lower = оффсет және 3-қадамға өтіңіз, себебі (мүмкін) төменгі нүкте табылды. Егер тип = 0 болса, онда midcount = midcount + 1. Келесі түйірмен қайталаңыз. Егер тізімнің соңына жетсе, 6-қадамға өтіңіз. [алдын ала төменгі нүкте табылды, жоғарғы нүктені табу үшін инициализациялау] endcount=0 деп қойыңыз. [орталық нүктелердің санын анықтау] Тізімнің соңынан бастап, төменгі оффсеттерге қарай жұмыс істеңіз. endcount = endcount + тип. Егер endcount ≥ M−f болса, онда upper = оффсет, 5-қадамға дайындық. Егер тип = 0 болса, онда midcount = midcount + 1. Келесі түйір үшін қайталаңыз. Егер тізімнің соңына жетсе, 6-қадамға өтіңіз. Егер lower ≤ upper және midcount ≤ f болса, онда [lower, upper] интервалын сенімділік интервалы ретінде қайтарыңыз. [жалған белгілердің санын арттыру] f = f + 1. Егер f ≥ M/2 болса, тоқтатыңыз және FAILED қайтарыңыз, әйтпесе 1-қадамға өтіңіз.

Given M intervals of the form c ± r (which means [c−r,c+r]), the algorithm seeks to find an interval with M−f sources. The value f is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the confidence band). The best estimate is that which assumes the fewest falsetickers, f. The results will be considered valid if f < M/2, otherwise the algorithm will return failure instead of an interval. The intersection algorithm begins by creating a table of tuples <offset, type>. For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively. Thus the interval c ± r results in the entries <c−r,−1>, <c,0> and <c+r,+1>. These entries are then sorted by offset. Variables: This algorithm uses f as number of false tickers, endcount and midcount are integers. Lower and upper are values of offsets. [initialize best f] Start with f=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or f ≥ M/2. [initialize] endcount=0 and midcount=0. [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. endcount = endcount−type. If endcount ≥ M−f then lower = offset and goto step 3 because the (possible) lower endpoint has been found. If the type = 0 then midcount = midcount+1. Repeat with next tuple. If reach end of list then goto step 6. [tentative lower endpoint found, initialize to find upper endpoint] set endcount=0. [determine number of midpoints] Start from end of list and work towards lower offsets. endcount = endcount+type. If endcount ≥ M−f then upper = offset, goto step 5. If type = 0 then midcount = midcount+1. Repeat for next tuple. If reach end of list then goto step 6.
if lower ≤ upper and midcount ≤ f then return interval [lowerendpoint, upperendpoint] as resulting confidence interval. [increment number of falsetickers] f = f+1. If f ≥ M/2 then terminate and return FAILED, otherwise goto step 1.