zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Thuật toán tìm kiếm theo chiều rộng

Chia sẻ: Đinh Thị Hòa | Ngày: | Loại File: DOC | Số trang:8

Báo xấu

804
lượt xem 153
download

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

Toán rời rạc - Lý thuyết đồ thị: Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị

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 theo chiều rộng

Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG Input: Đơn đồ thị vô hướng G = (V,E) gồm n đỉnh, m cạnh. Các đỉnh được đánh số từ 1 đến n. Đỉnh xuất phát là S, điểm kết thúc là F. Output: - Số thành phần liên thông của đồ thị. - Tìm đường đi từ 1 đỉnh đến các đỉnh còn lại. - Chỉ ra các đỉnh cùng thuộc một thành phần liên thông Tư tưởng: - Lưu trữ thông tin của đồ thị vô hướng G vào file DOTHI.INF trong đó + Dòng 1 ghi số đỉnh n và số cạnh m của đồ thị cách nhau một dấu cách. + m dòng tiếp theo mỗi dòng có 2 số nguyên dương u,v cách nhau một dấu cách, thể hiện có cạnh nối giữa đỉnh u và đỉnh v trong đồ thị. Ví dụ: Với đồ thị vô hướng sau: Ta có file DOTHI.INF thể hiện dưới bảng sau: - Cơ sở của thuật toán tìm kiếm theo chiều rộng là lập lịch duyệt các đỉnh.Việc thăm một đỉnh sẽ lên lịch duyệt tất cả các đỉnh kề của nó Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị sao cho thứ tự duyệt là ưu tiên chiều rộng ( nghĩa là đỉnh nào gần S hơn sẽ được duyệt trước). - Ví dụ: Bắt đầu thăm đỉnh S.. Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh (x1,x2,…,xp) kề với S ( đó là những đỉnh gần S nhất). Khi thăm những đỉnh x1 sẽ lại phát sinh yêu cầu duyệt những đỉnh (u1,u2,…,uq) kề với x1. Nhưng rõ ràng là các đỉnh này xa S hơn những đỉnh x khác nên chúng chỉ được duyệt khi tất cả những đỉnh x đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi thăm x1 là (x2,x3,…,xp,u1,u2,..,uq,…) Thuật toán: Bước 1: Khởi tạo: - Các đỉnh đều ở trạng thái chưa đánh dấu, ngoại trừ đỉnh xuất phát S là đã đánh dấu. - Một hàng đợi Q (tổ chức dưới dạng hàng đợi Queue), ban đầu chỉ có một phần tử là S. Hàng đợi dùng để chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng. Bước 2: Lặp lại các bước sau cho đến khi hàng đợi Q rỗng: - Lấy u ra khỏi hàng đợi, thông báo thăm u ( Bắt đầu duyệt đỉnh u) - Xét tất cả các đỉnh v kề với u mà chưa được đánh dấu, với mỗi đỉnh v đó: 1. Đánh dấu v 2. Ghi nhận đường đi từ v đến u 3. Đẩy v vào hàng đợi (v sẽ chờ được duyệt tại những bước sau) Bước 3: Truy ngược lại đường đi Thể hiện cách lưu trữ với hàng đợi Q: Lưu trữ và biểu diễn hàng đợi Queue bằng một mảng 1 chiều, số phần tử của hàng đợi là không quá n (số đỉnh của đồ thị). Giả sử ta dùng một mảng Q, một số nguyên last lưu trữ chỉ số cuối hàng đợi và một số nguyên first lưu trữ chỉ số đầu hàng đợi. Các thao tác trên hàng đợi: Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị - Đưa một giá trị V vào hàng đợi tương đương với việc thêm một phần tử vào cuối mảng Q. Lúc này chỉ số đầu hàng đợi giữ nguyên, chỉ số cuối hàng đợi tăng 1: - Lấy một phần tử khỏi hàng đợi tương đương với việc lấy phần tử thứ first của mảng Q, phần tử kế tiếp trở thành đầu hàng đợi. chỉ số đầu hàng đợi tăng lên 1, chỉ số cuối hàng đợi vẫn giữ nguyên. Xây dựng chương trình con ( các thủ tục và hàm cần thiết) 1. Khai báo • a: array[1..max,1..max] of boolean; {Mảng cho thông tin về cạnh của đồ thị, có cạnh giữa hai đỉnh phần tử mảng tương ứng mang giá trị True, không có cạnh giữa 2 đỉnh phần tử mảng tương ứng mang giá trị True, hay nói cách khác a là ma trận kề của đồ thị} • tham: array[1..max] of boolean; { Mảng cho biết đã thăm đỉnh chưa = True nếu đỉnh chưa được thăm} • danhdau: array[1..max] of integer; {Lưu vết đường đi từ một đỉnh} • q: array[1..max] of integer; {Queue Q lưu trữ thông tin của đồ thị} • n,st,fi,first,last: integer; {n: số đỉnh của đồ thị; st: điểm xuất phá; fi: điểm kiết thúc; First: chỉ số đầu hàng đợi; Last: chỉ số cuối hàng đợi} 2. Nhập thông tin cho hàng đợi và chương trình: thông tin của hàng đợi Q được lưu trữ trên file DOTHI.INF Procedure nhap; var f:text; { f là biến dùng lưu trữ thông tin đồ thị từ file text DOTHI.INF} i,u,v,m: integer; Begin fillchar(a,sizeof(a),false); {Khởi tạo ma trận kề toàn False: đồ thị chưa có cạnh nào} assign(f,'E:\DOTHI.INF'); reset(f); readln(f,n,m); {đọc dòng đầu tiên ra số đỉnh n và số cạnh m} for i:=1 to m do begin readln(f,u,v); {đọc các dòng tiếp theo ra 2 giá trị u và v} Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị a[u,v]:=true; {các phần tử tương ứng trong ma trận kề bằng=true} a[v,u]:=true; {đồ thị vô hướng} end; close(f); write('Diem bat dau:');readln(st); {Điểm xuất phát} write('Diem ket thuc:'); Readln(fi); {Điểm kết thúc} end; 3. Khởi tạo các giá trị của mảng thăm và hàng đợi Q procedure khoitao; begin fillchar(tham,n,true); {ban đầu các phần tử của mảng thăm có giá trị True} tham[st]:=false; q[1]:=st; { Phần tử đầu tiên của hàng đợi Q là điểm bắt đầu} last:=1; { Chỉ số cuối của hàng đợi ban đầu bằng 1} first:=1; { Chỉ số đầu của hàng đợi ban đầu bằng 1} end; 4. Đẩy một phần tử vào Queue procedure push(v:integer); begin inc(last); q[last]:=v; end; 5. Lấy một phần tử ra khỏi hàng đợi function pop:integer; begin pop:=q[first]; inc(first); end; 6. Hiển thị kết quả đường đi từ 1 đỉnh đến 1 đỉnh. procedure ketqua; begin writeln; if tham[fi] then writeln('Khong co duong di tu ',st,' den ',fi) else begin while fist do begin write(fi,'
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị fi:=danhdau[fi]; end; writeln(st); end; end; 7. Đếm số thành phần liên thông function demtplt:integer; var v,d: integer; begin d:=0; for v:=1 to n do if tham[v] and a[ then begin d:=d+1; end; demtplt:=d; end; CHƯƠNG TRÌNH HOÀN CHỈNH uses crt; const max=100; var a: array[1..max,1..max] of boolean; tham: array[1..max] of boolean; danhdau: array[1..max] of integer; q: array[1..max] of integer; n,st,fi,first,last: integer; procedure nhap; var f:text; i,u,v,m,j: integer; begin fillchar(a,sizeof(a),false); assign(f,'E:\DOTHI.INF'); reset(f); readln(f,n,m); for i:=1 to m do begin readln(f,u,v); a[u,v]:=true; Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị a[v,u]:=true; end; close(f); write('Diem bat dau:');readln(st); write('Diem ket thuc:'); Readln(fi); end; procedure khoitao; begin fillchar(tham,n,true); tham[st]:=false; q[1]:=st; last:=1; first:=1; end; procedure push(v:integer); begin inc(last); q[last]:=v; end; function pop:integer; begin pop:=q[first]; inc(first); end; procedure duyetrong; var u,v:integer; begin write('Thanh phan thuoc lien thong:'); repeat u:=pop; write(u:5); for v:=1 to n do if tham[v] and a[u,v] then begin push(v); tham[v]:=false; danhdau[v]:=u; end; until first>last; Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị end; procedure ketqua; begin writeln; if tham[fi] then writeln('Khong co duong di tu ',st,' den ',fi) else begin write('Duong di la:'); while fist do begin write(fi,'
Toán rời rạc - Lý thuyết đồ thị Tìm kiếm và ứng dụng của tìm kiếm trên đồ thị Áp dụng với ví dụ : Được lưu trữ trong tệp: Màn hình chạy: Nhóm 2 - Tìm kiếm theo chiều rộng dùng hàng đợi Lớp ĐL Tin 3B – Trường Đại học SPKT Nam Định

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.