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

Đề tài: Tìm đường đi ngắn thứ hai

  1. #1
    Ngày gia nhập
    11 2008
    Bài viết
    5

    Mặc định Tìm đường đi ngắn thứ hai

    Mọi người giúp mình giải thuật bài này với:

    Cho đồ thị vô hướng có trọng số không âm. Cần tìm một dãy đỉnh ( đường đi ) để đi từ A đến B với tổng độ dài ngắn thứ hai . ( các đỉnh lặp thoải mái ).

  2. #2
    Ngày gia nhập
    11 2008
    Bài viết
    10

    Mình đưa ra giải thuật thế này.
    Ban đầu bạn tìm đường đi ngắn nhất, tính độ dài đường đi này rồi chia nhị phân để tìm độ dài đường đi ngắn thứ 2, tìm đường đi từ đỉnh A tới B với tổng trọng số cho trước có lẽ không phải là khó phải không.
    Bài toán sẽ đơn giản hơn nếu trọng số là số nguyên hoặc có nhiều đường đi có tổng trọng số bằng đường đi ngắn nhất.

    Trước đây mình từng làm giải thuật là xóa từng cạnh của đường đi ngắn nhất và thực hiện tìm đường lại, nhưng thuật toán đó đã sai.

  3. #3
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Ý tưởng của mình là tìm tất cả đường đi từ s -> t, đường nào ngắn nhì thì lấy :P
    Nhưng sao lại có vụ lặp nhỉ ?
    Đã được chỉnh sửa lần cuối bởi 6220119 : 05-11-2008 lúc 05:57 PM.
    code ra gió bão

  4. #4
    Ngày gia nhập
    11 2008
    Bài viết
    2

    Theo mình để tìm đường đi ngắn nhất từ đình A đế đỉnh B thì bạn có thể từ đỉnh A bạnh chọn lấy đường đi ngắn nhất đến các đỉnh lân cận của A, rồi từ các đỉnh lân cận của A ta lại lặp lại quá trình trên cho đến khi nào tim đến đích thì thôi.tìm theo cách này cũng ko hẳn là tối ưu nhưng nó cũng khá là tốt.
    (*_* Italya *_*)

  5. #5
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    49

    Mấy bài đầu của môn Trí tuệ nhân tao đã đc học về cái này rồi đây mà.
    Ý tưởng, thuật toán, cài đặt đều có trong giáo trình Trí tuệ nhân tạo.
    Oa chu choa! Buồn ngủ wa! Oap oap!
    bb cả cộng đồng, em đi ngủ đây! Oap oap!

    Cảnh cáo bạn: tiger86love102 Không spam trong các bài viết.
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 06-11-2008 lúc 01:00 AM.

  6. #6
    Ngày gia nhập
    09 2008
    Bài viết
    5

    Mặc định Tìm đường đi ngắn thứ hai

    Trích dẫn Nguyên bản được gửi bởi 6220119 Xem bài viết
    Ý tưởng của mình là tìm tất cả đường đi từ s -> t, đường nào ngắn nhì thì lấy :P
    Nhưng sao lại có vụ lặp nhỉ ?
    Chắc là thế này.
    Tìm tất cả các đường đi từ S->T(không lặp)
    Rồi phải tính tất cả các đường đi S-...-U-V-U-V-...-T tương ứng với mỗi đường đi S-T ở trên ( Với điều kiện trọng số (u,v) là min trong số các cạnh trong đường đi đó).
    rồi so sánh với Đường đi ngắn nhất để tìm ngắn nhì.
    đấy là thuật toán của mình.
    mình thì chưa từng học qua cái môn Trí tuệ nhân tạo. bạn nào có sách thì post lên cho dễ hỉu đi.

  7. #7
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    49

    Bạn đọc qua tài liệu này thì chắc chắn giải quyết bài này đơn giản thôi!
    Đọc mấy bài đầu là OK rồi!
    Chúc cả nhà ngủ ngon!
    Attached Files Attached Files

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

  1. Lập trình C Hàm tạo số ngẫu nhiên | Cách nhập giá trị ngẫu nhiên cho ma trận?
    Gửi bởi chuong01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 15
    Bài viết cuối: 13-08-2012, 09:43 PM
  2. Trả lời: 0
    Bài viết cuối: 03-06-2011, 08:35 PM
  3. Bài tập C Tạo ngẫu nhiên mảng 2 chiều vuông 4X4 với các phần tử tạo ngẫu nhiên trong đoạn[0,50]
    Gửi bởi truongtrungviet trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 16-04-2011, 08:06 AM
  4. Ngắt trong C, Giúp chỉnh sửa code về ngắt
    Gửi bởi darkryte trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 17-11-2007, 07:21 PM
  5. Lập trình ngắt | Interupt | Ngắt 33h của Dos, Giúp mình xử lý!
    Gửi bởi thang@ 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: 15-10-2007, 10:34 PM

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