用动态规划实现文本对齐 [英] Implementing Text Justification with Dynamic Programming

问题描述

我想了解动态规划的概念，通过课程MIT OCW <一href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/#vid_playlist">here.对开放式课程的视频的解释是伟大的，但是我觉得我真的不明白，直到我实现了解释为code。虽然implementiing，我指的是一些笔记讲座笔记<一href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec20_orig.pdf">here,该说明特别3页。

I'm trying to understand the concept of Dynamic Programming, via the course on MIT OCW here. The explanation on OCW video is great and all, but I feel like I don't really understand it until I implemented the explanation into code. While implementiing, I refer to some notes from the lecture note here, particularly page 3 of the note.

现在的问题是，我不知道如何翻译一些数学符号为code的。下面是我实现的解决方案的某些部分（并认为这是正确的实现）：

The problem is, I have no idea how to translate some of the mathematical notation to code. Here's some part of the solution I've implemented (and think it's implemented right):

import math

paragraph = "Some long lorem ipsum text."
words = paragraph.split(" ")

# Count total length for all strings in a list of strings.
# This function will be used by the badness function below.
def total_length(str_arr):
    total = 0

    for string in str_arr:
        total = total + len(string)

    total = total + len(str_arr) # spaces
    return total

# Calculate the badness score for a word.
# str_arr is assumed be send as word[i:j] as in the notes
# we don't make i and j as argument since it will require
# global vars then.
def badness(str_arr, page_width):
    line_len = total_length(str_arr)
    if line_len > page_width:
        return float('nan') 
    else:
        return math.pow(page_width - line_len, 3)

现在的一部分，我不明白的是在讲义3点至5。我真的不明白，不知道从哪里开始实施的。到目前为止，我已经试过遍历单词列表，并计算线各据称年底的不良，像这样的：

Now the part I don't understand is on point 3 to 5 in the lecture notes. I literally don't understand and don't know where to start implementing those. So far, I've tried iterating the list of words, and counting the badness of each allegedly end of line, like this:

def justifier(str_arr, page_width):
    paragraph = str_arr
    par_len = len(paragraph)
    result = [] # stores each line as list of strings
    for i in range(0, par_len):
        if i == (par_len - 1):
            result.append(paragraph)
        else:
            dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)] 
            # Should I do a min(dag), get the index, and declares it as end of line?

不过，我不知道我怎么能继续功能，说实话，我不明白这行：

But then, I don't know how I can continue the function, and to be honest, I don't understand this line:

dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)] 

和我怎么会返回公正地对待为 INT （因为我已经决定要保存返回值结果，这是一个名单，我应该让另一个函数和递归从那里？如果有在所有任何递归是什么？

and how I'll return justifier as an int (since I already decided to store return value in result, which is a list. Should I make another function and recurse from there? Should there be any recursion at all?

能否请你告诉我下一步该怎么做，并解释这是动态规划？我真的不能看到的递归，而子问题是什么。

Could you please show me what to do next, and explain how this is dynamic programming? I really can't see where the recursion is, and what the subproblem is.

感谢了。

推荐答案

如果你无法理解动态规划本身这里的核心思想是我拿就可以了：

In case you have trouble understanding the core idea of dynamic programming itself here is my take on it:

动态规划实质上是牺牲的空间复杂度的的的的时间复杂度的（但是你用额外的空间通常的非常的一点比一次保存，使得动态规划完全值得的，如果正确实施）。您从每个递归调用，你去（例如，在一个数组或字典），这样就可以避免计算，第二次当你碰到的递归树的另一个分支相同的递归调用储存的值。

Dynamic programming is essentially sacrificing space complexity for time complexity (but the extra space you use is usually very little compared to the time you save, making dynamic programming totally worth it if implemented correctly). You store the values from each recursive call as you go (e.g. in an array or a dictionary) so you can avoid computing for the second time when you run into the same recursive call in another branch of the recursion tree.

和没有你做的没有的必须使用递归。下面是我的实现您正在使用的使用只是循环的问题。我接着AlexSilva联系非常紧密的TextAlignment.pdf。希望对您有所帮助。

And no you do not have to use recursion. Here is my implementation of the question you were working on using just loops. I followed the TextAlignment.pdf linked by AlexSilva very closely. Hopefully you find this helpful.

这篇关于用动态规划实现文本对齐的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！