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

Đề tài: Bài toán tìm đường đi nhắn nhất(bài nâng cao)

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

    Red face Bài toán tìm đường đi nhắn nhất(bài nâng cao)

    Cho tọa độ (trong hệ vuông góc) của N hòn đảo Đ1,Đ2, … ,Đn là (X1,Y1,), (X2,Y2), …, (Xn, Yn).
    Giả thiết mọi thiết bị chứa xăng của cano chỉ đủ chứa số xăng để đi quãng đường dài không quá M km cho trước.
    Trên mỗi đảo đầu có xăng dự trữ để cano có thể nạp đầy cho các thiết bị chứa xăng.
    a Tìm mọi đường đi có thể được của cano xuất phát từ đảo Đi(Xi,Yi) tới đảo Đj(Xj,Yj).
    b.Chỉ ra một đường đi của cano mà số lần ghé vào đảo để lấy xăng là ít nhất.

    Câu b là hay nhất đó???

  2. #2
    Ngày gia nhập
    10 2008
    Nơi ở
    sài gòn
    Bài viết
    422

    bài toán đồ thị này phải dùng quy hoạch động rồi,cậu đã học đến phần quy hoạch động của môn cấu trúc dữ liệu và giải thuật chưa

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

    Bạn đọc rồi nhưng khó hiểu quá> Cũng không biết làm thế nào?Còn phải đánh giá độ phức tạp thuật toán nữa?nếu bạn biết chỉ giúp mình nhé??

  4. #4
    Ngày gia nhập
    11 2008
    Nơi ở
    www.freelancer.com
    Bài viết
    75

    pa nào có tài liệu về qui hoạch động ko?? share cho mìh
    mìh chưa học đến phần đấy nhưg nghe thấy hay muốn tìm hiểu lém.
    Hiring someone to help someone else!

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

    theo mình :
    câu a: dùng giải thuật loang
    -Ta xây dựng 1 ma trận A[][] chứa khoảng cách giữa các đảo với A[i][j] là khoảng cách từ đảo i -> đảo j (= km) . A[i][j] = vô cùng nếu A[i][j] > M
    -Thực hiện giải thuật loang => mọi đường đi từ đảo i-> đảo j

    câu b:
    -dùng Giải thuật Dijtra (thay đổi 1 chút là thay vì tìm đường đi ngắn nhất = số bước đi ngắn nhất)
    Dương Nhật Tân
    dnhattan1910@yahoo.com

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Bài toán tìm đường đi nhắn nhất(bài nâng cao)

    theo mình :
    câu a: dùng giải thuật loang
    -Ta xây dựng 1 ma trận A[][] chứa khoảng cách giữa các đảo với A[i][j] là khoảng cách từ đảo i -> đảo j (= km) . A[i][j] = vô cùng nếu A[i][j] > M
    -Thực hiện giải thuật loang => mọi đường đi từ đảo i-> đảo j

    câu b:
    -dùng Giải thuật Dijtra (thay đổi 1 chút là thay vì tìm đường đi ngắn nhất = số bước đi ngắn nhất)
    Cả 2 câu, giải thuật của cậu Tân nói đều rất tốt, cậu thử làm trước xem sao . Lâu rồi không có làm mấy dạng này giờ chỉnh dám góp ý T_T, chứ cài đặt chắc cũng sai lên sai xuống T_T !

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

  1. Sửa máy tính, cài đặt windows, phần mềm tại nhà nhanh nhất, rẻ nhất, hiệu quả nhất …
    Gửi bởi hopluccc trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 08-07-2013, 02:07 PM
  2. Trả lời: 12
    Bài viết cuối: 25-10-2012, 02:48 AM
  3. Bài tập C++ NHập mảng một chiều gồm n phần tử kết thúc nhập khi nhập một chữ cái
    Gửi bởi thienthanoze trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 09-07-2012, 10:10 PM
  4. Bài tập C++ Viết phương trình nhập vào 1 chuỗi số.Hãy nhập vào 1 số.Đếm xem có bao nhiêu chữ số bạn vừa nhập
    Gửi bởi namtuocdn trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 16-10-2011, 10:39 AM
  5. Bài tập C++ Nhập mảng 1 chiều, nếu phần tử nhập trùng nhau thì bắt nhập lại
    Gửi bởi danielh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-07-2011, 03:35 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