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

Đề tài: Dynamic programming

  1. #1
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Mặc định Dynamic programming

    Dr thấy cái tài liệu này cũng hay hay, và rất có ích. Mời các bạn tham khảo. Sẽ có phiên bản tiếng Việt, nhưng các bạn đọc trước phiên bản tiếng Anh này đã nhé!



    Dynamic programming is a common and useful technique in writing programs. In this context, "programming" does not refer to coding, it refers to planning in a tabular format. The very hallmark of dynamic programming is that it stores intermediate results during the computation in one or more separate arrays. However, in doing so, sometimes it can result in a faster algorithm. Usually, dynamic programming is used to solve optimization problems, such as to determine the shortest, fastest, most profitable, least cost, etc. way of doing a task.
    We shall consider the following problem. Suppose you are in a city with m horizontal roads and n vertical roads. The horizontal roads are numbered from 1 to m and the vertical roads are numbered from 1 to n as shown in the diagram below.

    All the horizontal roads intersect with the vertical roads at the junctions. Each junction is labelled (i, j), where i is the number of the horizontal road and j is the number of the vertical road.
    You are driving a car and is at the junction (1, 1), and your car is low in petrol, so you need to drive your car to the petrol station located at (m, n). As you have to meet an important client after filling up the petrol, so you need to reach the petrol station in the shortest possible time. However, the amount of petrol in your car is low, so you have to drive to the petrol using the shortest distance route. That is, you want to drive only rightward or downward, you do not want to waste petrol by driving leftward or upward. Also, the amount of time need to travel from a junction to any of its adjacent junctions is known, the amount of time varies from place to place because the amount of congestion at different places is not the same. You can assume that no time is needed to clear a junction.
    What is the fastest route you should take to drive to the petrol station, and how much time is required?
    We shall formalize the problem as follows. Let h(i, j) be the amount of time needed to drive from (i, j) to (i, j + 1), and v(i, j) be the amount of time needed to drive from (i, j) to (i + 1, j). Both h(i, j) and v(i, j) are known for all junctions (i, j). We shall answer the second question on the time required first.
    Using the dynamic programming approach, we will need to define another array t of size m by n, where t(i, j) is the minimum amount of time needed to drive from (i, j) to (m, n).
    Let us define the basis first:
    • t(m, n) = 0.
    • t(m, j) = t(m, j + 1) + h(m, j), for j = 1 to n - 1.
    • t(i, n) = t(i + 1, n) + v(i, n), for i = 1 to m - 1.
    The first is simple: if you are already at (m, n), you don't need to spend any more time travelling. The second base case arise because if you are already at horizontal road m, then you can only move right. Similarly, if you are already at vertical road n, then you can only drive downwards, so this is how the third base case is derived. With the above three conditions, we can fill up the last row and column of the array t backwards from t(m, n).
    Next, we define the recurrence:
    • t(i, j) = min{t(i, j + 1) + h(i, j), t(i + 1, j) + v(i, j)}.
    This recurrence relation should be self-explanatory: suppose we already computed t(i, j + 1) and t(i + 1, j), then we can find the fastest way to reach (m, n) from (i, j) using the recurrence relation. The recurrence is the one which allows us to fill up the remaining entries of the table t.
    Thus, we can derive an algorithm to compute the entries of the table t:
    Code:
    // Basis
    t(m, n) = 0
    for j = n - 1 downto 1
        t(m, j) = t(m, j + 1) + h(m, j)
    for i = m - 1 downto 1
        t(i, n) = t(i + 1, n) + v(i, n)
    
    // Recurrence
    for i = m - 1 downto 1
        for j = n - 1 downto 1
            if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j)
                t(i, j) = t(i, j + 1) + h(i, j)
            else
                t(i, j) = t(i + 1, j) + v(i, j)
    Notice that the correctness of this algorithm is from the fact that the array t is built backwards from bottom up as well as right to left. The algorithm terminates when we have computed t(1, 1), which is the minimum time required to drive from (1, 1) to (m, n).
    So we have solved half the problem. How do we find out the route which takes the shortest time?
    To do this, we will augment the above algorithm with another array r of size m by n, where r(i, j) is either the value RIGHT or DOWN, indicating driving rightward or downward will lead to the fastest route from (i, j) to (m, n). Again we define the basis and recurrence for r:
    • r(m, j) = RIGHT, for j = 1 to n - 1.
    • r(i, n) = DOWN, for i = 1 to m - 1.
    • r(i, j) = RIGHT, if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j), for j = 1 to n - 1 and i = 1 to m - 1.
    • r(i, j) = DOWN, if t(i, j + 1) + h(i, j) >= t(i + 1, j) + v(i, j), for j = 1 to n - 1 and i = 1 to m - 1.
    Note that r(m, n) is undefined, but that is not important. We will use the array r to determine the route from (1, 1) to (m, n).
    We modify the algorithm thus:
    Code:
    // Basis
    t(m, n) = 0
    for j = n - 1 downto 1
        t(m, j) = t(m, j + 1) + h(m, j)
        r(m, j) = RIGHT
    for i = m - 1 downto 1
        t(i, n) = t(i + 1, n) + v(i, n)
        r(i, n) = DOWN
    
    // Recurrence
    for i = m - 1 downto 1
        for j = n - 1 downto 1
            if t(i, j + 1) + h(i, j) < t(i + 1, j) + v(i, j)
                t(i, j) = t(i, j + 1) + h(i, j)
                r(i, j) = RIGHT
            else
                t(i, j) = t(i + 1, j) + v(i, j)
                r(i, j) = DOWN
    Finally, we can determine the shortest time route by backtracking using the array r:
    Code:
    // Backtracking
    i = 1
    j = 1
    while i < m and j < n
        if r(i, j) == RIGHT
            print "Drive rightward from (i, j) to (i, j + 1)"
            j = j + 1
        else  // r(i, j) == DOWN
            print "Drive downward from (i, j) to (i + 1, j)"
            i = i + 1
    Although the algorithm seems a little bit complicated, it actually achieves the best possible time complexity. Since both t and r are of size m by n, filling up both tables in the basis and recurrence steps take O(mn) time. For the backtracking step, we will move rightwards a total of n - 1 times and downwards a total of m - 1 times, so the time complexity is O(m + n). Hence, the total time complexity is still O(mn). Intuitively, this is the best possible time complexity since there are mn junctions in the problem, so the time complexity is actually linear with respect to the size of the problem.
    We shall conclude this miniature with another exercise in dynamic programming known as the subset sum problem.
    Formally, we define the subset sum problem as follows. You are given:
    • A set of n positive integers, S.
    • A positive number, m.
    Is there a subset of S whose elements sum up to m? For example, if S = {2, 3, 5, 7, 11} and m = 14, then the answer is yes because 2 + 5 + 7 = 14; and if S = {2, 3, 5, 7, 11} and m = 6, then the answer is no.
    Give an algorithm that uses dynamic programming to solve the subset sum problem, and analyze the time complexity of your algorithm in terms of n and m.

    Chúc mọi thành viên cộng đồng C Việt thành công và học tập tốt!
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

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

    Dynamic programming : divide and conquer with a table.
    Application to :
    - Computing combinations
    - Knapsack problem

    Counting Combinations

    To choose r things out of n, either :
    - Choose the first item. Then we must choose the remaining r-1 items from the other n-1 items. Or
    - Don't choose the first item. Then we must choose the r items from the other n-1 items.

    There fore :
    [C(r,n) = C(n-1, r-1) + C(n-1, r) /*C tổ hợp chập r của n phần tử*/

    Divide and Conquer
    This gives a simple divide and conquer algorithm for finding the number of combinations for n things chosen r at a time.
    Code:
    function choose ( n, r )
    if r = 0 or n = r then return (1) else
    return ( choose ( n-1, r-1) + choose ( n-1, r ) )
    Correctness proof : A simple induction on n.
    Analysics : Let T(n) be the worst case running time of choose (n, r ) over all possible values of r.

    Then
    T(n) :
    + c if n = 1
    + 2T(n-1) + d otherwise.
    for some constant c, d.
    Hence :
    T(n) = 2T(n-1) + d
    = 2(2T(n-2) + d ) + d
    = 4T(n-2) + 2d + d
    = 4(2T(n-3) + d ) + 2 + d
    = 8T(n-3) + 4d + 2d + d
    = 2^i T(n-i) + d.Sum (j=0;i-1)2^j
    = 2^(n-1) T(1) + d.Sum(j=0;n-2) 2^j
    = (c + d)2^(n-1) - d.
    Hence T(n) = O(2^n) --> sucks^^

    Example

    The problems is, the algorithm solves the same problems over and over again :


    Repeated Computation


    Pascal's triangle. Use a table T[0..n, 0...r]

    T[i,j] holds C(i,j)
    Code:
    function choose (n,r)
    for i:= 0 to n - r do T[i,0] = 1;
    for i:= 0 to r do T[i,j] = 1;
    for j:= 1 to r do 
         for i:= j+1 to n - r + j do 
               T[i,j] = T[i-1,j-1] + T[i-1,j]
    return ( T[n,r] )
    Initialization


    General Rule
    To fill in T[i,j] we need T[i-1,j-1] and T[i-1, j] to be already filled ịn


    Fill in the Table
    Fill in the columns from left to right. Fill each of the columns from top to bottom.



    Analysis
    How many table entries are filled in ?
    (n - r + 1 )(r+1) = n.r + n - r^2 + 1 <= n(r+1) + 1
    Each entries takes time O(1), so the total times required is O(n^2), and this much better than O(2^n).

    Dynamic Programming
    When divide and conquer generates a large number of identical subproblems, recursion is too expensive
    Instead, store solutions to subproblems in a table. This technique called dynamic programming.

    Dynamic Programming Techniques

    Identification :
    - Devise divide-and-conquer algorithm.
    - Analyze-running time is exponential.
    - Same subproblems solved many times.

    Construction :
    - Take part of divide-and-conquer algorithm that does the "conquer" part and replace recursive calls with table lookups.
    - Instead of returning a value, record it in a table.
    - Use base of divide-and-conquer to fill in start of table.
    - Devise "look-up template"
    - Devise for-loops that fill the table using "look-up Template"


    (to be continued )
    Đã được chỉnh sửa lần cuối bởi rox_rook : 25-11-2007 lúc 06:23 AM.

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

  1. Hỏi về Dynamic Help của VS 2008
    Gửi bởi trantuy trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 3
    Bài viết cuối: 09-03-2012, 01:35 AM
  2. ADO.NET Làm sao tạo report với dữ liệu cột dynamic ?
    Gửi bởi robinsonit trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 17-09-2011, 09:42 AM
  3. ADO.NET Chuyể Phần mềm QLNS sang Ngôn ngữ Dynamic Programming. Ai chuyển giúp mình!?
    Gửi bởi huynhanhton trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 03-04-2011, 11:41 PM
  4. Dynamic Programming với các bài toán 1 chiều
    Gửi bởi hienclubvn 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: 18-10-2010, 03:51 PM
  5. Hỏi về traceback trong dynamic programming
    Gửi bởi fomasudoi 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: 17-06-2009, 11:39 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