1

我一直在关注这本电子书，但我被他们的一个自我检查问题困住了，这个问题是这样的：

自检

这是一个自我检查，真正涵盖了到目前为止的所有内容。你可能听说过无限猴子定理？该定理指出，一只猴子在打字机键盘上随机敲击无限时间的键几乎肯定会键入给定的文本，例如威廉·莎士比亚的全集。好吧，假设我们用 Python 函数替换猴子。你认为一个 Python 函数只生成一个莎士比亚的句子需要多长时间？我们要拍摄的句子是：“我认为它就像一只黄鼠狼”</p>

你不想在浏览器中运行这个，所以启动你最喜欢的 Python IDE。我们将模拟这种情况的方法是编写一个函数，该函数通过从字母表中的 26 个字母加上空格中选择随机字母来生成一个 27 个字符长的字符串。我们将编写另一个函数，通过将随机生成的字符串与目标进行比较，对每个生成的字符串进行评分。

第三个函数将重复调用 generate 和 score，然后如果 100% 的字母是正确的，我们就完成了。如果字母不正确，那么我们将生成一个全新的字符串。为了更容易跟踪程序的进度，第三个函数应该打印出迄今为止生成的最佳字符串及其每 1000 次尝试的得分。

自检挑战

看看您是否可以通过保持正确的字母并仅修改迄今为止最好的字符串中的一个字符来改进自检中的程序。这是“爬山”算法中的一种算法，也就是说，我们只保留比前一个更好的结果。

我编写了一些代码，使用生成的字符串和所需字符串之间的 Levenshtein 距离来完成这个挑战的第一部分。

import random, string, nltk

def string_generator(length, collection):
    """
    takes all characters in collection and generates a string of size length.
    """
    return ''.join([random.choice(collection) for _ in xrange(length)])

def string_tester(output, text):
    """
    compares strings given and returns the Levenshtein distance.
    """
    return nltk.metrics.edit_distance(output, text)

if __name__ == '__main__':
    collection = [x for x in (string.ascii_lowercase + ' ')]
    longest_distance = 27
    best_string = None
    ctr = 0
    while True:
        random_string = string_generator(26, collection)
        distance = string_tester(random_string, "methinks it is like a weasel")
            ctr += 1
        ctr %= 1000
            if distance < longest_distance:
            best_string = random_string
            longest_distance = distance
            # end if the string generated is same as the one given
        if longest_distance == 0:
            print best_string
            print longest_distance
            break
            # use the best string to generate a better string every 1000th time
        if ctr == 0:
            print longest_distance
            print best_string
            # TODO: optimization here

我不知道如何在 TODO 中生成更好的字符串 - 在迭代之前使用最好的字符串和给定的方法。

tl;dr： 我如何编写一个爬山算法，使用 Levenshtein 距离作为其启发式算法，直到它生成某个字符串？请概述过程。

4

3 回答 3

2 
target_word = "hello world"
target_size = len(target_word)
alphabet = "abcdefghijklmnopqrstuvwxyz "
def make_guess(alphabet,size):
   return "".join(random.choice(alphabet) for _ in range(size))

guess = make_guess(alphabet,target_size)

for i in itertools.count(0):
   if guess == target_word:
      break;
   if not i % 1000:
      print "Best So Far:",guess
   #climb hill and replace our guess if our next guess is better
   guess = min(guess,make_guess(alphabet,target_size),key=lambda _guess:levenstein(_guess,target_word))
print "Final Guess:",guess

这被称为爬山，因为只有在下一个潜在解决方案更好时才会替换潜在解决方案。这可能会导致其他类型的问题陈述出现问题，您会发现局部最大值或最小值，它们的性能相对较好，但您会错过全局最大值或最小值

于 2013-12-19T18:45:30.700 回答
1

请参阅：Python 集体智能编程。

本书提供了有关 IA 算法、优化和启发式（对我来说都是 IA 算法）的示例和完整程序，包括爬山算法。

于 2013-12-19T18:45:42.547 回答
1

这是爬山的完整解决方案，它需要不到 100 次迭代。

import string
import random

def randomGen(goalList):
    characters = string.ascii_lowercase+" "
    randString =""
    for i in range(len(goalList)):
        randString = randString+characters[random.randrange(len(characters))]
    randList = [randString[i] for i in range(len(randString))]
    return randList

def scoreRand(goalList,randList):
    numScore = 0
    for i in range(len(goalList)):
        if goalList[i] == randList[i]:
            numScore = numScore+1
    return numScore / len(goalList)

def common_elements(clist,list1, list2):
    for i in range(len(list1)):
        if list1[i] == list2[i]:
            clist[i] = list1[i]
    return clist

def main():
    goal = "methinks it is like a weasel"
    goalList = [goal[i] for i in range(len(goal))]
    clist = [' ' for i in range(len(goal))]
    randList = randomGen(goalList)
    clist = common_elements(clist,goalList, randList)
    score = scoreRand(goalList,clist)
    totalIteration = 0
    while(score < 1):
        newrandList = randomGen(goalList)
        newclist = common_elements(clist,goalList, randList)
        newscore = scoreRand(goalList,clist)
        score = newscore
        randList = newrandList
        clist = newclist
        totalIteration = totalIteration+1
        print(score," : ",''.join(clist))
    print("Total iterations: ",totalIteration)

main()
于 2018-03-30T10:18:31.100 回答