我有一个“块状”的项目序列,我想将其分成一定数量的大致相等大小的包裹,同时保持包裹内容(以及包裹本身)的排序顺序。由于在阳光下没有什么新鲜事,我猜我只是缺少这个问题的正确名称。我的最终目标是算法的 python 实现,但我至少需要朝着正确的方向推进。
问题是我有一个文本,分成不同长度的部分,我想把它分成一系列公平的阅读。当然,读数的顺序必须保持不变。
对于某些细节,我有 2,519 个部分。最长1876字,最短7字。平均长度为 305 个单词,中位长度为 242。
我不确定它是否能完全解决您的程序,但在 MIT OCW 课程Introduction to Algorithms中,他们使用动态编程来解决行的最佳分割问题,以便沿着页面很好地填写文本(' word-wrapping ') ,类似于 Latex 所做的。请参阅此视频的第 17 分钟。
给定一些函数,该算法将提供有保证的最佳分割,该函数根据线分割的丑陋程度来定义惩罚。在讲座中,他们将这个丑陋函数定义为(pagewidth - actual_linewidth)^3
,但您可以定义自己的函数。该算法或多或少地尝试了所有不同的分裂可能性(以一种聪明的方式)并选择最佳的一个。DP的主要要求是可以将问题划分为子程序,例如,n
可以在之前的单词解的基础上描述n-1, n-2, ...
单词的解。这些类型的 DP 算法通常是O(n^2)
或O(n^3)
,所以绝对不是 NP 难的。
如果您对基本算法感兴趣,我强烈建议您观看整个讲座系列,老师们很棒。
这应该会给你一个好的结果,一个“贪婪”的策略:
avg = total_words / num_readings
。要做得更好,您需要一些启发式方法。如果你把输入搞砸了,比如一个很大的部分和许多较小的部分,说
100 100 100 100 100 100 40000 100 100 100 100
你想把它分成 5 个部分,你希望你的输出是什么样的?我的算法会给你这个:
100 100 100 100 100 100
40000
100 100 100 100
0
0
您可以轻松地对其进行调整以强制每个部分至少使用一个单词:
100 100 100 100 100 100
40000
100 100
100
100
但这可能不像这个选项那么“好”:
100 100 100
100 100 100
40000
100 100
100 100
是的,我建议查看Bas建议的讲座。你必须稍微调整一下启发式。例如,对你来说,一个部分有更多的单词是可以的,而对于换行来说,如果你超过了,那就太糟糕了。
好的,这激起了我的好奇心,所以我编写了一个动态编程算法,其中包含abs(num_words - avg_words)**3
. 它应该适用于任何启发式方法。以下是示例输出:
>>> section_words = [100, 100, 100, 100, 100, 100, 40000, 100, 100, 100, 100]
>>> def heuristic(num_words, avg):
... return abs(num_words - avg)**3
...
>>> print_solution(solve(section_words, heuristic, 3))
Total=41000, 3 readings, avg=13666.67
Reading #1 ( 600 words): [100, 100, 100, 100, 100, 100]
Reading #2 (40000 words): [40000]
Reading #3 ( 400 words): [100, 100, 100, 100]
>>> print_solution(solve(section_words, heuristic, 5))
Total=41000, 5 readings, avg=8200.00
Reading #1 ( 300 words): [100, 100, 100]
Reading #2 ( 300 words): [100, 100, 100]
Reading #3 (40000 words): [40000]
Reading #4 ( 200 words): [100, 100]
Reading #5 ( 200 words): [100, 100]
>>> section_words = [7, 300, 242, 100, 115, 49, 563,
1000, 400, 9, 14, 300, 200, 400,
500, 200, 10, 19, 1876, 100, 200,
15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]
>>> print_solution(solve(section_words, heuristic, 10))
Total=9098, 10 readings, avg=909.80
Reading #1 ( 649 words): [7, 300, 242, 100]
Reading #2 ( 727 words): [115, 49, 563]
Reading #3 ( 1000 words): [1000]
Reading #4 ( 723 words): [400, 9, 14, 300]
Reading #5 ( 600 words): [200, 400]
Reading #6 ( 729 words): [500, 200, 10, 19]
Reading #7 ( 1876 words): [1876]
Reading #8 ( 902 words): [100, 200, 15, 59, 299, 144, 85]
Reading #9 ( 1000 words): [400, 600]
Reading #10 ( 892 words): [534, 200, 143, 15]
>>> print_solution(solve(section_words, heuristic, 5))
Total=9098, 5 readings, avg=1819.60
Reading #1 ( 2376 words): [7, 300, 242, 100, 115, 49, 563, 1000]
Reading #2 ( 2023 words): [400, 9, 14, 300, 200, 400, 500, 200]
Reading #3 ( 1905 words): [10, 19, 1876]
Reading #4 ( 1302 words): [100, 200, 15, 59, 299, 144, 85, 400]
Reading #5 ( 1492 words): [600, 534, 200, 143, 15]
>>> print_solution(solve(section_words, heuristic, 3))
Total=9098, 3 readings, avg=3032.67
Reading #1 ( 3099 words): [7, 300, 242, 100, 115, 49, 563, 1000, 400, 9, 14, 300]
Reading #2 ( 3205 words): [200, 400, 500, 200, 10, 19, 1876]
Reading #3 ( 2794 words): [100, 200, 15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]
这是代码。尽管我建议您尝试自己实现它以进行良好的练习!
子问题是:用读数R(n, i, j)
分割部分的最低坏处是什么i
?j
n
基本情况很简单:
R(1, i, j) = heuristic(num words in sections i thru j, total words / total sections)
然后对于递归,您可以从所有可能的方法中找到最佳解决方案,以将您留下的部分数量拆分为左侧和右侧,以及放置该分区的最佳位置:
R(n, i, j) = the lowest badness out of
R(1, i, i+1) + R(n-1, i+1, j)
R(1, i, i+2) + R(n-1, i+2, j)
...
R(1, i, j-1) + R(n-1, j-1, j)
R(2, i, i+1) + R(n-2, i+1, j)
R(2, i, i+2) + R(n-2, i+2, j)
...
R(2, i, j-1) + R(n-2, j-1, j)
...
...
R(n-1, i, i+1) + R(1, i+1, j)
R(n-1, i, i+2) + R(1, i+2, j)
...
R(n-1, i, j-1) + R(1, j-1, j)
病理情况是当您的读数多于部分时:
R(n, i, j) = infinity if n > j-i
你构建解决方案从n=1
上到上,然后从j-i = 1
上到上,然后从i=0
上到上。
它最终有 5 个嵌套的 for 循环,所以我不确定它是否尽可能高效,但它似乎可以解决问题。