NHẬP TỪ KHÓA BẠN QUAN TÂM VÀO KHUNG BÊN DƯỚI
LIKE ỦNG HỘ GOCCAY.VN NHA CÁC BẠN ^_^
TRUYỆN XEM NHIỀU NHẤT
Đấu Phá Thương Khung
Đấu La Đại Lục
Cực Phẩm Gia Đinh
Tân Tác Long Hổ Môn
Phong Thần Ký III
Tuyệt Thế Vô Song
Thời Đại X Long
Thiên Địa Long Hồn
Chu Tước Ký
Bàn Long
Thôn Phệ Tinh Không
Chín Chín Tám Mốt
Mãng Hoang Ký
Hắc Khuyển
+ Trả Lời Ðề Tài
kết quả từ 1 tới 3 trên 3

Ðề tài: Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]

  1. #1
    Tham gia ngày
    Jun 2012
    Đến từ
    CDTH10B
    Bài gởi
    4
    Thanks
    5
    Thanked 18 Times in 3 Posts

    Lightbulb Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]

    Ý tưởng cài đặt thuật toán BFS:
    - Nguyên liệu ^^! :
    + Mảng int arrDiemLanCan với độ dài bằng số đỉnh (vì trường hợp cao nhất là tất cả các đỉnh đều được xét cùng lúc – chiều cao của cây = 1)
    + Biến int k, nhiệm vụ là đánh dấu tiến trình xét các phần tử, khi k=-1 là lúc arrDiemLanCan rỗng.
    + Mảng int arrDinh là nơi chứa các đỉnh có thể liên kết với nhau để đưa ra lời giải với đỉnh Start và Goal.
    + Cuối cùng là mảng 2 chiều matranLienKet => Ma trận.
    - Thực hiện:
    B1: Gán k = 0
    Phần tử đầu mảng sẽ là Start (arrDiemLanCan[0] = Start). Như hình:
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    B2: Xét arrDiemLanCan[0] là Goal hoặc k = -1 (arrDiemLanCan rỗng) thì chạy B7. Ngược lại thì chạy B3.
    B3: Tạo vòng lặp xét tất cả các cột của dòng arrDiemLanCan[0] trong ma trận, col là cột trong ma trận và cũng là điểm lân cận nếu arrLienKet[arrDiemLanCan[0], col] = 1 => có liên kết thì xét arrDinh[col] có bằng -1 hay ko. Nếu bằng thì chạy B4. Ngược lại Không có liên kết hoặc khác -1, thì chạy B6. (Tránh trường hợp bị lặp liên tục trong liên kết 2 chiều)
    B4: Xét điểm col có nằm trong arrDiemLanCan, đã xét hay chưa. Nếu chưa chạy B5. Còn đã tồn tại thì chạy B6.
    B5: Gán cho phần tử kế tiếp arrDiemLanCan là col (arrDiemLanCan[++k]=col). Gán cho phần tử thứ col trong mảng arrDinh[col] là điểm arrDiemLanCan[0].
    B6: Đẩy mảng arrDiemLanCan từ phải qua trái 1 phần tử. Gán arrDiemLanCan[k] = -1 và giảm k--. Chạy B2.
    B7: Xét arrDinh[Dich] có khác -1 không và đường đi có dừng chân tại -2 hay không. Nếu khác thì quay lui, nếu không thì xuất "Không tìm được lời giải".

    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    - Chạy từng bước: (chữ trước hình giải thích sau)
    k=0; arrDiemLanCan[0] = Start;
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k=1;
    arrDiemLanCan[1] = 1;
    arrDinh[1] = arrDiemLanCan[0];
    k=2;
    arrDiemLanCan[2] = 2;
    arrDinh[2] = arrDiemLanCan[0];
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k--; (k=1)
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    //không có điểm lân cận
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k--; (k=0)
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k=1;
    arrDiemLanCan[1] = 3;
    arrDinh[3] = arrDiemLanCan[0];
    k=2;
    arrDiemLanCan[2] = 4;
    arrDinh[4] = arrDiemLanCan[0];
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k--; (k=1)
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    //không có điểm lân cận
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    k--; (k=0)
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    arrDiemLanCan[0] = Goal;
    Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]

    + arrDinh lúc này: Hướng dẫn các thuật toán BFS, LCBFS, DFS [Code + Ý tưởng cài đặt]
    + Quay lui : 4 <- 2 <- 0.
    + Kết quả: 0 -> 2 -> 4.
    - Code:
    Code:
                        //Xét các điểm để tìm đường đi
                        int k = 0; //Đánh dấu tiến trình xét các phần tử
                        arrDiemLanCan[0] = Dau;
                        while (true)
                        {
                            if (arrDiemLanCan[0] == -1 || k == -1 || arrDiemLanCan[0] == Dich)
                            {
                                break;
                            }
                            for (int col = 0; col < SoDinh; col++)
                            {
                                if (matranLienKet[arrDiemLanCan[0], col] == 1) //Trường hợp có điểm lân cận
                                {
                                    if (arrDinh[col] == -1)
                                    {
                                        int flag = 0;
                                        for (int i = 0; i <= k; i++)
                                        {
                                            if (col == arrDiemLanCan[i]) //Xét điểm lân cận có thuộc vùng đã xét chưa
                                            {
                                                flag = 1;
                                            }
                                        }
                                        if (flag == 0)
                                         {   //Gán cho điểm kế tiếp là điểm lân cận => xét lần lượt các điểm  lân cận của nhiều nhánh 
                                            k++;
                                            arrDiemLanCan[k] = col;
                                            arrDinh[col] = arrDiemLanCan[0];
                                        }
                                    }
                                }
                            }
                            for (int i = 0; i < k; i++)
                            {
                                arrDiemLanCan[i] = arrDiemLanCan[i + 1];
                            }
                            arrDiemLanCan[k] = -1;
                            k--;
                        }
    Cài đặt LCBFS:
    + Việc có thêm chi phí cho đường đi LCBFS thì cũng dựa vào ý tưởng này nhưng thêm mảng arrChiPhi với chiều dài là số lượng đỉnh (vì chi phí thấp hơn sẽ triệt tiêu những cái còn lại, nên phần tử mảng luôn < số lượng đỉnh)
    Code:
                        //Xét các điểm để tìm đường đi
                        int k = 0; //Đánh dấu tiến trình xét các phần tử
                        arrDiemLanCan[0] = Dau;
                        arrChiPhi[Dau] = 0;
                        while (true)
                        {
                            if (arrDiemLanCan[0] == -1 || k == -1 || arrDiemLanCan[0] == Dich)
                            {
                                break;
                            }
                            //Xét điểm lân cận bằng cách xét cột của từng dòng trong ma trận
                            for (int col = 0; col < SoDinh; col++)
                            {
    
                                if (matranLienKet[arrDiemLanCan[0], col] != 0) //Trường hợp có điểm lân cận
                                {
                                    //Trường hợp chưa có đỉnh nào tới đỉnh col
                                    if (arrDinh[col] == -1)
                                    {
                                        k++;
                                        arrDiemLanCan[k] = col;
                                        arrDinh[col] = arrDiemLanCan[0];
                                        arrChiPhi[col] = arrLienKet[arrDiemLanCan[0], col] + arrChiPhi[arrDiemLanCan[0]];
                                    }
                                    else
                                    {
                                         //Tách điều kiện ra vì trường hợp chi phí chưa có thì sẽ là số ngẫu  nhiên => không chính xác
                                        //Trường hợp đã có đỉnh tới đỉnh col nhưng chi phí cao hơn
                                        if (arrChiPhi[col] > matranLienKet[arrDiemLanCan[0], col] + arrChiPhi[arrDiemLanCan[0]])
                                        {
                                            k++;
                                            arrDiemLanCan[k] = col;
                                            arrDinh[col] = arrDiemLanCan[0];
                                            arrChiPhi[col] = matranLienKet[arrDiemLanCan[0], col] + arrChiPhi[arrDiemLanCan[0]];
                                        }
                                    }
                                }
                            }
                            for (int i = 0; i < k; i++)
                            {
                                arrDiemLanCan[i] = arrDiemLanCan[i + 1];
                            }
                            arrDiemLanCan[k] = -1;
                            k--;
                        }
    Cài đặt DFS:
    Gần giống với BFS, chỉ khác ở Bước 5. Vì nguyên lý là xét từng phần tử trong từng nhánh, nên phải đảm bảo là xét hết phần tử trong nhánh này rồi mới xét nhánh khác.

    B5: Bắt đầu từ intSoDinhTrongNhanh++, dời các phần tử sau nó từ trái qua phải 1 phần tử, gán cho phần tử arrDiemLanCan[intSoDinhTrongNhanh] là col. Gán cho phần tử thứ col trong mảng arrDinh[col] là điểm arrDiemLanCan[0].
    Code:
                        //Xét các điểm để tìm đường đi
                        int k = 0; //Đánh dấu tiến trình xét các phần tử
                        arrDiemLanCan[0] = Dau;
                        while (true)
                        {
                            if (arrDiemLanCan[0] == -1 || k == -1 || arrDiemLanCan[0] == Dich)
                            {
                                break;
                            }
                            int intSoDinhTrongNhanh = 0;
                            for (int col = 0; col < SoDinh; col++)
                            {
                                if (matranLienKet[arrDiemLanCan[0], col] == 1) //Trường hợp có điểm lân cận
                                {
                                    if (arrDinh[col] == -1)
                                    {
                                        int flag = 0;
                                        for (int i = 0; i <= k; i++)
                                        {
                                            if (col == arrDiemLanCan[i]) //Xét điểm lân cận có thuộc vùng đã xét chưa
                                            {
                                                flag = 1;
                                            }
                                        }
                                        if (flag == 0)
                                         {   //Hoán vị điểm lân cận của nhánh đầu với nhánh sau => xét hết  điểm lân cận nhánh đầu mới xét nhánh sau
                                            intSoDinhTrongNhanh++; //Xác định thứ tự của các đỉnh trong nhánh
                                            k++;
                                            if (k > 0)
                                            {
                                                for (int i = k; i > intSoDinhTrongNhanh; i--)
                                                {
                                                    arrDiemLanCan[i] = arrDiemLanCan[i - 1];
                                                }
                                                arrDiemLanCan[intSoDinhTrongNhanh] = col;
                                            }
                                             else //Trường hợp k=0, chỉ còn 1 nhánh để xét nên không còn nhánh để  hoán vị với điểm lân cận
                                            {
                                                arrDiemLanCan[k] = col;
                                            }
    
                                            arrDinh[col] = arrDiemLanCan[0];
                                        }
                                    }
                                }
                            }
                            for (int i = 0; i < k; i++)
                            {
                                arrDiemLanCan[i] = arrDiemLanCan[i + 1];
                            }
                            arrDiemLanCan[k] = -1;
                            k--;
                        }

    Bài làm của mình. Viết bằng chương trình Microsoft Visual Studio 2005, ngôn ngữ C# giao diện Form:

    http://www.mediafire.com/?sp254mgilm72clq

    Hy vọng bài viết này giúp ích cho bạn!

    View more latest threads same category:

    thay đổi nội dung bởi: AnhTuan; 08-31-2012 lúc 06:11 PM Lý do: nhầm giữa đặt tên ma trận và mảng (arrLienKet => matranLienKet)
    CĐKT Cao Thắng - CĐTH10B - Anh Tuấn - 306101223

  2. The Following 9 Users Say Thank You to AnhTuan For This Useful Post:

    brokensmile2103 (06-24-2012), gorokolo (06-24-2012), graphic (06-29-2012), hocacad (06-27-2012), hocxongdiem113 (06-25-2012), naufantasy (06-28-2012), nhoc_ac (06-24-2012), phuongthao_cdth10b (06-24-2012), s2susancaos2 (06-27-2012)

  3. Circuit advertisement
    Tham gia ngày
    Always
    Đến từ
    Advertising world
    Bài gởi
    Many
  4. #2
    Tham gia ngày
    Jun 2012
    Bài gởi
    1
    Thanks
    0
    Thanked 1 Time in 1 Post

    ngon ngon tk ku

    ngon ngon tk ku

  5. The Following User Says Thank You to cumacuong113 For This Useful Post:

    AnhTuan (08-31-2012)

  6. #3
    Tham gia ngày
    Jun 2012
    Bài gởi
    1
    Thanks
    2
    Thanked 1 Time in 1 Post
    thanks you !
    .............................................30610 1118

  7. The Following User Says Thank You to naufantasy For This Useful Post:

    AnhTuan (08-31-2012)

+ Trả Lời Ðề Tài

Tags for this Thread

Quuyền Hạn Của Bạn

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể chỉnh sửa bài viết