Map (ánh xạ) trong C++

Map là một loại associative container. Mỗi phần tử của map là sự kết hợp của khóa (key value) và ánh xạ của nó (mapped value). Cũng giống như set, trong map không chứa các khóa mang giá trị giống nhau.

Trong map, các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và ánh xạ có thể khác nhau.

Và cũng giống như set, các phần tử trong map được sắp xếp theo một trình tự nào đó theo cách so sánh.

Map được cài đặt bằng red-black tree (cây đỏ đen) – một loại cây tìm kiếm nhị phân tự cân bằng. Mỗi phần tử của map lại được cài đặt theo kiểu pair (xem thêm ở thư viện utility).

Khai báo: 

#include <map>

map <kiểu_dữ_liệu_1,kiểu_dữ_liệu_2>

// kiểu dữ liệu 1 là khóa, kiểu dữ liệu 2 là giá trị của khóa.

 

Sử dụng class so sánh:

Dạng 1:

struct cmp{

bool operator() (char a,char b) {return a<b;}

};

.....

map <char,int,cmp> m;
  • Truy cập đến giá trị của các phần tử trong map khi sử dụng iterator: Ví dụ ta đang có một iterator là it khai báo cho map thì:
  • (*it).first;   // Lấy giá trị của khóa, kiểu_dữ_liệu_1
    
    (*it).second;  // Lấy giá trị của giá trị của khóa, kiểu_dữ_liệu_2
    
    (*it)          // Lấy giá trị của phần tử mà iterator đang trỏ đến, kiểu pair
    
    it->first;  // giống như (*it).first
    
    it->second; // giống như (*it).second
    
    

    Capacity:

    • size : trả về kích thước hiện tại của map. ĐPT O(1)
    • empty : true nếu map rỗng, và ngược lại. ĐPT O(1).

     

    Truy cập tới phần tử:

    • operator [khóa]: Nếu khóa đã có trong map, thì hàm này sẽ trả về giá trị mà khóa ánh xạ đến. Ngược lại, nếu khóa chưa có trong map, thì khi gọi [] nó sẽ thêm vào map khóa đó. ĐPT O(logN)

    Chỉnh sửa

    • insert : Chèn phần tử vào map. Chú ý: phần tử chèn vào phải ở kiểu “pair”. ĐPT O(logN).
    • erase :

    o xóa theo iterator ĐPT O(logN)

      1. xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).
    • clear : xóa tất cả set. ĐPT O(n).
    • swap : đổi 2 set cho nhau. ĐPT O(n).

    Operations:

    • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của map. ĐPT O(logN).
    • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)

    Chương trình demo:

    #include <iostream>
    
    #include <map>
    
    #include <vector>
    
    using namespace std;
    
    main() {
    
        map <char,int> m;
    
        map <char,int> :: iterator it;
    
        m['a']=1;
        m.insert(make_pair('b',2));
        m.insert(pair<char,int>('c',3) );
    
        // m={{'a',1}}
        // m={{'a',1};{'b',2}}
        // m={{'a',1};{'b',2};{'c',3}}
    
        cout << m['b'] << endl; m['b']++;     // In ra 2
    
        // m={{'a',1};{'b',3};{'c',3}}
    
        it=m.find('c');    // it trỏ tới phần tử khóa 'c'
    
        cout << it->first << endl; 
        cout << it->second << endl;
        // In ra 'c'
        // In ra 3
    
        m['e']=100;
        //m={{'a',1};{'b',3};{'c',3};{'e',100}}
    
        it=m.lower_bound('d'); 
        cout << it->first << endl; 
        cout << it->second << endl;
        // it tỏ tới phần tử khóa 'e'
        // In ra 'e'
        // In ra 100
        system("pause");
    }
    

Giới thiệu về Deep Learning

Thời gian gần đây, AI – Artificial Intelligence (Trí Tuệ Nhân Tạo) nổi lên như một thế lực đang làm thay đổi thế giới. Nào là chuyện VTV nói ra rả về công nghệ 4.0, rồi các báo giật tít về chuyện Facebook phải tắt AI do sợ chúng tạo ra ngôn ngữ riêng. Mới đầu nghe cụm từ Trí tuệ nhân tạo thì có vẻ rất ngầu, hay xuất hiện trong các phim bom tấn của Hollywood như anh chàng Javit của Iron-man hay lũ Ultron định xâm chiến trái đất… Tuy nhiên trí tuệ nhân tạo trong thực tế đang được sử dụng khá rộng rãi và có thể là hàng ngày, hàng giờ bạn đang dùng những ứng dụng như thế. Hệ thống tự tag khuôn mặt trong ảnh của Facebook, trợ lý ảo Siri – Cortana – Google now, google dịch…  chính là một vài sản phẩm của AI/Machine Learning/Deep Learning.

Cuối năm 2017, trí tuệ nhân tạo có bước phát triển mới khi mà một game thủ Dota 2 hàng đầu thế giới bị hạ gục bởi một trí tuệ nhân tạo. Điều này cho thấy trí tuệ nhân tạo có tiềm năng vô cùng lớn và có thể giỏi hơn con người trong một vài lĩnh vực.

OpenAI’s Dota 2 bot đã hạ gục game thủ nổi tiếng nhất thế giới trong trận chiến 1 vs 1 tại chung kết Dota 2 thế giới 2017.

Nguồn gốc trí tuệ của chú bot này chính là Deep Learning. Trong bài viết này tôi sẽ trình bày một vài kiến thức cơ bản về Trí tuệ nhân tạo/Machine Learning, đặc biệt là Deep Learning mà tôi biết. Đầu tiên các bạn hãy xem gia phả của Deep Learning nhé.

Artificial Intelligence

Trí tuệ nhân tạo nghiên cứu về các tác tử thông minh (intelligence agents) có khả năng nhận thức thế giới xung quanh, lập kế hoạch và đưa ra quyết định để đạt được mục tiêu của nó.

Hiểu một cách đơn giản hơn thì trí tuệ nhân tạo là trí tuệ được thể hiện trên các hệ thống nhân tạo. Một chiếc ô tô tự chạy không cần tài xế điều khiển, một trợ lý ảo có trả lời các câu hỏi của bạn… đó đều là những sản phẩm có trí tuệ do con người tạo nên. Người ta tạo ra AI nhằm trợ giúp hoặc thay thế con người trong một lĩnh vực nào đó. Ví dụ như:

  • Google đã và đang ứng dụng AI vào lĩnh vực xe tự hành;
  • Facebook sử dụng trí tuệ nhân tạo trong việc nhận diện hình ảnh;
  • Microsoft đang theo đuổi dự án điều trị ung thư bằng trí trí tuệ nhân tạo;
  • Google ứng dụng AI trong việc nhận diện giọng nói…

Trí tuệ nhân tạo gồm nhiều lĩnh vực con, chẳng hạn như thị giác máy tính, robot, machine learning, và xử lý ngôn ngữ tự nhiên…

Machine Learning

Machine Learning là một lĩnh vực của trí tuệ nhân tạo. Theo định nghĩa của Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed”. Machine Learning là một lĩnh vực nhỏ của Khoa Học Máy Tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải được lập trình cụ thể.

Bạn đưa cho Machine Learning rất nhiều dữ liệu – 5000 ảnh chó mèo và mong muốn chương trình của bạn thể đoán 1 bức ảnh chưa gặp bao giờ là chó hay mèo. Mỗi lần xem qua một ảnh, Machine Learning sẽ cố “ghi nhớ” đặc trưng của con chó hoặc con mèo: màu lông, vóc dáng, kích thước… Không chỉ dừng lại ở ghi nhớ, Machine Learning phải có khả năng tổng quát hóa những ảnh nó đã xem để có thể dự đoán cho những bức ảnh chưa bao giờ thấy.

Khả năng tổng quát là một khả năng tự nhiên và kì diệu của con người: bạn không thể nhìn thấy tất cả các khuôn mặt người trên thế giới nhưng bạn có thể nhận biết được một thứ có phải là khuôn mặt người hay không với xác suất đúng gần như tuyệt đối. Đỉnh cao của machine learning sẽ là mô phỏng được khả năng tổng quát hóa và suy luận này của con người. – anh Nguyễn Xuân Khánh (Machine Learning là gì?)

Bạn có thể tìm hiểu thêm về các kiến thức, thuật toán Machine Learning tại Blog Machine Learning cơ bản của anh Vũ Hữu Tiệp. Đây là nguồn kiến thức bằng tiếng Việt rất hữu ích với các bạn có ý định tìm hiểu sâu hơn về Machine Learning/Deep Learning.

Deep Learning

Deep Learning là một kỹ thuật trong Machine Learning, liên quan đến các thuật toán lấy cảm hứng từ cấu trúc và hoạt động của bộ não động vật gọi là Mạng nơ-ron nhân tạo (artificial neural networks).

Theo Wikipedia, An ANN is based on a collection of connected units or nodes called artificial neurons (analogous to biological neurons in an animal brain). Each connection (analogous to a synapse) between artificial neurons can transmit a signal from one to another. The artificial neuron that receives the signal can process it and then signal artificial neurons connected to it. Mạng nơ-ron nhân tạo được tạo nên từ một tập hợp các nơ-ron nhân tạo (tương tự nơ-ron sinh học trong não động vật) liên kết với nhau. Mỗi liên kết (tương tự một xi-náp) giữa các nơ-ron nhân tạo có thể truyền tín hiệu từ một nơ-ron đến các nơ-ron khác. Nơ-ron nhân tạo nhận tín hiệu, xử lý rồi laị truyền tín hiệu đã qua xử lý đến các nơ-ron mà nó liên kết.

Mạng nơ-ron nhân tạo có 3 lớp: input, hidden, output.

Cái gì Deep trong Deep Learning?

Các mạng nơ-ron nhân tạo truyền thống có rất ít lớp, hầu hết chỉ là 2 lớp. Cấu trúc như vậy không thích hợp với việc tính toán trên các mạng lớn hơn. Vì vậy các mạng có nhiều hơn 10 hoặc thậm chí đến 100 lớp được sử dụng. Trong Deep Learning thì mạng nơ-ron nhân tạo được chia ra thành rất nhiều lớp tạo ra một mạng nơ-ron sâu và lớn.

Tại sao vài năm nay Deep Learning mới trở thành hot trend?

Ý tưởng về mạng nơ-ron nhân tạo xuất hiện từ rất sớm, những năm 50 thế kỷ trước. Nhưng việc tạo ra những mạng nơ-ron hoạt động hiệu quả là không hề dễ dàng, nhìn chung, mạng nơ-ron sẽ cho kết quả tốt hơn khi:

  • Nhiều dữ liệu đầu vào hơn +
  • Mạng lớn hơn +
  • Khả năng tính toán của máy tính tốt hơn

Results Get Better With More Data, Larger Models, More Compute
Slide by Jeff Dean, All Rights Reserved.

Khả năng tính toán của máy tính ngày càng mạnh mẽ hay việc sử dụng các thuật toán tối ưu hơn trong Deep Learning đã góp phần vào thành công của Deep Learning như ngày nay. Bên cạnh đó là nguồn dữ liệu khổng lồ mà chúng ta có thể thu thập được dựa vào sự bùng nổ internet. Facebook có thể dễ dàng có được các bức ảnh chụp khuôn mặt của bạn từ đó tạo nên hệ thống tự động tag ảnh, hay Google biết mỗi ngày bạn tìm kiếm thứ gì, xem gì trên youtube, từ đó gợi ý cho bạn các quảng cáo hay video thú vị… Mà Deep Learning lại chính là “con quái vật” lớn lên từ những núi dữ liệu, khi chúng ta có rất nhiều dữ liệu thì Deep Learning có hiệu quả hơn hẳn các thuật toán khác.

QBMST – spoj

Đề bài:

Thuật toán:

Code:

#include <iostream>
#include <vector>
#include <algorithm> // Hàm sort
using namespace std;
 
// Cấu trúc để lưu cạnh đồ thị,
// u, v là 2 đỉnh, w là trọng số cạnh
struct edge {
    int u, v, w;
};
// Hàm so sánh để dùng trong hàm sort ở dưới
bool cmp(const edge &a, const edge &b) {
    return a.w < b.w;
}
 
// Số đỉnh tối đa trong đề bài
#define N 10005
 
// 2 mảng sử dụng trong Disjoint Set
int cha[N], hang[N];
 
// Tìm xem u thuộc cây nào
int find(int u) {
    if (cha[u] != u) cha[u] = find(cha[u]);
    return cha[u];
}
 
// Hợp nhất 2 cây chứ u và v,
// Trả về false nếu không thể hợp nhất
bool join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (hang[u] == hang[v]) hang[u]++;
    if (hang[u] < hang[v]) cha[u] = v;
    else cha[v]=u;
    return true;
}
 
int main() {
    // Thêm dòng này để cin, cout chạy nhanh
    ios::sync_with_stdio(false); cin.tie(0);
 
    // Nhập vào số đỉnh và số cạnh
    int n, m; cin >> n >> m;
 
    // Nhập danh sách các cạnh
    vector<edge> edges(m);
    for (edge &e: edges) cin >> e.u >> e.v >> e.w;
 
    // Sắp xếp lại các cạnh theo trọng số tăng dần
    sort(edges.begin(), edges.end(), cmp);
 
    // Khởi tạo cấu trúc Disjoint Set
    for (int i=1; i<=n; i++) {
        cha[i] = i;
        hang[i] = 0;
    }
 
    // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất
    int mst_weight = 0;
 
    // Duyệt qua các cạnh theo thứ tự đã sắp xếp
    for (edge &e: edges) {
        // Thử hợp nhất 2 cây chứa u và v
        if (join(e.u, e.v)) {
            // Hợp nhất thành công, ta thêm e và kết quả
            mst_weight += e.w;
        }
    }
 
    // Xuất kết quả
    cout << mst_weight;
    return 0;
}
const   fi='';
        fo='';
        maxn=10003;
        maxc=trunc(1e9);
        maxm=15000;
var     link,head,ke,ts :array[-maxm..maxm] of longint;
        i,j,n,m :longint;
        d       :array[1..maxn] of longint;
        h,p     :array[1..maxn] of longint;
        nh,res  :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     i,u,v,w :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[j]]>d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]] , p[h[j]] );
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j :longint;
begin
        j:=i+i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]]>d[h[j+1]]) then inc(j);
        if d[h[i]]>d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]] , p[h[j]]);
                        downheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else
                begin
                        upheap(p[i]);
                end;
end;
procedure process;
var     i,u,v   :longint;
begin
        for i:=1 to n do
                d[i] := maxc;
        d[1] := 0; push(1);
        repeat
                u:=pop;
                res := res + d[u];
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>ts[i] then
                                        begin
                                                d[v]:=ts[i];
                                                update(v);
                                        end;
                                i := link[i];
                        end;
        until nh=0;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

PCIRCLE – spoj

Đề bài:

Thuật toán:

  • Duyệt cấu hình tổ hợp

Code:

uses    math;
 
const   fi='';
        fo='';
        maxn=10;
 
type    data=longint;
 
var     x       :array[1..2*maxn] of longint;
        i,j,n,m :longint;
        st      :array[1..2*maxn] of longint;
        kq      :array[1..10001,1..2*maxn] of longint;
        res     :int64;
        cx      :array[1..2*maxn] of boolean;
 
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        close(input);
end;
 
function ngto(x : longint) : boolean;
var     i       :longint;
begin
        for i:=2 to trunc(sqrt(x)) do
                if x mod i = 0 then exit(false);
        exit(true);
end;
 
procedure cnkl;
begin
        if ngto(x[2*n]+x[1]) then
                begin
                        inc(res);
                        if res<=10000 then
                        kq[res] := x;
                end;
end;
 
procedure try(i : longint);
var     j :longint;
begin
        for j:= 1 to 2*n do
                if cx[j] then
                        if ngto(j+x[i-1]) then
                        begin
                                x[i] := j;
                                cx[j] := false;
                                if i=2*n then cnkl else try(i+1);
                                cx[j] := true;
                        end;
end;
procedure process;
begin
        {for i:=2 to 2*n do
                if ngto(i) then
                        begin
                                inc(m);
                                st[m] := i;
                        end;     }
        fillchar(cx,sizeof(cx),true);
        cx[1] := false;
        x[1] := 1;
        try(2);
end;
 
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        for i:=1 to min(res,10000) do
                begin
                        for j:=1 to 2*n do write(kq[i,j],' ');
                        writeln;
                end;
        close(output);
end;
 
begin
        enter;
        process;
        print;
end.

QBSCHOOL – spoj

Đề bài:

Thuật toán:

  • Gọi Gọi f[i] và d[i] lần lượt là độ dài và số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
  • Để tính d[i] ta sử dụng thuật toán Dijkstra
  • Để tính số lượng đường đi ngắn nhất giữa hai đỉnh ta tính như sau
  • Nếu d[v]>d[u]+c(u,v), ta gán d[v]=d[u]+c(u,v) và f[v]=f[u]

    Nếu d[v]=d[u]+c(u,v) thì gán f[v]=f[v]+f[u].

    (có thể xem rõ hơn ở code bên dưới)

Code:

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w,k:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(k,u,v,w);
                        add(i,u,v,w);
                        if k=2 then add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(d1[n],' ',f1[n]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef pair<long long, int> lli;
 
const long long oo = ((1 << 30)-1)*2-1;
const int max_n = 5000+1;
 
int n, m;
long long min_d, dist = 0, f[max_n];
vector<lli> adj[max_n];
 
inline void load_map()
{
    cin >> n >> m;
    int type, u, v, w;
    while (m--)
    {
        cin >> type >> u >> v >> w;
        adj[u].push_back(lli(w, v));
        if (type==2) adj[v].push_back(lli(w, u));
    }
}
 
inline void dijkstra()
{
    vector<lli>::iterator it;
    long long cuv, du, d[max_n];
    int u, v;
    priority_queue<lli, vector<lli>, greater<lli> > heap;
    for (u=1; u <= n; u++) d[u] = +oo;
    memset(f, 0, sizeof(f));
    d[1] = 0; f[1] = 1;
    heap.push(lli(0, 1));
    while (heap.size())
    {
        du = heap.top().first; u = heap.top().second;
        heap.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        for (it=adj[u].begin(); it != adj[u].end(); it++)
        {
            cuv = it->first; v = it->second;
            if (d[v]==d[u]+cuv) f[v] += f[u];
            if (d[v] > d[u]+cuv)
            {
                d[v] = d[u]+cuv;
                f[v] = f[u];
                heap.push(lli(d[v], v));
            }
        }
    }
    min_d = d[n];
}
 
main()
{
    load_map();
    dijkstra();
    cout << min_d << " " << f[n];
}

Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”,
nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching”
không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài
ra đây cũng là một nội dung được đề cập trong TAoCP – Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link).
Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP – Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được
độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng
vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay
shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không
thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ
lưu trữ ngoại vi trở nên tốn kém ( link ).
Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc
dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời
mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần
References. Một phiên bản cải tiến với kích thức mảng $N$ bất
kì sẽ được update sau.

[[code]]czo2MDQ6XCJJbnB1dDogbeG6o25nICRLXzEsIEtfMiwgLi4uLCBLX04kIMSRxrDhu6NjIHPhuq9wIHjhur9wIHbDoCBwaOG6p24gdOF7WyYqJl19u60gJEskIGPhuqduIHTDrG0uIEdp4bqjIHPhu60NCiROKzEgPSBGX3trKzF9LiBMxrB1IMO9IGluZGV4IGPhu6dhIG3huqNuZyBi4XtbJiomXX26r3QgxJHhuqd1IDEkDQoNClAxLiBbS2jhu59pIHThuqFvXSBpID0gRltrXSwgcCA9IEZbay0xXSwgcSA9IEZbay0yXQ0KUDIuIFtTe1smKiZdfW8gc8OhbmhdLg0KICAgIGlmIEtbaV0gJmx0OyBLOiBnbyB0byBQMy4NCiAgICBlbHNlIGlmIEtbaV0gJmd0OyBLOiBnbyB0byBQNC57WyYqJl19DQogICAgZWxzZTogcmV0dXJuIGk7DQpQMy4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gdHLDoWldDQogICAgaWYgcSA9IHtbJiomXX0wOiByZXR1cm4gLTENCiAgICBlbHNlOg0KICAgICAgICBpIC09IHENCiAgICAgICAgKHAsIHEpID0gKHEsIHAtcSkNCiAgICAgICAge1smKiZdfWdvIHRvIFAyDQpQNC4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gcGjhuqNpXQ0KICAgIGlmIHAgPSAxOiByZXR1cm4gLTF7WyYqJl19DQogICAgZWxzZToNCiAgICAgICAgaSArPSBxDQogICAgICAgIHAgLT0gcQ0KICAgICAgICBxIC09IHANCiAgICAgICAgZ28gdG8gUHtbJiomXX0yDQpcIjt7WyYqJl19[[/code]]

Bài tập

  • Thiết kế thuật toán cho trường hợp $N \geq 0$.
  • Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi
    nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Cây tìm kiếm Fibonacci với k=6. Source: TAoCP, Vol 3, P417.

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm
kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay
vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với
$F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),1
cây Fibonacci được xây dựng như sau:

  1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
  2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci
    bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes
    tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử
($N+1=F_{k+1} = F_7 = 13$)), số internal nodes
$F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra,
ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có
$F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal
nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo
đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận
chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể”
có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã
nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát
của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của
giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần
tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số
cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với
fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở
đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử
đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$
nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer
recurrence. Nếu sử dụng Akra-Bazzi method
thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

TODO

Mình cũng không biết nên dịch internal nodes với external nodes thế nào cho hợp (node trong và node ngoài?). ^

COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}