什么是"天真"算法,什么是"封闭式"解决方案？

Question

关于描述算法时使用的术语的语义,我有几个问题.

首先,'天真'算法是什么意思？这与给定问题的其他解决方案有何不同？解决方案可采取哪些其他形式？

其次,我听到很多关于采用"封闭式"解决方案的建议.我不知道这意味着什么 - 但通常在尝试解决复发关系时出现...

谢谢你的时间

Answer 1

一个天真的算法通常是当一个人问一个问题,最明显的解决方案.它可能不是一个聪明的算法,但可能会完成工作(......最终.)

例如.尝试搜索已排序数组中的元素. 朴素算法将使用线性搜索.一个不那么天真的解决方案是使用二进制搜索.

一个更好的例子,将是字符串搜索的情况下,天真的算法远远小于有效Boyer–Moore或Knuth–Morris–Pratt算法

一个封闭形式的解决方案是一个简单的解决方案,可以立即工作没有任何循环,功能等.

例如:从1到n的整数之和的迭代算法

s= 0
for i in 1 to n
s = s + i
end for
print s

封闭表格(针对同一问题)

s = n * (n + 1 ) /2

Answer 2

朴素算法是一种非常简单的算法,具有非常简单的规则.有时会想到第一个.它可能是愚蠢而且非常慢,甚至可能无法解决问题.它有时可能是最好的.这是一个问题和" 天真 "算法的例子:

问题:你处于一个(二维)迷宫中.找到出路.(意思是:到一个带" 退出 "标志的地方:)

朴素算法1:开始步行,在你遇到的每个交叉路口选择合适的算法(直到找到"退出").

朴素算法2:开始步行并在你遇到的每个交叉路口中选择一个随机算法(直到找到"退出").

算法1甚至不会让你离开一些迷宫!

算法2将使你脱离所有迷宫(尽管这很难证明).