Հանգույցների հայտնաբերում
Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
Հանգույցների հայտնաբերում | |
---|---|
Տեսակ | computational problem? |
Համակարգչային գիտության մեջ հանգույցների հայտնաբերումը իտեգրացված ֆունկցիայի արժեքների հաջորդականության մեջ հանգույցի որոնման ալգորիթմական խնդիրն է։
Ցանկացած ƒ ֆունկցիայի համար, որն արտապատկերում է S վերջավոր բազմությունն ինքն իր վրա, և ցանկացած սկզբնական x0 արժեք S-ում, իտեգրացված ֆունկցիայի արժեքների հաջորդականությունը՝
Ի վերջո պետք է օգտագործի միևնույն արժեքն երկու անգամ. պետք է լինի մի որոշ i ≠ j այնպես, որ xi = xj։ Սա մեկ անգամ կատարվելուց հետո հաջորդականությունը պետք է շարունակվի կրկնելով xi-ից xj−1-ը ընկած արժեքների հանգույցը։ Հանգույցի հայտնաբերումը i-ի և j-ի որոնման խնդիրն է, երբ տված են ƒ-ն ու x0-ն։
Օրինակ[խմբագրել | խմբագրել կոդը]
Նկարը ցույց է տալիս ƒ ֆունկցիան, որն արտապատկերում է S = {0,1,2,3,4,5,6,7,8} բազմությունն ինքն իր վրա։ Երբ մեկը սկսվում է x0 = 2 և հաջորդաբար կիրառում է ƒ-ը, մյուսը կտեսնի հետևյալ արժեքների հաջորդականությունը
- 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...
Հանգույցը, որն անհրաժեշտ է հայտնաբերել հանդիսանում է այս հաջորդականության 6, 3, 1 արժեքների կրկնվող ենթահաջորդականությունը։
Սահմանումներ[խմբագրել | խմբագրել կոդը]
Դիցուք S-ը ներկայացնում է ցանկացած վերջավոր բազմություն, ƒ-ը S-ից S-ի վրա ցանկացած ֆունկցիա է, իսկ x0-ն S-ի որևէ տարր։ Ցանկացած i > 0, ենթադրենք xi = ƒ(xi−1)։ Ենթադրենք μ-ն ներկայացնում է փոքրագույն ինդեքսը այնպես, որ xμ-ն հայտնվում է անսահման հաճախ xi արժեքների բազմությունում, և դիցուք λ (հանգույցի երկարությունը) ներկայացնում է փոքրագույն ամբողջ թիվը այնպես, որ xμ = xλ+μ։ Հանգույցի հայտնաբերման խնդիրը կայանում է λ-ի և μ-ի որոնման մեջ։
Նույն խնդիրը հանդես է գալիս գրաֆների տեսությունում, կառուցելով ֆունկցիոնալ գրաֆ, որի գագաթները S բազմության տարրերն են և որը կողերը արտապատկերում են տարրերը համապատասխան ֆունկցիայի արժեքի, ինչպես պատկերված է նկարում։ Ցանկացած x0 գագաթով սկսվող հասանելի գագաթների բազմությունը ձևավորում է ենթագրաֆ կառուցվածքով նման ρ. x0-ից λ գագաթների հանգույց եղած μ երկարության ճանապարհը։
Ալգորիթմներ[խմբագրել | խմբագրել կոդը]
Եթե մուտքը տված է որպես ƒ-ի հաշվարկման պրոցեդուրա, ապա հանգույցի հայտնաբերումը կարող է հեշտորեն լուծվել օգտագործելով միայն λ+μ ֆունկցիայի կիրառություններ, պարզապես հաշվելով xi արժեքների հաջորդականությունը և օգտագործելով այնպիսի տվյալների կառուցվածք՝ ինչպիսին է հեշ-աղյուսակը, այս արժեքները պահելու և ստուգելու, թե արդյոք յուրաքանչյուր արժեք պահպանվել է արդեն։
Բրենտի ալգորիթմ[խմբագրել | խմբագրել կոդը]
Ռիչարդ Պ. Բրենտը նկարագրել է հանգույցների հայտնաբերման այլընտրանքային ալգորիթմ, որը, ինչպես և կրիայի և ճագարի ալգորիթմը, պահանջում է միայն երկու ցուցիչ բազմության մեջ։ Ինչևէ, այն հիմնված է այլ սկզբունքի վրա. որոնում է փոքրագույն 2i-ն, որն ավելի մեծ է, քան λ-ն և μ-ն։ i = 0, 1, 2, և այլն, ալգորիթմը համեմատում է x2i−1-ը յուրաքանչյուր հաջորդիվ հաջորդականության արժեքի հետ մինչև հաջորդ երկուսի աստիճանը, դադարելով, երբ գտնում է համապատասխանություն։
Հետևյալ ծրագրային կոդը գրված Python-ով ցուցադրում է այս մեթոդը ավելի մանրամասն
def brent(f, x0):
# հիմնական փուլ. որոնում է երկուսի հերթական աստիճանը
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # ժամանակն է արդյո՞ք սկսել երկուսի նոր աստիճան
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Որոնել լյամբդայի երկարության առաջին կրկնության դիրքը
mu = 0
tortoise = hare = x0
for i in range(lam):
# range(lam) բազմապատկում է ցուցակը այս արժեքների հետ 0, 1, ... , lam-1
hare = f(hare)
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
Բրենտի ալգորիթմի իրականացումը C++ լեզվով (Boost գրադարանի տարբերակ).
template <class F, class T>
std::pair<T, T> brent_find_minima(F f, T min, T max, int bits, boost::uintmax_t& max_iter)
{
BOOST_MATH_STD_USING
bits = (std::min)(policies::digits<T, policies::policy<> >() / 2, bits);
T tolerance = static_cast<T>(ldexp(1.0, 1-bits));
T x; // minima so far
T w; // second best point
T v; // previous value of w
T u; // most recent evaluation point
T delta; // The distance moved in the last step
T delta2; // The distance moved in the step before last
T fu, fv, fw, fx; // function evaluations at u, v, w, x
T mid; // midpoint of min and max
T fract1, fract2; // minimal relative movement in x
static const T golden = 0.3819660f; // golden ratio, don't need too much precision here!
x = w = v = max;
fw = fv = fx = f(x);
delta2 = delta = 0;
uintmax_t count = max_iter;
do{
// get midpoint
mid = (min + max) / 2;
// work out if we're done already:
fract1 = tolerance * fabs(x) + tolerance / 4;
fract2 = 2 * fract1;
if(fabs(x - mid) <= (fract2 - (max - min) / 2))
break;
if(fabs(delta2) > fract1)
{
// try and construct a parabolic fit:
T r = (x - w) * (fx - fv);
T q = (x - v) * (fx - fw);
T p = (x - v) * q - (x - w) * r;
q = 2 * (q - r);
if(q > 0)
p = -p;
q = fabs(q);
T td = delta2;
delta2 = delta;
// determine whether a parabolic step is acceptible or not:
if((fabs(p) >= fabs(q * td / 2)) || (p <= q * (min - x)) || (p >= q * (max - x)))
{
// nope, try golden section instead
delta2 = (x >= mid) ? min - x : max - x;
delta = golden * delta2;
}
else
{
// whew, parabolic fit:
delta = p / q;
u = x + delta;
if(((u - min) < fract2) || ((max- u) < fract2))
delta = (mid - x) < 0 ? (T)-fabs(fract1) : (T)fabs(fract1);
}
}
else
{
// golden section:
delta2 = (x >= mid) ? min - x : max - x;
delta = golden * delta2;
}
// update current position:
u = (fabs(delta) >= fract1) ? T(x + delta) : (delta > 0 ? T(x + fabs(fract1)) : T(x - fabs(fract1)));
fu = f(u);
if(fu <= fx)
{
// good new point is an improvement!
// update brackets:
if(u >= x)
min = x;
else
max = x;
// update control points:
v = w;
w = x;
x = u;
fv = fw;
fw = fx;
fx = fu;
}
else
{
// Oh dear, point u is worse than what we have already,
// even so it *must* be better than one of our endpoints:
if(u < x)
min = u;
else
max = u;
if((fu <= fw) || (w == x))
{
// however it is at least second best:
v = w;
w = u;
fv = fw;
fw = fu;
}
else if((fu <= fv) || (v == x) || (v == w))
{
// third best:
v = u;
fv = fu;
}
}
}while(--count);
max_iter -= count;
return std::make_pair(x, fx);
}
Ինչպես և կրիայի և ճագարի ալգորիթմը, սա ևս ցուցիչ ալգորիթմ է, որն օգտագործում է O(λ+μ) թեստեր և ֆունկցիայի գնահատումներ և O(1) հիշողության տարածք։ Դժվար չէ ցույց տալ, որ ֆունկցիայի գնահատումների քանակը երբեք չի գերազանցի Ֆլոյդի ալգորիթմինը։ Բրենտը պնդում է, որ միջին հաշվով, նրա հանգույցների հայտնաբերման ալգորիթմը աշխատում է 36% ավելի արագ, քան Ֆլոյդինը և որ արագությունը գերազանցում է Փոլլարդի ռո ալգորիթմը մոտ 24%-ով։