Рекурсив хамаарал, Матриц ашиглан N-р гишүүнийг Log-д олох

Бид рекуррент харьцаатай бодлого бодож байхдаа N-аар гишүүнийг DP ашиглан O(N)-д олдог. Гэвч зарим тохиолдолд хугацааны хязгаарлалт маш бага байхад 10^6-р гишүүнийг P модуль жиш гэсэн бодлогууд гарч ирдэг. Жишээ нь Фибаночийн дарааллын N-р гишүүнийг (1<=N<=1000000000) % 999983 мөн саяны Үндэсний олимпиадад бодогдсон Маяабоначийн тоо бодлого.



Энэ постыг та уншихаасаа өмнө Матрицын талаар зохих мэдлэгтэй, үржих, нэмэх хасах үйлдэлүүдийг хийж чаддаг байх ёстой шүү!



Ерөнхий тохиолдол:

Бид өгөгдсөн эсвэл өөрийн олсон рекуррент харьцаагаа ашиглан дараах шинэ харьцааг гаргаж авна.
X(i+1) = M*X(i) Энд X нь Кх1 хэмжээтэй матриц, М нь КхК хэмжээтэй тогтмол утгатай матриц. Бид тэгэхээр рекуррэнт харьцаагаа ашиглан М матрицыг олох ёстой.

  X(i+1)              X(i)
| f(n+1)   |       | f(n)   |
|  f(n)    |       | f(n-1) |
| f(n-1)   | = M x | f(n-2) |
| ......   |       | ...... |
| f(n-k+1) |       | f(n-k) |

Бодлогуудыг ерөнхийд нь дараах хэдэн төрөлд хувааж болно.



#1::

Хамгийн энгийн буюу рекуррент харьцаа дараах хэлбэрийнх байж болно.

f(n) = f(n-1) + f(n-2). Үүнийг дараах байдлаар бичиж болно. f(n+1) = f(n) + f(n-1). Тэгвэл X(i+1) болон X(i) матрицууд
дараах байдлаар бичигдэнэ.

  X(i+1)           X(i)
| f(n+1) | = M x | f(n)   | => | f(n+1) | = | a b | x | f(n)   |
| f(n)   |       | f(n-1) |    | f(n)   |   | c d |   | f(n-1) |

Тэгэхээр харж байгаа байх, К-г олохдоо тухайн харьцаа өөрөөсөө өмнөх хэдэн гишүүнээсээ хамаарч байна, тэдгээрийн гишүүдийн тоотой тэнцүү байх нь. Фибаночийн хувьд өмнөх 2 гишүүнээсээ хамаардаг тул бидний матрицууд X(Kx1), M(KxK) байх нь. Одоо М матрицыг олъё. Дээрх тэгшитгэлийн баруун талын 2 матрицыг үржүүлээд бодохоор бид дараах 2 тэгшитгэлийг гаргаж чадна.

a*f(n) + b*f(n-1) = f(n+1)

c*f(n) + d*f(n-1) = f(n) . Дарааллыхаа эхний 3-н гишүүнийг мэдэх учир орлуулаад бодохоор a=1, b=1, c=1, d=0 гэж гарна.

Одоо бид М-г мэдэх учраас дараах байдлаар бичиж болно.

| f(n+1) | = | 1 1 | x | f(n)   |
| f(n)   |   | 1 0 |   | f(n-1) |

#2::

Рекуррент харьцаа дараах хэлбэртэй байж болно. f(n) = a * f(n-1) + b * f(n-2). a, b тогтмол тоо. Дараах хэлбэртэй тэнцүү f(n+1) = a * f(n) + b * f(n-1).

Бидний олох матрицууд К нь 2 гэдгийг хялбархан харж байгаа байх. Өмнөхтэй адилхан энгийн алгебр бодоод дараах харьцаагаа гаргана.

| a   b | x |  f(n)  | = | f(n+1) |
| 1   0 |   | f(n-1) |   |  f(n)  |

#3::

f(n) = a * f(n-1) + c * f(n-3). Энд f(n-2) байхгүй үед яах вэ? Энэ дараах формтой тэнцүү.

f(n) = a * f(n-1) + 0 * f(n-2) + c * f(n-3) = f(n+1) = a * f(n) + 0 * f(n-1) + c * f(n-2)

| a  0  c |   |  f(n)  |   | f(n+1) |
| 1  0  0 | x | f(n-1) | = |  f(n)  |
| 0  1  0 |   | f(n-2) |   | f(n-1) |.

#4::

f(n) = a*f(n-1) + b*f(n-2) + c, С дурын тогтмол тоо.

| f(n+1) | = | a b 1 | x | f(n)   |
| f(n)   |   | 1 0 0 |   | f(n-1) |
| c      |   | 0 0 1 |   | c      |

#5::

Зарим тохиолдолд И тэгш үед ийм, сондгой үед ийм гэхчихлэн өөр өөр нөхцөлтэй байдаг. Энэ үед аль ч тохиолдолд нь 2 өөрөөр бодолт хий.

#6::

Рекуррент харьцаа 2 өөр функцээр тодорхойлогдож болно.

g(n) = a*g(n-1) + b*g(n-2) + c*f(n), f(n) = d*f(n-1) + e*f(n-2).

| g(n+1) |   | a b c 0 |   | g(n)   |
| g(n)   | = | 1 0 0 0 | x | g(n-1) |
| f(n+2) |   | 0 0 d e |   | f(n+1) |
| f(n+1) |   | 0 0 1 0 |   | f(n)   |

За ерөнхийдөө ойлгомжтой гэж бодож байна. Ингээд М матрицаа олцон тохиодолд яах вэ?

X(i+1) = M*X(i). Хоёр талыг хоюуланг нь М-д үрж.



M * X(i+1) = M * M * X(i)

X(i+2) = M^2 X(i)

..

X(i+k) = M^k * X(i)

Бид 2 матрицыг O(N^3)-д үрждэг. Тэгвэл К зэргийг шугаман олвол O(N^3*K). Хэрвээ бид К зэргийг Log-д олж чадвал O(N^3*LogK) хангалттай хурдан олж чадахнээ. Одоо зэргийг хэрхэн Log-д олохыг харъя.
a^k олох байг.

- Хэрэв К 0 бол мэдээж 1

- Хэрэв К тэгш тоо байвал a^k = (a(k/2)*a(k/2))

- Хэрэв К сондгой байвал a^k = (a(k-1)*a)

Үүнийг С++ дээр бичвэл:

int p(int n, int k){
    int ret = 1;
    if(k==0)return ret;
    if(k==1)return n;
    if(k%2==0) ret *= p(n, k/2)*p(n, k/2);
    else ret *= p(n, k/2)*p(n, k/2)*n;
    return ret;
}

Маяабоначийн Тоо бодлого бол дээрх формоос 3дугаар форм-д нь орох бодлого. М матрицаа ерөнхийдөө аналитик байдлаар гаргана. М матрицын эхний мөрний a болон b дэх багана дахь тоо 1 бусад нь 0. Бусад мөрийн (i-1)-р тоо нь 1 бусад нь 0 гэж матрицаа үүсгэнэ. Бодолт O(B^3 * LogN)-д шийдэгдэнэ.

Дижкстра

За энэ удаагийхаа постоор Дижкстрагийн алгоритмыг тайлбарлая. Бидэнд дараах бодлого өгөгдсөн байг.

N оройтой M ирмэгтэй, жинтэй, чиглэлт граф өгөгдсөн бол А хотоос Б хүртлэх хамгийн богино замын маршрутыг хэвлэ.

Дижкстрагийн алгоритм нь үнэндээ А хотоос ганцхан Б хот хүртлэх биш, А хотоос бүх хот хүртлэх богино замуудыг олдог. Мөн графыг чиглэлтэй мөн чиглэлгүй ч байхад бодолт хүчинтэй байдаг. Харин ганц тавьдаг шаардлага бол граф-д сөрөг утгатай жин байхыг зөвшөөрдөггүй. Сөрөг жинтэй графын хувьд Bellman Ford-н алгоритм авч үзнэ(дараа).
Алгоритм бол маш амархан, яг л түвшний нэвтрэлт шиг ажиллана (Түвшний нэвтрэлтээ сайн ойлгоогүй бол ЭНЭ постыг сайн уншаарай) , энгийн дараах Greedy санаан дээр тулгуурладаг.

Бид ямар нэгэн С орой хүртлэх богино замыг олцон гэж үзье. Мэдээж А оройгоос С орой хүртэл хэрэглэгдэж байгаа оройнуудыг дахин ашиглахгүй. Тэгвэл С оройгоос хамгийн ойрхон орших хөрш оройг нь сонгоно. Энэ оройг D гэж үзье. Энэ D маань А оройгоос D орой хүртлэх богино замыг олчихлоо гэсэн үг. Алгоритм ердөө л энэ. Маш амархан энгийн байгаа биз. Харин програм ямар үед зогсох вэ? Б орой дээр ирсэн үед эсвэл бүх орой дээр очсон үед зогсоно.
Харин код бичих, тохирсон өгөгдөлийн бүтцийг сонгосноор Дижкстраг маш хүчтэй болгож байдаг юм.

Бид түвшний нэвтрэлт хийхдээ дараалалдаа бүх хөрш оройнуудыг хийгээд явдаг. Үүнтэй яг л адилхан бид дараалалдаа хөрш оройнуудыг хийгээд, хамгийн ойрхон оройг нь дарааллаасаа хасаад явах юм. Сүүлд хасагдсан оройн бүх хөрш оройнуудыг дараалалдаа нэмээд, дарааллаас хамгийн бага жинг сонгоно гэсэн үг. Энд нэг зүйлийг нэмж тайлбарлахад ямар нэгэн орой хүртлэх богино зайг олсны дараа, дараагийн хамгийн бага оройг сонгоно гэдэг маань, тухайн сүүлд ирсэн оройн хамгийн ойрхон хөрш оройг олох биш, дараалалд хадгалагдаж байгаа бүх оройнуудаас хамгийн багыг олох ёстой шүү!!
Алгоритм ойлгомжтой байх, одоо анализ хийгээд, шаардлагатай өгөгдлийн бүтцээ үзье (Энэ хүртэл маш сайн ойгоцон байх ёстой шүү).

Алгоритмаас харахад алхам бүрдээ дараалалд байгаа жингүүдээс хамгийн багыг нь сонгоод яваад байх нь. Дарааллаа энгийн массиваар шийдэх гээд үзье. Хамгийн бага жинг шугаман хайлтаар хийвэл O(M). Олсон элементээ устгах нь мөн л O(M). Ингэвэл манай алгоритм O(NM) болохнээ. Бид түвшний нэвтрэлт дээр ашигласан QUEUE өгөгдөлийн бүтцийг хэрэглэх боломжгүй. Одоо арай өөр өгөгдлийн бүтэц авч үзье.

PRIORITY_QUEUE

Энэ өгөгдөлийн бүтцийн хийдэг үйлдэлүүд QUEUE өгөгдөлийн бүтэцтэй яг адилхан. Харин дараахь онцлогтой.

1. Хамгийн бага элементийг/их элементийг O(1);

2. Хамгийн бага/их элементийг устгах O(LogM);

3. Элемент нэмэх O(LogM).

Одоо бид алгоритмаа O(NLogM)-д шийдэх бүрэн боломжтой боллоо. Яг үнэн хэрэгтээ бол Дижкстрагийн алгоритмыг Heap өгөгдөлийн бүтэц ашигладаг ба хугацааны үнэлгээ O(NLogM) байдаг. Priority_Queue өгөгдлийн бүтэц Heap-тэй бараг адилхан бүтэц төрөл юм. Удахгүй Heap-н талаар пост оруулна. Одоо Java болон C++ дээрх кодыг сонирхуулъя.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <bitset>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <sstream>
#include <iostream>
#include <algorithm>
#define sqr(x) ((x)*(x))
#define ABS(x) ((x<0)?(-(x)):(x))
#define eps (1e-9)
#define mp make_pair
#define pb push_back
#define Pair pair<int,int> //V W
#define xx first
#define yy second
#define equal(a,b) (ABS(a-b)<eps)
using namespace std;

template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
#define Max 100010
/////////////////////////////////////////////////////////////////////////////////////////////////////
struct cmp{
   bool operator()(const Pair &a, const Pair &b)const{
       return a.yy>b.yy;
   }
};
const long long INF = 12345678987654321LL;
priority_queue< Pair, vector< Pair >, cmp>q;
vector< Pair >v[Max];
int n, m;
bool used[Max];
int uu[Max];
long long d[Max];
void dfs(int i){
    if(i==0){printf("1 ");return;}
    dfs(uu[i]);
    printf("%d ", i+1);
}
int main(int argc, char *argv[]) {
   //freopen("dij.in", "r", stdin);
   //freopen("dij.out", "w", stdout);
   scanf("%d%d", &n, &m);
   while(m--){
      int a, b, w;
      scanf("%d%d%d", &a, &b, &w);
      a--;
      --b;
      v[a].pb(mp(b, w));
      v[b].pb(mp(a, w));
   }
   uu[0] = 0;
   for(int i=0; i<n; i++)d[i] = INF;
   d[0] = 0;
   q.push(mp(0, 0));
   while(q.size()){
      int u = q.top().xx;
      q.pop();
      int sz = v[u].size();
      for(int i=0; i<sz; i++){
          int vv = v[u][i].xx;
          int ww = v[u][i].yy;
          if(!used[vv]&&d[u]+ww<d[vv]){
             d[vv] = d[u] + ww;
             q.push(mp(vv, d[vv]));
             uu[vv] = u;
          } 
      }
      used[u] = 1;
   }
   if(d[n-1]==INF)printf("-1\n");
   else
   dfs(n-1);
return 0;
}

import java.io.*;
import java.util.*;

public class test2
{

 public static void main(String[] args)
 {
  new test2().run();
 }

 PrintWriter out = null;

 void run()
 {
  Scanner in = new Scanner(System.in);
  out = new PrintWriter(System.out);

  int n = in.nextInt();
  int m = in.nextInt();

  ArrayList<Ele>[] mat = new ArrayList[n];
  for (int i = 0; i < n; i++)
   mat[i] = new ArrayList<Ele>();

  for (int i = 0; i < m; i++)
  {
   int a = in.nextInt() - 1;
   int b = in.nextInt() - 1;
   int c = in.nextInt();

   mat[a].add(new Ele(b, c));
   mat[b].add(new Ele(a, c));
  }

  boolean[] visited = new boolean[n];
  int[] prev = new int[n];
  int[] costs = new int[n];
  Arrays.fill(costs, Integer.MAX_VALUE);
  costs[0] = 0;

  prev[0] = -1;

  PriorityQueue<Vert> pq = new PriorityQueue<Vert>();
  ArrayList<Integer> al = new ArrayList<Integer>();

  pq.add(new Vert(0, 0));

  while (!pq.isEmpty())
  {
   Vert v = pq.poll();

   if (v.id == n - 1)
   {
    int k = n - 1;
    while (k >= 0)
    {
     al.add(k);
     k = prev[k];
    }
    break;
   }
   if (visited[v.id])
    continue;

   visited[v.id] = true;

   int i = v.id;
   for (Ele e : mat[i])
   {
    int j = e.y;
    int d = e.d;

    if (!visited[j] && d + v.cost < costs[j])
    {
     costs[j] = d + v.cost;
     prev[j] = i;

     pq.add(new Vert(j, costs[j]));
    }
   }
  }

  if (al.size() < 2 || al.get(al.size() - 1) != 0)
   out.println(-1);
  else
  {
   for (int i = al.size() - 1; i >= 0; i--)
    out.print((al.get(i) + 1) + " ");
  }
  out.close();
 }
}

class Ele
{
 int y;
 int d;

 public Ele(int _y, int _d)
 {
  y = _y;
  d = _d;
 }
}

class Vert implements Comparable<Vert>
{
 int id;
 int cost;

 public Vert(int _i, int _c)
 {
  id = _i;
  cost = _c;
 }

 public int compareTo(Vert o)
 {
  return cost - o.cost;
 }
}