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

Đề tài: [Lý Thuyết quy hoạch động] Lỗi phụ thuộc tiền sử

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

    Mặc định [Lý Thuyết quy hoạch động] Lỗi phụ thuộc tiền sử

    Quy Hoạch Động (QHD) là 1 phương pháp rất mạnh mẽ trong Tin học. Nếu phân tích kĩ các bạn
    sẽ thấy những thuật toán nổi tiếng như Ford-Bellman, Dijkstra, hay Floyd đều có bản chất là
    QHD. Nhưng không phải bài toán nào cũng giải bằng QHD được, nếu quá áp đặt, cố sức giải nó
    như vậy bạn sẽ dễ dàng mắc phải 1 sai lầm gọi là Phụ thuộc tiền sử.

    Để tìm hiểu sai lầm này chúng ta nhắc lại về nguyên lí QHD do Bellman phát minh ra: "Một dãy là
    tối ưu thì các dãy con của nó cũng là tối ưu". Nghe có vẻ khó hiểu nhưng đại loại là ta có 1 cái
    bảng rồi lần lượt điền các số vào bảng đó, các số điền vào đầu tiên thường đơn giản, các số sau
    đó dựa vào các số trước mà điền, cho đến khi điền kín bảng. Kết quả bài toán là số mà ta điền
    cuối cùng. Như vậy nguyên lí "chia để trị" đã được đẩy tới cao độ ở đây.

    Khâu quan trọng nhất là làm thế nào điền được số sau dựa trên các số trước, hay nói cách
    khác là ta đang tìm 1 hệ thức truy hồi.

    Gọi f(i) là hàm QHD tại i, ta xây dựng công thức truy hồi tính f(i) dựa vào các f(j) với j = i - 1, i - 2,
    ... Công thức truy hồi này chỉ được phụ thuộc vào các f(j) cùng các đại lượng cố định của các j
    (cho trong đề bài) tuyệt đối không được phụ thuộc vào tiền sử, cách thức tạo nên f(j). Đây là
    chính là sai lầm mà tôi muốn nói đến!

    Để dễ hiểu chúng ta xét 1 ví dụ rất thú vị sau:
    Bài toán: ngày xửa ngày xưa, có 1 chàng Hoàng tử bị 1 mụ Phù thủy hóa phép biến thành
    1 con ếch, còn Công chúa thì bị mụ ta nhốt trong 1 tòa lâu đài nằm trên 1 hòn đảo giữa hồ. Bây
    giờ ếch đang đứng ở bờ hồ, trên đoạn thẳng từ chỗ đó đến tòa lâu đài có các lá sen nổi trên mặt
    nước ở những vị trí, khoảng cách khác nhau, ếch phải nhảy qua các lá sen để vào tòa lâu đài
    cứu Công chúa. Bước nhảy kề sau không được dài hơn bước nhảy kề trước A mét cho trước.
    Ếch có 1 túi rất nhiều muỗi thần, ăn K con muỗi, ếch có thể nhảy tối đa trong 1 bước là K mét.
    Mỗi bước nhảy (dù dài hay ngắn) đều tốn 1 giây. Cho trước thời gian giới hạn là T giây, hãy tính
    số muỗi ít nhất mà ếch cần ăn để có thể nhảy đến tòa lâu đài!

    Dữ liệu vào cho trong file ECHOP.INP có cấu trúc:
    Dòng đầu là 3 số nguyên N A T
    Dòng 2 là N số nguyên dương tăng dần thể hiện tọa độ các lá sen.
    Các số trên cùng 1 dòng cách nhau bởi ít nhất 1 dấu cách.
    Dữ liệu ra file ECHOP.OUT gồm 1 số duy nhất là số muỗi tối thiểu, nếu không có phương án giải
    cứu Công chúa in ra số -1

    Rồi, đọc xong là biết phải dùng QHD, đây là cách sai:
    Gọi d[t, i] là số muỗi ít nhất cần ăn khi phải nhảy đến lá sen thứ i và thời gian giới hạn là t. Để
    tính d[t, i] ta chỉ cần xét các d[j, t - 1] với j = i - 1, i - 2, ... kiểm tra xem khoảng cách từ lá sen j
    đến lá sen i là bao nhiêu (là P), xem tiền sử của d[j, t - 1] xem lá sen kề trước j là lá nào (lá thứ
    z), tính khoảng cách giữa lá sen z và j là Q, kiểm tra Q + A >= P được thỏa mãn rồi đặt x =
    max(d[t, j], P), trong các x như thế chọn ra cái nhỏ nhất và đó chính là d[t, i]

    Cách đúng: gọi d[t, i, j] là số muỗi ít nhất khi trong thời gian t, cần nhảy đến lá sen j nhưng lá kề
    trước j phải là i. Lúc này hệ thức truy hồi tương tự như trên nhưng không còn phụ thuộc tiền sử
    nữa.

    Bạn cũng dễ mắc sai lầm này khi đi tìm cách giải hoàn hảo cho các bài toán "bất trị", cho đến
    nay loài người vẫn chưa giải được như bài toán Người du lịch, bài toán Tìm đường đi dài nhất
    không lặp lại đỉnh trên đồ thị trọng số dương, bài toán Tập thống trị nhỏ nhất...
    {Sưu tầm từ congdongtinhoc.com}
    Đã được chỉnh sửa lần cuối bởi hailoc12 : 19-06-2007 lúc 10:41 AM.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Đúng là trong nguyên lý quy hoạch động em thấy khó hiểu nhất là chỗ "Một dãy là tối ưu thì các dãy con của nó cũng là tối ưu". "tối ưu" ở đây không biết phải hiểu là tối ưu một cách khách quan (nghĩa là từ bước i đến bước i+1 thì chọn lựa này là tốt nhất) hay một cách chủ quan ( phụ thuộc vào các giá trị đã chọn trước ). Trong một số ví dụ như tìm đường đi ngắn nhất thì việc chọn đường đi ngắn nhất từ i tới i+1 là khách quan, chỉ có một đường ngắn nhất duy nhất. Nhưng trong ví dụ mà anh huynguyen đưa ra nó lại phụ thuộc vào những bước thực hiện trước nữa. Đúng là quá khó hiểu

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Chậc sao mình lại chả thấy gì khó hiểu dù mình chả biết QHD là cái gì cả ? Hix chẳng lẽ mình tệ thế sao ?

    Để làm rõ tí nào ?

    Giả sử như thế này đi có 5 điểm A,B,C,D,E , từ 1 điểm có thể đi đến tất cả các điểm và chúng ta phải tìm đường đi ngắn nhất từ A -> E

    Đầu tiên theo cách hiểu của kid thì tìm Min (A->B,C,D,E) giả sử là B.
    Tiếp tục thì từ B ta có đường tiếp theo là C .
    Bây giờ ta mới lui lại và tính Min(A->C, A->B->C) rồi tiếp tục các bước lần lượt từ C.

    Không biết tớ hiểu vậy có đúng với ....

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

    bài toán người đi du lịch cũng thuộc quy hoạc động đúng k các bạn ?

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

    mấy bạn ui cho mình hỏi phụ thuộc tiền sử là sao???
    Giải thik rõ cho mìh 1 xíu.thx

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

  1. Lý thuyết đồ hoạ | Lập trình đồ họa với openGL
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 120
    Bài viết cuối: 01-09-2012, 09:21 AM
  2. Cách thức hoạt động của thuộc tính mã hóa password trong C#
    Gửi bởi QuangLinh trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 6
    Bài viết cuối: 05-07-2012, 09:36 AM
  3. Algorithm Bài Toán Quản Lý Thuốc. Làm sao kiểm tra thuốc còn hay hết hoặc đã hết hạn?
    Gửi bởi lthict trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 9
    Bài viết cuối: 31-03-2012, 03:51 PM
  4. Lý thuyết quy hoạch động cơ sở
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 11-05-2011, 09:37 AM
  5. Làm sao đặt thuộc tính chỉ đọc cho file hoặc thư mục
    Gửi bởi AlexF trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 8
    Bài viết cuối: 23-04-2010, 03:14 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