Հանգույցների հայտնաբերում

Համակարգչային գիտության մեջ հանգույցների հայտնաբերումը իտեգրացված ֆունկցիայի արժեքների հաջորդականության մեջ հանգույցի որոնման ալգորիթմական խնդիրն է։

Հանգույցների հայտնաբերում
Տեսակ	computational problem?

Ցանկացած ƒ ֆունկցիայի համար, որն արտապատկերում է S վերջավոր բազմությունն ինքն իր վրա, և ցանկացած սկզբնական x₀ արժեք S-ում, իտեգրացված ֆունկցիայի արժեքների հաջորդականությունը՝

$x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots$

Ի վերջո պետք է օգտագործի միևնույն արժեքն երկու անգամ. պետք է լինի մի որոշ i ≠ j այնպես, որ x_i = x_j։ Սա մեկ անգամ կատարվելուց հետո հաջորդականությունը պետք է շարունակվի կրկնելով x_i-ից x_j−1-ը ընկած արժեքների հանգույցը։ Հանգույցի հայտնաբերումը i-ի և j-ի որոնման խնդիրն է, երբ տված են ƒ-ն ու x₀-ն։

Օրինակ

{0,1,2,3,4,5,6,7,8} բազմությունից դեպի նույնը ֆունկցիա և համապատասխան ֆունկցիոնալ գրաֆ.

Նկարը ցույց է տալիս ƒ ֆունկցիան, որն արտապատկերում է S = {0,1,2,3,4,5,6,7,8} բազմությունն ինքն իր վրա։ Երբ մեկը սկսվում է x₀ = 2 և հաջորդաբար կիրառում է ƒ-ը, մյուսը կտեսնի հետևյալ արժեքների հաջորդականությունը

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...

Հանգույցը, որն անհրաժեշտ է հայտնաբերել հանդիսանում է այս հաջորդականության 6, 3, 1 արժեքների կրկնվող ենթահաջորդականությունը։

Սահմանումներ

Դիցուք S-ը ներկայացնում է ցանկացած վերջավոր բազմություն, ƒ-ը S-ից S-ի վրա ցանկացած ֆունկցիա է, իսկ x₀-ն S-ի որևէ տարր։ Ցանկացած i > 0, ենթադրենք x_i = ƒ(x_i−1)։ Ենթադրենք μ-ն ներկայացնում է փոքրագույն ինդեքսը այնպես, որ x_μ-ն հայտնվում է անսահման հաճախ x_i արժեքների բազմությունում, և դիցուք λ (հանգույցի երկարությունը) ներկայացնում է փոքրագույն ամբողջ թիվը այնպես, որ x_μ = x_λ+μ։ Հանգույցի հայտնաբերման խնդիրը կայանում է λ-ի և μ-ի որոնման մեջ։

Նույն խնդիրը հանդես է գալիս գրաֆների տեսությունում, կառուցելով ֆունկցիոնալ գրաֆ, որի գագաթները S բազմության տարրերն են և որը կողերը արտապատկերում են տարրերը համապատասխան ֆունկցիայի արժեքի, ինչպես պատկերված է նկարում։ Ցանկացած x₀ գագաթով սկսվող հասանելի գագաթների բազմությունը ձևավորում է ենթագրաֆ կառուցվածքով նման ρ. x₀-ից λ գագաթների հանգույց եղած μ երկարության ճանապարհը։

Ալգորիթմներ

Եթե մուտքը տված է որպես ƒ-ի հաշվարկման պրոցեդուրա, ապա հանգույցի հայտնաբերումը կարող է հեշտորեն լուծվել օգտագործելով միայն λ+μ ֆունկցիայի կիրառություններ, պարզապես հաշվելով x_i արժեքների հաջորդականությունը և օգտագործելով այնպիսի տվյալների կառուցվածք՝ ինչպիսին է հեշ-աղյուսակը, այս արժեքները պահելու և ստուգելու, թե արդյոք յուրաքանչյուր արժեք պահպանվել է արդեն։

Բրենտի ալգորիթմ

Ռիչարդ Պ. Բրենտը նկարագրել է հանգույցների հայտնաբերման այլընտրանքային ալգորիթմ, որը, ինչպես և կրիայի և ճագարի ալգորիթմը, պահանջում է միայն երկու ցուցիչ բազմության մեջ։ Ինչևէ, այն հիմնված է այլ սկզբունքի վրա. որոնում է փոքրագույն 2ⁱ-ն, որն ավելի մեծ է, քան λ-ն և μ-ն։ i = 0, 1, 2, և այլն, ալգորիթմը համեմատում է x_2ⁱ−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%-ով։