Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    A. Phương pháp duyệt đồ thị theo chiều sâu:
    Mẫu thầy đưa ra.

    for all x Э V Đx(x) : = false;
    Proc. DS (v: Đỉnh xuất phát)
    1. Đx(v) : = true;
    2. For all x Э Danh sách kề (v);
              IF !Đx(x) DS (x)


    B. Phương pháp duyệt đồ thị theo chiều rộng:
    Mẫu thầy đưa ra.
    for all x Э V Đx(x) : = false;
    Proc. DR (v: Đỉnh xuất phát)
    Enqueue (v, HĐ)
    Đx(v) :=True;
    While (HĐ ≠ Ø )
                        a. u:=front (HĐ); Dequeue (HĐ);
                        for all x Э Danh sách kề (u)
                                            if !Đx(x) then
                                                                Đx(x) := True;
                                                                Enqueue (x, HĐ);


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Áp dụng phần trên để giải vào bài cụ thể.
    Đề thầy ra:
    - Đồ thị G liên thông, có n đỉnh được đánh số từ 1 đến n, cho bởi ma trận kề A = a(i,j) Viết thủ tục xây dựng cây khung của đồ thị n x n dựa trên phép duyệt ưu tiên chiều rộng.

    A) Mô tả cấu trúc câu khung:
    T = array (1.. n-1) of Edge;
    Edge = record
              d, c: tên đỉnh;
              end;
    B) Thuật toán
    E' = Ø; Q = Ø;
              1) FOR i = 1 TO n DO Đx(i) : = false;
              2)u là đỉnh xuất phát
              3) Đx(u) : = true;
              4) ENQUEUE(u, Q);
              5)WHILE Q ≠ Ø DO
                        a) x = TOP(Q); DEQUEUE(Q);
                        b) FOR j = 1 TO n DO
                                  IF A(x, j) = 1 & Đx(j) THEN
                                            i) E' = E' + (x, j)
                                            ii) Đx(j) = True
                                            iii) ENQUEUE(j, Q);



    Được sửa bởi Admin ngày Mon Jul 18, 2011 10:00 am; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    2. Trường hợp tiếp theo đề thầy ra:
    - Đồ thị G, có n đỉnh 1 -n được cho bởi ma trận A(i,j) Viết
    thủ tục dựa trên phép tì kiếm ưu tiên chiều sâu để liệt kê các đỉnh tìm
    kiếm của đồ thị.

    Ở đây G không nhắc đến liên thông, nên thủ tục chỉ cần đôi dòng, gọi thủ tục ở phần trên đã viết:
    For i := 1 to n
    IF (!Đx(i)           DS (i);


    3. Trường hợp tiếp theo đề thầy ra:
    Đếm số vùng liên thông của đồ thị G:

    d=0;
    For i = 1 to n
                        IF (!Đx(i))
                                            DS (i);
                                            d++
    Output d;

    4. Trường hợp tiếp theo đề thầy ra:
    Đồ thị G có n đỉnh liên thông (1-n) cho bởi danh sách kề, có cấu trúc:
    DS [1..n] of List
    List: ^ Kề;
              Kề = Record
              t: Tên đỉnh;
              next: List;
              end.

    Viết thủ tục liệt kê tên các đỉnh dựa trên phép tìm kiếm ưu tiên chiều rộng.

    For all x Э DsachKe (u) , P:= DS (u);
    Proc. DR (v: Đỉnh xuất phát)
    Enqueue (v, HĐ)
    Đx(v) :=True;
    While (HĐ ≠ Ø )
                        a. u:=front (HĐ); Dequeue (HĐ);
                        While (P ≠ Nil)
                                            a. x:= P^.t
                                            if !Đx(x) then
                                                                Đx(x) := True;
                                                                Enqueue (x, HĐ);
                        b. P:=P^.Next


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Đề thầy ra tiếp:
    Làm các bài tập trên thật thành thạo với danh sách liên kết và phương pháp duyệt theo chiều sâu. Bạn nào giải xong thì post lên chia sẻ nha. Đồng thời cần thêm bình giảng viên để mọi người hiểu chắc chắn nội dung này. Đây là nội dung chắc chắn có trong đề thi với nhóm điểm cao 3,5-5 điểm.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    LeVanDat


    Chuyên viên
    Chuyên viên
    Tôi nghĩ là đ/c Admin chưa áp dụng đúng thuật toán duyệt theo chiều rộng đối với đầu bài cho là mảng danh sách liên kết, thể hiện là danh sách kề.
    Vẫn áp dụng cấu trúc của duyệt theo chiều rộng. Nhưng nhớ rằng : input đầu bài là DS(1..n) cho nên thủ tục có thể viết như sau:

    for i := 1 to n do Đx(i) := false;
    for all P Э DS[1..n] do
    Proc. DR (P: danh sách xuất phát)
    x := P^.t;

    Enqueue (x, HĐ);
    if Đx(x) = false then
              a, Đx(x) :=True;

              b, Output(x);
    While (HĐ ≠ Ø ) do
              1. u:=front (HĐ); Dequeue (HĐ);
              2. While (P ≠ Nil) do
    a. x:= P^.t;
    b.if !Đx(x) then
              Đx(x) := True; Output(x);

              Enqueue (x, HĐ);

    c. P:=P^.Next;


    ================

    6 Duyệt bằng liên kết on Mon Jun 13, 2011 9:16 pm

    Admin


    Quản trị viên
    Quản trị viên
    Bài tập thầy yêu cầu:
    Cho đồ thị G (V, E) với /V/ = n, /E/ = m các đỉnh được đánh số 1..n các canh được cho bởi mảng.
    DS: array [1..m] of cạnh
    cạnh = record
              đ, c: tên đỉnh
              end;
    Viết thủ tục duyệt đồ thị theo chiều rộng, chiều sâu

    - Duyệt theo chiều sâu:

              + Thủ tục con
              proc DS (u: tên đỉnh);
                                  1. ĐX (u): = true;
                                  2. viet (u);
                                  for i: = 1 to n do
                                                      if ke(u, i) and ĐX (i) = false then DS (i)
              Function ke (x, y: tên đỉnh): boolean;
                                  1. tg: false; k:=1;
                                  2. while not tg and k ≤ m do
                                                      if DS[k].đ = x and DS[k].c = y then
                                                                                    tg = true
                                                      k:++
                                  3.ke: = tg or k ≤ m+1

              + Thủ tục chính
                        Proc. DFS (G);
                                                      1. for i := 1 to n do ĐX (i): = false
                                                      2. u: = đỉnh xuất phát
                                                      3. DS (u)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Admin đã viết:4. Trường hợp tiếp theo đề thầy ra:
    Đồ thị G có n đỉnh liên thông (1-n) cho bởi danh sách kề, có cấu trúc:
    DS [1..n] of List
    List: ^ Kề;
              Kề = Record
              t: Tên đỉnh;
              next: List;
              end.

    Viết thủ tục liệt kê tên các đỉnh dựa trên phép tìm kiếm ưu tiên chiều rộng.

    For all x Э DsachKe (u) , P:= DS (u);
    Proc. DR (v: Đỉnh xuất phát)
    Enqueue (v, HĐ)
    Đx(v) :=True;
    While (HĐ ≠ Ø )
                        a. u:=front (HĐ); Dequeue (HĐ);
                        While (P ≠ Nil)
                                            a. x:= P^.t
                                            if !Đx(x) then
                                                                Đx(x) := True;
                                                                Enqueue (x, HĐ);
                        b. P:=P^.Next



    - Theo tôi thì câu lệnh P:= DS (u); nên gán trong dòng lệnh (a). Vì khi lấy đỉnh u từ hàng đợi ra, ta mới xét các danh sách kề của u. Còn nếu gán P:= DS (u); ở đầu tiên thì chỉ duyệt được mỗi thằng v - là đỉnh đầu tiên và những đỉnh kề v thôi, còn những đỉnh không kề v thì không được đụng đến.

    - Tiếp nữa câu lệnh P:=P^.Next phải nằm trong vòng while.

    - Output?



    1.
              for x:=1 to n do Đx(x):=false;

    2.
              v:= đỉnh xuất phát; write (v);
              Đx(v) :=True;
              Enqueue (v, HĐ);

    3.
              While (HĐ ≠ Ø )
                        u:=front (HĐ); Dequeue (HĐ);
                        P:=DS(u);
                        While (P ≠ Nil)
                                  x:= P^.t;
                                  if !Đx(x) then
                                            Đx(x) := True;   write (x);                   
                                            Enqueue (x, HĐ);
                                  P:=P^.Next;


    ================
    [You must be registered and logged in to see this image.]

    haihonglyk6


    Chuyên viên
    Chuyên viên
    Hi. Bài 7 a.Phương viết đúng rồi
    [You must be registered and logged in to see this image.]


    ================
    Chúc Khách viếng thăm một ngày vui vẻ!

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Anh phương viết chuẩn rồi đấy.


    ================

    LeVanDat


    Chuyên viên
    Chuyên viên
    Bài toán trên duyệt theo chiều sâu:
    1. For i : = 1 to n do Đx(i) := False
    2. Procedure D_S(u: đỉnh xuất phát);
    Đx(u) := True;
    Write(u);
    P := DS[u];
    While (P # Nil) do
    x := P^.t;
    If !Đx(x) then D_S(x);
    P := P.next;

    Lê Văn Đạt


    ================

    hienha


    Chuyên viên
    Chuyên viên
    LeVanDat đã viết:Tôi nghĩ là đ/c Admin chưa áp dụng đúng thuật toán duyệt theo chiều rộng đối với đầu bài cho là mảng danh sách liên kết, thể hiện là danh sách kề.
    Vẫn áp dụng cấu trúc của duyệt theo chiều rộng. Nhưng nhớ rằng : input đầu bài là DS(1..n) cho nên thủ tục có thể viết như sau:

    for i := 1 to n do Đx(i) := false;
    for all P Э DS[1..n] do
    Proc. DR (P: danh sách xuất phát)
    x := P^.t;

    Enqueue (x, HĐ);
    if Đx(x) = false then
    a, Đx(x) :=True;

    b, Output(x);
    While (HĐ ≠ Ø ) do
    1. u:=front (HĐ); Dequeue (HĐ);
    2. While (P ≠ Nil) do
    a. x:= P^.t;
    b.if !Đx(x) then
    Đx(x) := True; Output(x);

    Enqueue (x, HĐ);

    c. P:=P^.Next;

    Theo tôi nghĩ đ/c Đạt đang có những nhầm lẫn rất cơ bản ở đây:
    1. Thuật toán DR luôn bắt đầu từ 1 đỉnh xuất phát chứ không phải danh sách xuất phát nên câu lệnh:
    Proc. DR (P: danh sách xuất phát) là không đúng.
    2. Đây là thuật toán loang: đầu tiên đánh dấu đỉnh xuất phát và cho vào hàng đợi. Lấy lần lượt các đỉnh ở đầu hàng đợi ra duyệt. Khi duyệt mỗi đỉnh, ta xét danh sách kề của nó, nếu các đỉnh trong danh sách kề chưa được xét thì đánh dấu đã xét và cho vào hàng đợi. Lấy cho đến khi hàng đợi rỗng. Quá trình này chỉ được làm 1 lần, không phải lặp đi lặp lại nên không viết:
    for all P Э DS[1..n] do
    Proc. DR (P: danh sách xuất phát)

    Đ/c Admin viết đúng rồi, chỉ thiếu các lệnh output đỉnh sau khi đánh dấu đã xét thôi.


    ================

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Free blog