Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Thuật toán GTS2- Greedy - Tính chi phí hành trình tốt nhất. Nhờ các bạn chỉ giúp!!

  1. #1
    Ngày gia nhập
    06 2009
    Bài viết
    60

    Question Thuật toán GTS2- Greedy - Tính chi phí hành trình tốt nhất. Nhờ các bạn chỉ giúp!!

    -Chào các bạn! mình có một số thắc mắc về thuật toán GTS2. Cho 1 bài toán cụ thể như sau :

    Yêu cầu :Tính chi phí hành trình tốt nhất (tiết kiệm nhất): (Thuật toán GTS2- Greedy)
    -Cho ma trận có chi phí như sau :
    A B C D E F
    A ∞ 20 42 30 6 25
    B 12 ∞ 16 7 33 19
    C 23 5 ∞ 28 14 9
    D 12 9 24 ∞ 31 15
    E 14 7 21 15 ∞ 45
    F 36 15 16 5 205 ∞


    Với số thành phố xuất phát p = 4:
    tp 1 xuất phát từ A,
    tp2 từ B,
    tp 4 từ D
    tp 6 từ F
    tương ứng với 4 hàng v1=A, v2=B, v3=D, v4=F.

    GIẢI:

    Bước 1: cost = ∞; // Tổng trọng số của cung (chi phí đi đường)
    Best = {}; // lộ trình tiết kiệm nhất
    k = 0; // duyệt lần lượt các điểm xuất phát
    Bước 2: Do k=0 <p → Bước 3
    Bước 3: k = 1
    Gọi GTS1(1)
    T1 = A → E → B → D → F → C → A (lộ trình v1: bắt đầu từ tp 1) // Mình chưa hiểu sao có lộ trình như thế này :A → E → B → D → F → C → A.
    C1 = 6 + 7 + 7 + 15+ 16+ 23 = 74 (chi phí cho lộ trình v1) // cái này nữa.
    Bước 4: do C1< cost cost=74; best=T1;
    - Mong các bạn giải thích hộ mình. thanks!!

  2. #2
    Ngày gia nhập
    06 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    48

    bài toán người du lịch thì yêu cầu là đưa ra lộ trình tiết kiệm chi phí nhất, đi từ thành phố nào thì trở về đúng thành phố đấy, các thành phố khác đi qua đúng 1 lần mà.

    Vậy nên lộ trình: A → E → B → D → F → C → A có gì lạ đâu nhỉ?
    Java Code:
    1. System.out.println("We are electric !");

  3. #3
    Ngày gia nhập
    06 2009
    Bài viết
    60

    Trích dẫn Nguyên bản được gửi bởi tungcheng Xem bài viết
    bài toán người du lịch thì yêu cầu là đưa ra lộ trình tiết kiệm chi phí nhất, đi từ thành phố nào thì trở về đúng thành phố đấy, các thành phố khác đi qua đúng 1 lần mà.

    Vậy nên lộ trình: A → E → B → D → F → C → A có gì lạ đâu nhỉ?
    Bạn giải thích rõ giúp mình. Mình vẫn chưa hiểu

  4. #4
    Ngày gia nhập
    06 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    48

    thì yêu cầu đề bài là tìm đường đi khép kín mà, đi từ thành phố nào thì cuối cùng phải trở về đúng thành phố đấy
    Java Code:
    1. System.out.println("We are electric !");

  5. #5
    Ngày gia nhập
    06 2009
    Bài viết
    60

    uh, cái đó mình biết nhưng mình muốn hỏi cấch làm như thế nào để chọn từ A -> E , E -> B ... sao không phải là từ A - D hay E - F ... ý mình hỏi là cách làm cụ thể. tại mình chưa biết cách làm từ đâu thôi.
    Cảm ơn bạn đã quan tâm. mong bạn giúp.

Các đề tài tương tự

  1. Bài tập C++ bài toán tìm đừong đi ngắn nhất bằng thuật toán FLoyd , đoạn code C++ bị lỗi các bạn xem giúp mình
    Gửi bởi BornIsBAD trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 30-11-2012, 09:23 AM
  2. Đường đi ngắn nhất = giải thuật dijkstra trong Dev C,xem & sửa giúp em với..outtime
    Gửi bởi minhtoan991 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 01-04-2011, 06:12 PM
  3. Lập trình C Tìm dãy con nhỏ nhất có tổng bằng M | Thuật toán quay lui? Giải đáp giúp?
    Gửi bởi nh0cbilly trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 14
    Bài viết cuối: 19-12-2010, 03:36 PM
  4. Thuật toán Prim tìm cây khung nhỏ nhất. giúp mình sửa lỗi
    Gửi bởi KupoMigawa trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 23-10-2010, 02:54 PM
  5. lưu đồ giải thuật bài mã đi tuần thuật toán quay lui vét cạn. Giúp mình với?
    Gửi bởi katemat000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 05-01-2010, 10:53 PM

Tags của đề tài này

Quyền hạn của bạn

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