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

Đề tài: Quy hoạch động bài toán tìm độ dài ngắn nhất

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

    Red face Quy hoạch động bài toán tìm độ dài ngắn nhất

    Đề bài: Trên trục hoành cho N điểm (1 <= N <=1000) được đánh số thứ tự từ 1 đến N. Điểm thứ i có hoành độ Ni (1<= Ni <= 10000). Hai điểm bất kỳ có thể nối với nhau bằng một đoạn thẳng.
    Yêu cầu: Tìm một cách nối các cặp điểm sao cho mỗi điểm được nối với ít nhất một điểm khác và tổng độ dài các đoạn thẳng dùng để nối là ngắn nhất. Đưa ra tổng độ dài ngắn nhất tìm được và số hiệu các cặp điểm để được nối với nhau.

    Mình hiểu bài toán nhưng chưa rõ cách xử lý quy hoạch động thế nào để tìm điểm có độ dài ngắn nhất nối với điểm đang xét. Mong các bạn giúp đỡ.





    Phương trình hồi quy của bài này tìm thế nào vậy?
    Attached Thumbnails Attached Thumbnails untitled.JPG  
    Đã được chỉnh sửa lần cuối bởi beautifulsoul84hung : 20-09-2011 lúc 09:42 AM. Lý do: Làm liền bài viết

  2. #2
    Ngày gia nhập
    05 2011
    Nơi ở
    TP HCM
    Bài viết
    27

    Để ý bài toán là những điểm cần nối với nhau đầu tiên phải thỏa ĐK : "Là những điểm liên tiếp nhau !". Dễ dàng thấy được điều này ! Do đó, 1 điểm chỉ có thể nối với 2 điểm kề nó mà thôi ! Gọi F[x] là giá trị nhỏ nhất khi x là điểm cuối !
    Ta có CT truy hồi cho bài này là :

    F[1]=0;
    F[2]=N[2]-N[1];
    F[3]=N[3]-N[1];

    F[i]=min( F[i-1] , F[i-2] ) + (N[i] - N[i-1])

    Với i: 4->N. Kết quả F[N] sẽ là giá trị nhỏ nhất cần tìm !

    Sau đó bạn có thể back tracking từ điểm thử N lại để tìm các cặp đỉnh theo quy tắc: nếu F[i]-N[i]=F[i-1] thì điểm i nối với i-1 và tiếp tục dò ở điểm (i-1) . Ngược lại nếu F[i]-N[i]=F[i-2] thì i nối với i-1, và dò tiếp ở điểm (i-2)

  3. #3
    Ngày gia nhập
    05 2010
    Nơi ở
    Nha Trang, Khánh Hòa
    Bài viết
    103

    Bài này nếu xét trên tập các điểm thì có vẻ phức tạp hơn so với khi xét trên tập các khoảng (số khoảng = số điểm -1). Nếu đc mình xin đề xuất công thức QHĐ tính theo khoảng (cơ sở của cách này chính là ĐK "các điểm đc nối phải liên tiếp với nhau" như bạn mini_bestboy đã nói)
    -Vì khoảng đầu tiên là bắt buộc phải chọn, do đó khởi tạo l[1,1]=x[2]-x[1], các khoảng còn lại là 1 giá trị cực lớn.
    -Nếu khoảng i được chọn thì khoảng i-1 có thể chọn hoặc không, ngược lại thì khoảng i-1 buộc phải được chọn, nên ta tính giá trị khoảng i theo 2 trường hợp:
    l[i,0]=l[i-1,1];//Trường hợp ko chọn
    l[i,1]=x[i+1]-x[i]+min(l[i-1,0],l[i-1,1]);//Trường hợp đc chọn
    Ngày mai ra sao cũng chẳng biết nữa
    Mà có ra sao thì cũng chả sao

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. Tim từ ngắn nhất và dài nhất trong chuổi lỗi has stopped working?
    Gửi bởi satthuprao trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 3
    Bài viết cuối: 27-05-2012, 11:51 AM
  3. Nhận miễn phí vé Lễ Hội Truyện Tranh – Phim Hoạt Hình Nhật Bản – MAF VIỆT NAM 2011 - 08/09/11
    Gửi bởi steven.thien 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-09-2011, 12:23 AM
  4. Trả lời: 0
    Bài viết cuối: 03-06-2011, 08:35 PM
  5. Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 AM

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