Phân tích và thiết kế giải thuật : Độ phức tạp của các giải thuật đồ thị - Chương 4

Chia sẻ: Nguyen Bac A. Châu | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

192
lượt xem 68
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 4: Phân tích độ phức tạp của các giải thuật đồ thị. Có nhiều bài toán được định nghĩa theo đối tượng và kết nối giữa các đối tượng ấy.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phân tích và thiết kế giải thuật : Độ phức tạp của các giải thuật đồ thị - Chương 4

Ch ng 4 ph c t p c a các gi i thu t th 1
N i dung 1. Các gi i thu t th c n b n 2. th có tr ng s 3. th có h ng 2
1.Các gi i thu t th c n b n Có nhi u bài toán c nh ngh a theo it ng và các k t n i gi a các i t ng y. M t th là m t i t ng toán h c mà mô t nh ng bài toán nh v y. Các ng d ng trong các lãnh v c: Giao thông Vi n thông i nl c M ng máy tính C s d li u Trình biên d ch Các h i u hành Lý thuy t th 3
M t thí d A H I B C G D E J K F L M Hình 4.1a M t th thí d 4
Thu t ng M t th là m t t p các nh và các c nh. Các nh là nh ng i t ng n mà có th có tên và có m t s tính ch t khác và c nh là ng k t n i gi a hai nh. M t l i i t x n y trong m t th là m t danh sách nh ng nh mà nh ng nh k ti p nhau c k t n i nh vào nh ng c nh trên th . M t th là liên thông n u có m t l i i t m i nút n m t nút khác trong th . M t th mà không liên thông thì bao g m nhi u thành ph n liên thông. M tl i i n là m t l i i mà trên ó không có nh nào l p l i. 5
Thu t ng (tt.) M t chu trình (cycle ) là m t l i i n ngo i tr nh u tiên và nh cu i cùng trùng nhau (m t l i i t m t nh quay v chính nó). M t th không có chu trình c g i là cây (tree). M t nhóm các cây không liên thông c g i là r ng ( forest ). Cây bao trùm c a m t th là m t th con mà ch a t t c các nh trong cây nh ng m t s c nh ch m n m i nh. G is nh trong m t th là V, s c nh là E, s c nh c a th có th có t 0 n V (V-1)/2. (Ch ng minh truy ch ng). th có t t c m i c nh hi n di n gi a m i c p nh c g i là th y (complete graphs). 6
Thu t ng (tt.) Các th v i s c nh t ng i ít c g i là th th a; các th v i ch m t s ít c nh m t i c g i là th dày. Các th mô t cho n gi là nh ng th vô h ng (undirected graphs). Trong các th có tr ng s (weighted graphs), nh ng giá tr s (tr ng s ) c g n vào m i c nh di n t thí d kho ng cách hay chi phí. Trong th có h ng (directed graphs) các c nh là “m t chi u”: m t c nh i t x sang y ch không ph i i t y sang x. Các th có h ng, có tr ng s còn c g i là các m ng (networks). 7
Cách bi u di n th Ta ph i ánh x các tên nh thành nh ng s nguyên trong t m tr gi a 1 và V. Gi s có t n t i hai hàm: - hàm index: chuy n i t tên nh thành s nguyên - hàm name: chuy n i s nguyên thành tên nh. Có hai cách bi u di n th : - dùng ma tr n k c n - dùng t p danh sách k c n 8
Cách bi u di n ma tr n k c n A B C D E F G H I J K L M M t ma tr n V A 1 1 1 0 0 1 1 0 0 0 0 0 0 B 1 1 0 0 0 0 0 0 0 0 0 0 0 hàng V c t ch a C 1 0 1 0 0 0 0 0 0 0 0 0 0 các giá tr Boolean D 0 0 0 1 1 1 0 0 0 0 0 0 0 mà a[x, y] là true if E 0 0 0 1 1 1 1 0 0 0 0 0 0 n ut nt im t F 1 0 0 1 1 1 0 0 0 0 0 0 0 c nh t nh x n G 1 0 0 0 1 0 1 0 0 0 0 0 0 H 0 0 0 0 0 0 0 1 1 0 0 0 0 nh y và false n u I 0 0 0 0 0 0 0 1 1 0 0 0 0 ng c l i. J 0 0 0 0 0 0 0 0 0 1 1 1 1 K 0 0 0 0 0 0 0 0 0 1 1 0 0 Hình 4.1b: Ma tr n k L 0 0 0 0 0 0 0 0 0 1 0 1 1 c nc a th hình M 0 0 0 0 0 0 0 0 0 1 0 1 1 4.1a 9
Ghi chú v cách bi u di n ma tr n k c n M i c nh t ng ng v i 2 bit trong ma tr n: m i c nh n i gi a x và y c bi u di n b ng giá tr true t i c a[x, y] và a[y, x]. ti n l i gi nh r ng có t n t i m t c nh n i m i nh v chính nó. L i bi u di n này ch thích h p khi các th là d y. 10
Gi i thu t program adjmatrix (input, output); const maxV = 50; var j, x, y, V, E: integer; a: array[1..maxV, 1..maxV] of boolean; begin readln (V, E); for x: = 1 to V do /*initialize the matrix */ for y: = 1 to V do a[x, y]: = false; for x: = 1 to V do a[x, y]: = true; for j: = 1 to E do begin readln (v1, v2); x := index(v1); y := index(v2); a[x, y] := true; a[y, x] := true end; end. 11
Cách bi u di n b ng t p danh sách k c n Trong cách bi u di n này, m i nh mà n i t i m t nh c k t thành m t danh sách k c n (adjacency-list ) cho nh ó. program adjlist (input, output); const maxV = 100; type link = node node = record v: integer; next: link end; var j, x, y, V, E: integer; t, x: link; adj: array[1..maxV] of link; 12
begin readln(V, E); new(z); z.next: = z; for j: = 1 to V do adj[j]: = z; for j: 1 to E do begin readln(v1, v2); x: = index(v1); y: = index(v2); new(t); t.v: = x; t.next: = adj[y]; adj[y]: = t; /* insert x to the first element of y’s adjacency list */ new(t); t.v = y; t.next: = adj[x]; adj[x]:= t; /* insert y to the first element of x’s adjacency list */ end; end. 13
a b c d e f g h i j k l m f a a f g a e i h k j j j c e f e a l m l b d d m g Hình 4.1c: Bi u di n b ng t p danh sách k c n c a th hình 4.1 14
Các ph ng pháp duy t th Duy t hay tìm ki m trên th : vi ng m i nh/nút trong th m t cách có h th ng. Có hai cách chính duy t th : - duy t theo chi u sâu tr c (depth-first-search ) - duy t theo chi u r ng tr c (breadth-first-search). 15
Duy t theo chi u sâu tr c – gi i thu t quy procedure dfs; procedure visit(n:vertex); begin add n to the ready stack; while the ready stack is not empty do get a vertex from the stack, process it, and add any neighbor vertex that has not been processed to the stack. if a vertex has already appeared in the stack, there is no need to push it to the stack, but it is moved to the top of the stack. end; begin Initialize status; for each vertex, say n, in the graph do if the status of n is “not yet visited” then visit(n) end; 16
Tìm ki m theo chi u sâu tr c – bi u di n danh sách k c n procedure list-dfs; var id, k: integer; val: array[1..maxV] of integer; procedure visit (k: integer); var t: link; begin id: = id + 1; val[k]: = id; /* change the status of k to “visited” */ t: = adj[k]; / * find the neighbors of the vertex k */ while t z do begin if val[t .v] = 0 then visit(t.v); t: = t.next end end; 17
begin id: = 0; for k: = 1 to V do val[k]: = 0; /initialize the status of all vetices */ for k: = 1 to V do if val[k] = 0 then visit(k) end; Ghi chú: M ng val[1..V] ch a tr ng thái c a các nh. val[k] = 0 n u nh k ch a h c vi ng (“not yet visited”), val[k] 0 n u nh k ã c vi ng. val[k]: = j ngh a là nh jth mà c vi ng trong quá trình duy t là nh k. 18
A A A A E F F F A A A A G G G G E E E E F F F F A A A A G G G G D E D E D E D E F F F F A A A A C G C G B C G B C G D E D E D E D E F F F F 19 Hình 4.2 Duy t theo chi u sâu tr c
Nh v y k t qu c a gi i thu t duy t DFS trên th cho hình 4.1a v i t p danh sách k c n cho hình 4.1c là AFEGDCG L u ý: th t c a các nh trong các danh sách k c n có nh h ng n th t duy t c a các nh khi áp d ng DFS. 20