Մետրոպոլիս-Հաստինգսի ալգորիթմ
From Wikipedia, the free encyclopedia
Մետրոպոլիս-Հաստինգսի ալգորիթմը, սեմպլիրացման ալգորիթմ է, որն հիմնականում օգտագործվում է բաշխման բարդ ֆունկցիաների համար։ Այն մասամբ նման է շեղումներով ընտրության ալգորիթմին, սակայն այստեղ բաշխման օժանդակ ֆունկցիան փոխվում է ժամանակի ընթացքում է։ Առաջին անգամ ալգորիթմը լույս է տեսել Նիկոլաս Մետրոպոլիսի կողմից 1953 թվին, և հետո ընդհանրացվել Հաստինգսի կողմից 1970 թվին. սեմպլիրացում ըստ Գիբբսի հանդիսանում է Մետրոպոլիս-Հաստինգսի ալգորիթմի մասնավոր դեպք, և ավելի հայտնի է իր պարզությամբ և արագությամբ, չնայած առավել հազվադեպ է կիրառվում։
Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
Այս հոդվածը կարող է վիքիֆիկացման կարիք ունենալ Վիքիպեդիայի որակի չափանիշներին համապատասխանելու համար։ Դուք կարող եք օգնել հոդվածի բարելավմանը՝ ավելացնելով համապատասխան ներքին հղումներ և շտկելով բաժինների դասավորությունը, ինչպես նաև վիքիչափանիշներին համապատասխան այլ գործողություններ կատարելով։ |
Մետրոպոլիս-Հաստինգսի ալգորիթմ | |
---|---|
Տեսակ | ալգորիթմ |
Հայտնաբերող | Nicholas Metropolis?[1], Marshall Rosenbluth?[1], Էդվարդ Թելեր[1], W. K. Hastings?[2], Էնրիկո Ֆերմի և Ստանիսլավ Ուլամ |
Անվանված է | Nicholas Metropolis? և W. K. Hastings? |
Մետրոպոլիս-Գաստինգի ալգորիթմը թույլ է տալիս սեմպլիրացնել ցանկացած բաշխման ֆունկցիա։ Այն հիմնված է Մարկովի շղթայի ստեղծման վրա, այսինքն ալգորիթմի յուրաքանչյուր քայլին նոր ընտրված -ի իմաստը կախված է նախորդ -ից.Ալգորիթմն օգտագործում է բաշխման օժանդակ ֆունկցիան, որը կախված է -ից, և որի համար գեներացիան выборку հեշտ է (օրինակ, նորմալ բաշխումը). Այս ֆունկցիայի համար ամեն քայլին գեներացվում է -ի պատահական իմաստ։ Հետո հավանականությամբ՝
( կամ 1 հավանականությամբ եթե ), ընտրված իմաստը ընդունվում է որպես նոր՝ , հակառակ դեպքում մնում է նույնը՝ .
Օրինակ, եթե ընդունենք բաշխման նորմալ ֆունկցիան որպես օժանդակ, ապա
.
Այսպիսի ֆունկցիան տալիս է նոր նշանակություն՝կախված նախկին քայլում ստացված նշանակությունից։ Ի սկզբանե Մետրոպոլիսի ալգորիթմը պահանջում էր, որ օժանդակ ֆունկցիան լիներ սիմետրիկ՝ , սակայն Գաստինգսի ընդհանրացումը այս սահմանափակումը վերացնում է։