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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Հանգույցների հայտնաբերում
Տեսակ computational problem

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

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

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

Օրինակ[խմբագրել | խմբագրել կոդը]

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

Նկարը ցույց է տալիս ƒ ֆունկցիան, որն արտապատկերում է 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-ի վրա ցանկացած ֆունկցիա է, իսկ x0S-ի որևէ տարր։ Ցանկացած 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%-ով։