Thuật toán tìm kiếm

Chia sẻ: Huynh Phuong | Ngày: | Loại File: DOC | Số trang:10

Thêm vào BST

Báo xấu

186
lượt xem 40
download

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

không dựa trên tư tưởng của các thuật toán tìm kiếm theo chiều rộng hoặc chiều sâu. Trong các thuật toán này, tại từng bước của quá trình xây dựng T luôn là một cây, chỉ có điều kiện về số...

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán tìm kiếm

không dựa trên tư tưởng của các thuật toán tìm kiếm theo chiều rộng hoặc chiều sâu. Trong các thuật toán này, tại từng bước của quá trình xây dựng T luôn là một cây, chỉ có điều kiện về số đỉnh của T phải đến bước cuối cùng mới thỏa mãn. Còn trong thuật toán Kruskal, trong quá trình xây dựng T có thể chưa là cây, nó chỉ thỏa mãn điều kiện không có chu trình. [sửa] Mô tả Giả sử G liên thông có n đỉnh. Gọi T là cây bao trùm sẽ xây dựng. 1. Khởi tạo: T lúc đầu là một đồ thị rỗng. 2. Nếu T đã gồm đúng n-1 cạnh của G thì T là cây bao trùm cần tìm. Kết thúc. 3. Nếu G còn chưa đủ n-1 cạnh, thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn các cạnh của G chưa thuộc T. Trong các cạnh của G chưa thuộc T có các cạnh không tạo ra chu trình với các cạnh đã có trong T, Chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ sung (cùng với các đỉnh chưa thuộc T của nó) vào T. 4. Quay lại 2. Một vài tác giả có cách trình bày khác của giải thuật Kruskal, tuy bản chất quá trình là giống nhau 1. Khởi tạo: T lúc đầu gồm tất cả các đỉnh của G và chưa có cạnh nào,như vây T lúc đầu là một rừng n cây,mỗi cây gồm đúng một đỉnh. 2. Nếu T chỉ gồm một cây thì dừng 3. Nếu T gồm nhiều hơn một cây, chọn cạnh nhỏ nhất của G có hai đầu mút thuộc hai cây khác nhau bổ sung vào T, khi đó hai cây được hợp thành một cây. 4. Quay lại 2. [sửa] Giả mã [sửa] Phân tích • Khi lập trình cài đặt giải thuật Kruskal có hai điểm mấu chốt cần chú ý: 1. Trong mỗi lần lặp ta chọn cạnh có trọng số nhỏ nhất đưa vào T. 2. Cạnh được chọn đưa vào T phải không tạo thành chu trình với các cạnh đã có trong T. • Vấn đề thứ nhất được giải quyết gần giống như trong giải thuật Prim là tạo một hàng đợi có ưu tiên trên danh sách các cạnh. Tuy nhiên có thể ngay từ đầu sắp xếp các cạnh theo thứ tự tăng dần của trọng số. Để giải quyết vần đề thứ hai, ta quay lại chú ý rằng, khác với giải thuật Prim, tại mỗi bước của giải thuật Kruskal, tập các đỉnh và các cạnh đã được đưa vào T chưa là cây
mà chỉ thỏa mã tính không chu trình. Như vậy tại mỗi bước T là một rừng, T = . • Bây giờ xét một cạnh e = (u,v) của G chưa nằm trong T có 3 khả năng xảy ra: 1. Cả u,v chưa thuộc T. Khi đó nếu bổ sung e vào T thì không có chu trình, nhưng chính cạnh e tạo thành một cây con mới. 2. Một đỉnh chẳng hạn u thuộc T, còn đỉnh kia v không thuộc T. Việc bổ sung cạnh e và đỉnh v vào T (vào cây con chứa đỉnh u) không tạo ra chu trình. 3. Cả u,v đều nằm trong T. Khi đó 1. Nếu u,v nằm trong cùng một cây con Tk ta không thể bổ sung canh e vào T. 2. Nếu u,v nằm trong hai cây con khác nhau thì có thể bổ sung cạnh e vào T (hai đỉnh u, v đã nằm trong T không cần bổ sung, sau khi bổ sung hai cây con sẽ hợp lại thành một cây. [sửa] Tổ chức dữ liệu • Giả sử G=(V,E)là đồ thị vô hướng n đỉnh, cho bằng danh sách kề Ajd(u), . Các đỉnh của G được đánh số từ 1 đến n, nghiã là V=V[1..n];Ta cũng kí hiệu Index(u) là chỉ số của đỉnh u trong mảng V. Hàm trọng số W(u,v) xác định trên các cạnh . Với mỗi cạnh e=(u,v) ký hiệu e.x u, e.y=v là hai đỉnh liên thuộc với cạnh e. • Các biến sau được đưa vào o Hàng đợi Q của các cạnh xếp theo thứ tự trọng số từ nhỏ đến lớn. o Với mỗi cây con, hàm PARENTS(u) xác định trên V, biểu diễn chỉ số của đỉnh cha của đỉnh u trong một cây. Riêng đỉnh gốc u của mỗi cây hàm PARENTS(u)lưu trữ số đỉnh trong cây với dấu âm. [sửa] Mã Procedure Kruskal (G) T = V; Q =Sort(E) /* Tạo n cây, mỗi cây gồm một đỉnh*/ For each u of X do Parent(u):=-1; m = |E| For j:=1 to m do { u:=NodeStart(Q(j)); V:=NodeEnd(Q(j)) If Find_tree(u)Find_tree(V) then T:=T U Q[j]; Union(u,v;) Ghi chú:
• Thủ tục Find_set(u) tìm đỉnh gốc của cây chứa đỉnh u. (xem cây biểu diễn tập hợp). • Thủ tục Union(u,v),ghép cây chứa v vào cây chứa u (xem cây biểu diễn tập hợp). Lấy từ “http://vi.wikipedia.org/wiki/C%C3%A2y_bao_tr%C3%B9m_nh%E1%BB %8F_nh%E1%BA%A5t” Thể loại: Cây (cấu trúc) | Bài toán thời gian đa thức | Giải thuật lý thuyết đồ thị ------------------------------------------------------------------------------- #include char Dinhdau[] ={‘a’,’a’,’a’,’b’,’b’,’c’, ’c’,’d’}; char Dinhcuoi[] ={‘b’,’c’,’d’,’c’,’e’,’d’, ’f’,’g’}; int Trongso[] ={10, 1, 10,5,10,4,2,10}; int n = sizeof(Trongso)/sizeof(int); int CanhCay = 7; int Cay[100] ;// canh thu may char Dinh[] = {‘a’,’b’,’c’,….}; int TPLT[] = {1,2,3,4,5,6,7}; int SapXep(){ for (int i = 0; i
int main(){ int Canh = 0; SapXep(); int i = 0; while (Canh
Phải có những chức năng cơ bản sau: - Cập nhật dữ liệu về đồ thị. - Biểu diễn đồ thị trên màn hình. - Kiểm tra tính liên thông. - Cho phép tìm cây có trọng lượng nhỏ nhất. MÔI TRƯỜNG CÀI ĐẶT : Ngôn ngữ lập trình sử dụng : Pascal, C, C ++ TÀI LIỆU THAM KHẢO : 1. Bài giảng: Lý Thuyết Đồ thị - Phan Tấn Tài 2. Lý Thuyết Đồ Thị - PTs. Nguyễn Cam & PTs. Chu Đức Khánh. 3. Tóan rời rạc – Nguyễn Đức Nghĩa & Nguyễn Tô Thành 4. “Tóan rời rạc ứng dụng trong tin học” dịch từ quyển Discrete Methamatíc and Its Application – Mc Graw Hill. 5. Data Structures and Algorithms - A. Aho, J. Ullman 6. Chương trình = Cấu trúc dữ liệu + Giải thuật – Wirth ---------------------------------------------------------------- #include char Dinhdau[] ={'a','a' ,'a','b','b','c','c','d','e','e'}; char Dinhcuoi[] ={'b','e','f','c','e','d','e','e','f','g'}; int Trongso[] ={3,5,7,10,12,12,13,16,16,16}; int n = sizeof(Trongso)/sizeof(int); int CanhCay = 9; int Cay[100] ; char Dinh[] = {'a','b','c','d','e','f'}; // sao lai char dinh la sao a int TPLT[] = {1,2,3,4,5,6,7,8,9,10}; // cai TPLT nay la cai gi a int SapXep() { for ( int i = 0; i
{ if (Trongso[min]>Trongso[j]) min = j; } if ( min != i) { int tg = Trongso[i] ; Trongso[i] = Trongso[min] ; Trongso[min] = tg; char ch = Dinhdau[i]; Dinhdau[i] = Dinhdau[min] ; Dinhdau[min] = ch; ch = Dinhcuoi[i]; Dinhcuoi[i] = Dinhcuoi[min]; Dinhcuoi[min] = ch; } } } //------------------------------------------------------------- -------------- void HopTPLT( int TP1 , int TP2 ) { for ( int i = 0;i
nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T ko tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T. Cứ làm nh ư vậy cho tới khi : _kết nạp được n-1 cạnh vào trong T thì ta được T là cây khung nhỏ nh ất _nếu chưa kết nạp đủ n-1 cạnh nhưng hễ cứ kết nạp thêm 1 cạnh b ất kỳ trong số các cạnh còn lại thì sẽ tạo thành chu trình đơn. Với tình huống này thì b ạn s ẽ nhận ra ngay là đồ thị G ko liên thông và như thế thì đương nhiên là việc tìm kiếm cây khung thất bại rồi, ko phải bàn thêm nữa. Như vậy thì bạn phải xác định được 2 vấn đề sau khi cài đặt thuật toán Kruskal : + Làm thế nào để xét dc các cạnh từ cạnh có trọng số nhỏ tới cạnh có trọng số lớn ? Bạn có thể làm dc điều này bằng cách sắp xếp danh sách cạnh theo th ứ tự không giảm của trọng số, sau đó duyệt từ đầu tới cuối ds cạnh + Làm thế nào để kt xem việc thêm 1 cạnh có tạo thành chu trình đơn trong T hay không ? Như ta đã biết thì các cạnh trong T ở các bước sẽ tạo thành 1 r ừng, tức là đồ thị ko có chu trình đơn. Muốn thêm 1 cạnh (u,v) nào đó mà vào T mà ko tạo thành chu trình đơn thì (u,v) bắt buộc phải nối 2 cây khác nhau c ủa r ừng T, bởi vì nếu u và v thuộc cùng 1 cây thì sẽ tạo thành chu trình đơn trong cây đó. Như vậy nếu bạn giải quyết được 2 vấn đề trên thì coi như bạn đã thành công. ------------------------------ không dựa trên tư tưởng của các thuật toán tìm kiếm theo chiều rộng hoặc chiều sâu. Trong các thuật toán này, tại từng bước c ủa quá trình xây dựng T luôn là một cây, chỉ có điều kiện về số đỉnh của T phải đến bước cuối cùng mới thỏa mãn. Còn trong thuật toán Kruskal, trong quá trình xây dựng T có thể chưa là cây, nó chỉ thỏa mãn điều kiện không có chu trình. [sửa]Mô tả Giả sử G liên thông có n đỉnh. Gọi T là cây bao trùm sẽ xây dựng. 1. Khởi tạo: T lúc đầu là một đồ thị rỗng. 2. Nếu T đã gồm đúng n-1 cạnh của G thì T là cây bao trùm cần tìm. Kết thúc. 3. Nếu G còn chưa đủ n-1 cạnh, thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn các cạnh của G chưa thuộc T. Trong các cạnh của G chưa thuộc T có các cạnh không tạo ra chu trình với các cạnh đã có trong T, Chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ sung (cùng với các đỉnh chưa thuộc T của nó) vào T. 4. Quay lại 2. Một vài tác giả có cách trình bày khác của giải thuật Kruskal, tuy bản chất quá trình là giống nhau 1. Khởi tạo: T lúc đầu gồm tất cả các đỉnh của G và chưa có cạnh nào,như vây T lúc đầu là một rừng n cây,mỗi cây gồm đúng một đỉnh. 2. Nếu T chỉ gồm một cây thì dừng 3. Nếu T gồm nhiều hơn một cây, chọn cạnh nhỏ nhất của G có hai đầu mút thuộc hai cây khác nhau bổ sung vào T, khi đó hai cây được hợp thành một cây.
4. Quay lại 2. [sửa]Giả mã [sửa]Phân tích  Khi lập trình cài đặt giải thuật Kruskal có hai điểm mấu chốt cần chú ý: 1. Trong mỗi lần lặp ta chọn cạnh có trọng số nhỏ nhất đưa vào T. 2. Cạnh được chọn đưa vào T phải không tạo thành chu trình với các cạnh đã có trong T.  Vấn đề thứ nhất được giải quyết gần giống như trong giải thuật Prim là tạo một hàng đợi có ưu tiên trên danh sách các cạnh. Tuy nhiên có thể ngay từ đầu sắp xếp các cạnh theo thứ tự tăng dần của trọng số. Để giải quyết vần đề thứ hai, ta quay lại chú ý rằng, khác với giải thuật Prim, tại mỗi bước của giải thuật Kruskal, tập các đỉnh và các cạnh đã được đưa vào T chưa là cây mà chỉ thỏa mã tính không chu trình. Như vậy tại mỗi bước T là một rừng, T = .  Bây giờ xét một cạnh e = (u,v) của G chưa nằm trong T có 3 khả năng xảy ra: 1. Cả u,v chưa thuộc T. Khi đó nếu bổ sung e vào T thì không có chu trình, nhưng chính cạnh e tạo thành một cây con mới. 2. Một đỉnh chẳng hạn u thuộc T, còn đỉnh kia v không thuộc T. Việc bổ sung cạnh e và đỉnh v vào T (vào cây con chứa đỉnh u) không tạo ra chu trình. 3. Cả u,v đều nằm trong T. Khi đó 1. Nếu u,v nằm trong cùng một cây con Tk ta không thể bổ sung canh e vào T. 2. Nếu u,v nằm trong hai cây con khác nhau thì có thể bổ sung cạnh e vào T (hai đỉnh u, v đã nằm trong T không cần bổ sung, sau khi bổ sung hai cây con sẽ hợp lại thành một cây. [sửa]Tổ chức dữ liệu  Giả sử G=(V,E)là đồ thị vô hướng n đỉnh, cho bằng danh sách kề Ajd(u), . Các đỉnh của G được đánh số từ 1 đến n, nghiã là V=V[1..n];Ta cũng kí hiệu Index(u) là chỉ số của đỉnh u trong mảng V. Hàm trọng số W(u,v) xác định trên các cạnh . Với mỗi cạnh e=(u,v) ký hiệu e.x u, e.y=v là hai đỉnh liên thuộc với cạnh e.  Các biến sau được đưa vào  Hàng đợi Q của các cạnh xếp theo thứ tự trọng số từ nhỏ đến lớn.  Với mỗi cây con, hàm PARENTS(u) xác định trên V, biểu diễn chỉ số của đỉnh cha của đỉnh u trong một cây. Riêng đỉnh gốc u của mỗi cây hàm PARENTS(u)lưu trữ số đỉnh trong cây với dấu âm. [sửa]Mã
Procedure Kruskal (G) T = V; Q =Sort(E) /* Tạo n cây, mỗi cây gồm một đỉnh*/ For each u of X do Parent(u):=-1; m = |E| For j:=1 to m do { u:=NodeStart(Q(j)); V:=NodeEnd(Q(j)) If Find_tree(u)Find_tree(V) then T:=T U Q[j]; Union(u,v;) Ghi chú:  Thủ tục Find_set(u) tìm đỉnh gốc của cây chứa đỉnh u. (xem cây biểu diễn tập hợp).  Thủ tục Union(u,v),ghép cây chứa v vào cây chứa u (xem cây biểu diễn tập hợp). ---------------------------------- 已已已已已收收收收收 QQ 收收 cruskal 源源源 C 源源 [ 收收收收收收 c 收收,cruskal,收收收 ] 收收收收:1 收收:19 收收收收:2009-03-08 13:37 收收满满满满 #include #include long u[200001],v[200001]; int d[200001],r[200001]; long i,j,m,n,ok=1,sum=0; bool ff=false; void dushu() {scanf("%d%d",&n,&m); for (i=1;i
while (d[j]>x) j--; if (i