Sơ lược về trí tuệ nhân tạo

Trí tuệ nhân tạo có thể chia làm hai trường phái chính là: trí tuệ nhân tạo cổ điển (Classical AI, CAI) và trí tuệ nhân tạo hiện đại (Modern AI, MAI). Mặc dù tên gọi có vẻ khác biệt về mặt thời gian, hai trường phái này thực sự xuất hiện gần như cùng lúc, vào khoảng những năm 1940 khi máy tính bắt đầu được xây dựng (chúng ta không cho những công trình toán học, triết học cổ xưa về hoạt động tư duy của con người là thuộc trí tuệ nhân tạo).

Trí tuệ nhân tạo cổ điển thường dựa trên việc tìm kiếm lời giải trong một cơ sở tri thức xác định trước. Để hệ thống có thể hoạt động được, lập trình viên phải chỉ rõ cách thức để tìm kiếm, suy luận và đưa ra quyết định. Hướng tiếp cận này đã đạt được những thành công đáng kể khi xây dựng nên những hệ chuyên gia (expert systems), những chương trình chơi cờ đánh bại các nhà vô địch thế giới, …

Tuy nhiên phương pháp này gặp phải rất nhiều khó khăn khi giải quyết những bài toán mà con người có thể dễ dàng giải được nhưng chính chúng ta cũng không biết ta thực hiện nó như thế nào, ví dụ như việc dạng đồ vật hay đọc hiểu một đoạn văn bản. Để hiểu được một văn bản, theo cách tiếp cận của CAI, chúng ta phải liệt kê toàn bộ các luật ngữ pháp và ý nghĩa của từng từ trong từng ngữ cảnh khác nhau. Việc đó là vô cùng tốn kém thậm chí là không thể bởi số lượng các luật là rất lớn và số lượng ngữ cảnh còn lớn hơn rất nhiều tới mức gần như là vô hạn. Phương pháp trên còn cực kì nhạy cảm với việc thay đổi bài toán, một hệ thống nhận dạng văn bản tiếng Anh không thể sử dụng cho tiếng Việt và càng không thể sử dụng cho việc nhận dạng ảnh được, chúng ta cần phải xây dựng một cơ sở tri thức hoàn toàn mới cho mỗi bài toán mới. Do đó, chúng ta cần những phương pháp mới có khả năng tự động phát hiện các quy luật và tự động thích nghi với những bài toán mới. Đó chính là mục tiêu của trí tuệ nhân tạo hiện đại và phương pháp phổ biến nhất, gần như chiếm trọn trí tuệ nhân tạo hiện nay là học máy (Machine Learning, ML).

INFORMAC – spoj

Đề bài:

Thuật toán:

Code:

uses math;
const
  fi='';//informac.inp';
  fo='';//informac.out';
  maxm=40000;
  maxn=200;
var
  match : array[1..maxn] of longint;
  l,r : array[1..maxn] of longint;
  left,right  :  array[1..maxn] of longint;
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,x,y,u,v : longint;
  kt : boolean;
procedure enter;
  var i,j,k : longint;
  begin
    assign(input,fi);reset(input);
    read(n,m);
    for i:=1 to n do
      begin
        r[i] := n;
        right[i] := n;
      end;
    for i:=1 to n do
      begin
        l[i] := 1;
        left[i] := 1;
      end;
    for i:=1 to m do
      begin
        read(j,x,y,v);
        left[v] := max(left[v], x);
        right[v] := min(right[v], y);
        if j = 1 then
          begin
            for k := x to y do r[k] := min(r[k],v);
          end;
        if j = 2 then
          begin
            for k := x to y do l[k] := max(l[k],v);
          end;
      end;
    close(input);
  end;
Procedure Ghepcap;
  var old,i,j,nlist : longint;
      cx : array[1..maxn] of boolean;
      found : boolean;
      list : array[1..maxn] of longint;
  procedure dfs( u : longint);
    var v,i : longint;
    begin
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if cx[v] then
            begin
              cx[v] := false;
              if match[v] = 0 then found := true else dfs(match[v]);
              if found then
                begin
                  match[v] := u;
                  exit;
                end;
            end;
          i := link[i];
        end;
    end;
  begin
    for i:=1 to n do list[i] := i;
    nlist := n;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until nlist = old;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure process;
  begin
    kt := false;
    for i:=1 to n do
      if r[i] < l[i] then exit;
    for i:=1 to n do
      for j:=left[i] to right[i] do
        if (i>=l[j]) and (i<=r[j]) then
        begin
          inc(m);
          add(m,i,j);
        end;
    ghepcap;
    for i:=1 to n do
      if match[i] = 0 then exit;
    kt := true;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    if not kt then writeln(-1) else for i:=1 to n do write(match[i],' ');
  end;
begin
  enter;
  process;
  print;
end.

SAFENET2 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const
  fi='';//safenet.inp';
  fo='';//safenet.out';
  maxn=50000;
  maxm=200000;
  oo=trunc(1e9);
type
  Tedge = record
     x,y  : longint;
     end;
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,u,v,ans,top,count,dem : longint;
  num,low : array[1..maxn] of longint;
  st : array[1..maxm] of Tedge;
  free : array[-maxm..maxm] of boolean;
  pa : array[1..maxn] of longint;
procedure push(x,y : longint);
  begin
    inc(top);
    st[top].x := x;
    st[top].y := y;
  end;
procedure pop ( var x,y : longint);
  begin
    x := st[top].x;
    y := st[top].y;
    dec(top);
  end;
procedure dfs(u : longint);
  var i,v,x,y : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := oo;
    if count = 1 then
      if head[u] = 0 then
        ans := max(ans,1);
    i := head[u];
    while i <> 0 do
      begin
          v := ke[i];
          if v <> pa[u] then
          if num[v] = 0 then
            begin
              pa[v] := u;
              push(u,v);
              dfs(v);
              low[u] := min(low[u],low[v]);
              if low[v] >= num[u] then
                begin
                  dem := 0;
                  repeat
                    pop(x,y);
                    dem := dem + 1;
                  until (X=U) AND (Y=V);
                  ans := max(ans,dem+1);
                end;
            end
            else
            begin
              low[u] := min(low[u],num[v]);
            end;
        i := link[i];
      end;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure main;
var i  :  longint;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  read(n,m);
  for i := 1to m do
    begin
      read(u,v);
      add(i,u,v);
      add(-i,v,u);
    end;
  fillchar(free,sizeof(free),true);
  for i := 1 to n do
    if num[i] = 0 then
      begin
        count := 0;
        dfs(i);
      end;
  writeln(ans);
  close(input);close(output);
end;
begin
  main;
end.

QBAGENTS – spoj

Đề bài:

Thuật toán:

  • BFS

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        maxm=maxn*maxn;
        oo=trunc(1e9);
type    Tq      =record
                u1,u2,k :longint;
                end;
var     q       :array[1..2*maxn*maxn*10] of Tq;
        cx      :array[1..maxn,1..maxn,1..2] of boolean;
        f       :array[1..maxn,1..maxn,1..2] of longint;
        i,j,n,m,s,t     :longint;
        dau,cuoi,res    :longint;
        // danh sach
        link,head,ke    :array[1..maxm] of longint;
procedure enter;
var     u,v     :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m,s,t);
        for i:=1 to m do
                begin
                        read(u,v);
                        link[i] := head[u];
                        head[u] :=i;
                        ke[i] := v;
                end;
        close(input);
end;
procedure push(x,y,z:longint);
begin
        inc(cuoi);
        q[cuoi].u1:=x;
        q[cuoi].u2:=y;
        q[cuoi].k:=z;
end;
procedure process;
var     v1,v2,u1,u2,k :longint;
begin
        dau :=1; cuoi :=0;
        push(s,t,1);
        fillchar(cx,sizeof(cx),true);
        //
        for i:=1 to n do
                for j:=1 to n do
                        for k:=1 to 2 do
                                f[i,j,k] := oo;
        f[s,t,1] := 0;
        while dau<=cuoi do
                begin
                        u1 := q[dau].u1;
                        u2 := q[dau].u2;
                        k := q[dau].k;
                        inc (dau);
                        if k=1 then
                                begin
                                        i := head[u1];
                                        while i>0 do
                                                begin
                                                        v1 := ke[i];
                                                        if cx[v1,u2,2] then
                                                          begin
                                                                f[v1,u2,2] := min(f[v1,u2,2],f[u1,u2,1]+1);
                                                                push(v1,u2,2);
                                                                cx[v1,u2,2] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                        if k=2 then
                                begin
                                        i := head[u2];
                                        while i>0 do
                                                begin
                                                        v2 := ke[i];
                                                        if cx[u1,v2,1] then
                                                          begin
                                                                f[u1,v2,1] := min(f[u1,u2,2]+1,f[u1,v2,1]);
                                                                push(u1,v2,1);
                                                                cx[u1,v2,1] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                end;
        res := oo;
        for i:=1 to n do
                res := min(res,f[i,i,1]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        if res=oo then write(-1) else write(res div 2);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

WS – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';
var
  a : array[1..50000] of longint;
  val,valmax,rem : array[1..200000] of longint;
  n,k,m : longint;
 
 
procedure enter;
  var
    i,j,tmp : longint;
  begin
    n := 0;
    readln(k,m);
    i := 1;
    for j := 1 to k do
      begin
        read(tmp);
        a[i] := 1;
        inc(i,tmp);
        inc(n,tmp);
      end;
    readln;
  end;
 
procedure init(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        valmax[s] := 1;
        exit;
      end;
    mid := (l + r) div 2;
    init(2*s,l,mid);
    init(2*s+1,mid+1,r);
    valmax[s] := valmax[2*s] + valmax[2*s+1];
  end;
 
procedure init2(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        inc(val[s],a[l]);
        exit;
      end;
    mid := (l + r) div 2;
    init2(2*s,l,mid);
    init2(2*s+1,mid+1,r);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure trans(s,l,r : longint);
  var
    mid : longint;
  begin
    if (s = 0) or (l = r) then exit;
    mid := (l + r) div 2;
    inc(val[2*s],rem[s]*(mid-l+1));
    inc(val[2*s+1],rem[s]*(r-mid));
    inc(rem[2*s],rem[s]);
    inc(rem[2*s+1],rem[s]);
    rem[s] := 0;
  end;
 
procedure Jupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = valmax[s] then
          begin
            dec(val[s],r-l+1);
            dec(rem[s]);
            exit;
          end;
        if val[s] = 0 then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Jupdate(2*s,l,mid,u,v);
    Jupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure Dupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = 0 then
          begin
            inc(val[s],r-l+1);
            inc(rem[s]);
            exit;
          end;
        if val[s] = valmax[s] then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Dupdate(2*s,l,mid,u,v);
    Dupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure query(c : char; u,v : longint);
  begin
    if c = 'J' then Jupdate(1,1,n,u+1,v)
    else Dupdate(1,1,n,u+1,v);
  end;
 
procedure main;
  var
    i,u,v : longint;
    c : char;
  begin
    init(1,1,n);
    init2(1,1,n);
    for i := 1 to m do
      begin
        read(c);
        if c = 'C' then
          begin
            writeln(val[1]);
            readln;
          end
        else
          begin
            readln(u,v);
            query(c,u,v);
          end;
      end;
  end;
 
 
begin
  assign(input,fi);
  reset(input);
  enter;
  main;
  close(input);
end.

NKLINEUP – spoj

Đề bài:

Thuật toán:

  • Interval tree

Code:

#include <bits/stdc++.h>
using namespace std;
 
int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;
 
void Init_Tree(int k, int l, int r, int i)
{
    if(l>i || r<i) return;
    if(l==r)
    {
        node[k]=make_pair(a[i],a[i]);
        return;
    }
    int m=(l+r)/2;
    Init_Tree(2*k,l,m,i);
    Init_Tree(2*k+1,m+1,r,i);
    node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}
 
void Init()
{
    scanf("%d%d",&n,&q);
    a.resize(n+2);
    node.resize(4*n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Init_Tree(1,1,n,i);
    }
}
 
void Query(int k, int l, int r, int A, int B)
{
    if(l>B || r<A) return;
    if(A<=l && B>=r)
    {
        resmax=max(resmax,node[k].first);
        resmin=min(resmin,node[k].second);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,A,B);
    Query(2*k+1,m+1,r,A,B);
}
 
void Solve()
{
    for (int i=1;i<=q;i++)
    {
        int A, B;
        scanf("%d%d",&A,&B);
        resmax=0;
        resmin=10000000;
        Query(1,1,n,A,B);
        printf("%dn",resmax-resmin);
    }
}
 
int main()
{
    Init();
    Solve();
}
uses    math;
const   fi='';
        fo='';
        maxn=50000;
        maxq=200000;
type    arrp=record
                dau:longint;
                cuoi:longint;
                end;
var     i,j,n,q:longint;
        f:text;
        res1,res2:longint;
        a:array[1..maxn] of longint;
        p:array[1..maxq] of arrp;
        mind,maxd:array[1..maxn*4] of longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,q);
    for i:=1 to n do readln(f,a[i]);
    for i:=1 to q do readln(f,p[i].dau,p[i].cuoi);
    close(f);
end;
procedure update(k,l,r:longint);
var     mid:longint;
begin
    if l=r then
    begin
        maxd[k]:=a[l];
        mind[k]:=a[l];
    end
    else
    begin
        mid:=(l+r) div 2;
        update(k*2,l,mid);
        update(k*2+1,mid+1,r);
        mind[k]:=min(mind[k*2],mind[k*2+1]);
        maxd[k]:=max(maxd[k*2],maxd[k*2+1]);
    end;
end;
procedure find(k,l,r:longint);
var     mid:longint;
begin
    if (l>j) or (r<i) then exit;
    if (i<=l) and (j>=r) then
    begin
        res1:=min(res1,mind[k]);
        res2:=max(res2,maxd[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    find(k*2,l,mid);
    find(k*2+1,mid+1,r);
end;
procedure xuat;
var     k:longint;
begin
    assign(f,fo);
    rewrite(f);
    update(1,1,n);
    for k:=1 to q do
    begin
        res1:=high(longint);
        res2:=0;
        i:=p[k].dau;
        j:=p[k].cuoi;
        find(1,1,n);
        writeln(f,res2-res1);
    end;
    close(f);
end;
begin
    nhap;
    xuat;
end.

TRAKA – spoj

Đề bài:

Tóm tắt đề

Có N người thợ, M chiếc xe. Người thứ i hoàn thành việc sửa bộ phận xe mình phụ trách với tốc độ T[i]. Xe thứ j có độ rắc rối là F[j]. Thời gian người thứ i cửa xong bộ phận người i phụ trách trên xe j trong thời gian T[i] * F[j]. Các công việc được thực hiện theo thứ tự từ người 1 -> n. Người i làm việc liên tục ko đc dừng lại(tức là sửa xong xe i thì đến xe i + 1). Với mỗi thời điểm t, mỗi chiếc xe chỉ được sửa bởi tối đa 1 người. Tính thời điểm bé nhất để n người sửa xong m chiếc xe.

Dữ Liệu:

  • Dòng đầu gồm 2 số nguyên N (1 <= N <= 100 000) – số người thợ, M (1 <= M <= 100 000) – số chiếc xe cần sửa.
  • Dòng thứ i trong n dòng tiếp theo là T[i] – tốc độ sửa xong bộ phận người i phụ trách.
  • Dòng thứ j trong m dòng tiếp theo là F[j] – độ rắc rối của chiếc xe thứ j.

Kết quả:

  • Gồm 1 dòng là kết quả của bài toán.

Ví dụ:

Input:

3 3
2
1
1
2
1
1

Output:

11

Thuật toán:

Ở bài toán này thì thời điểm kết thúc công việc của người n là kết quả bài toán. Vì mỗi người thợ sẽ làm việc liên tục ko nghỉ nên ta cần tìm thời điểm bắt đầu thực hiện công việc của người n.
Gọi q[i] là tổng độ phức tạp của các chiếc xe từ 1 -> i.

Xét:
Người thứ u bắt đầu công việc từ thời điểm 0, tốc độ C. Thời điểm người u hoàn thành xe i là q[i] * C, hoàn thành xe i + 1 là q[i + 1] * c.
Người thứ v bắt đầu công việc ngay sau u, tốc độ D. Có thời điểm hoàn thành xe i là q[i] * D.
=> Để người v sửa xe i + 1 thì v cần chờ 1 khoảng thời gian là q[i + 1] * C – q[i] * D. Ta cần tìm min(q[i + 1] * C – q[i] * D).
Từ đây, ta để tính được thời điểm bắt đầu làm việc của người n là delta.
Kết quả bài toán là: delta + q[m] * t[n].

Nhận thấy độ phức tạp của thuật toán trâu bò là O(n * m) không đem lại thuật toán đủ tốt để giải bài toán. Nên ta cần tìm cách giảm độ phức tạp xuống.

Vậy, chúng ta nên làm thế nào ?? 😀 ??

Nhìn vào biểu thức q[i + 1] * C – q[i] * D có j đặc biệt ? Đây là biểu thức tích chéo của 2 vector (C; D) * (q[i]; q[i + 1]).

Coi (q[i]; q[i + 1]) là 1 điểm trên mặt phẳng tọa độ Oxy, và ta có vector u = (C; D).
Ta cần tìm điểm A(x, y) sao cho vector OA * u bé nhất. Nhận thấy điểm A cần tìm nằm trên đường lồi.

Trong hình vẽ bên dưới, đường thẳng màu xanh là đường lồi.

traka-yeulaptrinh.pw

Nhận thấy, các điểm trên đường lồi có tích chéo với (C; D) có giá trị theo hình parabol. Đến đây ta có thể áp dụng kĩ thuật chặt nhị phân hoặc tam phân để tìm đỉnh có tích chéo bé nhất.

Độ phức tạp là: O(m * log(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <long long, long long> ii;
 
const int N = 1e5 + 10;
 
int n, m, k;
ii A[N], p[N];
long long t[N];
 
ii operator - (ii a, ii b) { return  make_pair(b.first - a.first, b.second - a.second); }
long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
 
bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
 
void load() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        A[i] = make_pair(t[i - 1], t[i]);
}
 
void findConvexLine() {
    k = 0;
    p[k++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
        p[k++] = A[i];
    }
}
 
long long get(int x, int y) {
    //ii v = make_pair(x, y);
    int l = 0, r = k - 2, cur = 0;
    while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
        int mid = (l + r) >> 1;
        if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
            l = mid + 1;
            cur = l;
        } else {
            r = mid - 1;
        }
    }
    return make_pair(x, y) * p[cur];
}
 
void process() {
    findConvexLine();
    int x = 0, y = 0;
    long long delay = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &y);
        delay += get(x, y);
      //  cerr << get(x, y) << "\n";
        x = y;
    }
    long long ans = delay + 1ll * t[n] * x;
    printf("%lld\n", ans);
}
 
int main() {
 
    load();
    process();
 
    return 0;
}