攀爬算法在Python中使用Levenshtein距離作爲啓發式生成一個字符串？

Question

我一直在關注這個ebook，我停留在他們的自我檢查的問題，它繼續像這樣的：

自我檢查

這裏有一個自我檢查，真正涵蓋了目前爲止。你可能有 聽說過無限猴子定理？該定理指出，在打字機鍵盤上隨機敲擊鍵的猴子 時間幾乎肯定會鍵入給定文本，例如威廉莎士比亞的完整作品 。那麼，假設我們用Python函數替換了一隻猴子。你認爲用Python 函數生成一個莎士比亞的句子需要多長時間？我們就開槍了一句 是：「記錯它像一隻黃鼠狼」

你不會想運行這一個在瀏覽器，因此火起來 你最喜歡的Python IDE。我們模擬這個的方式是編寫一個 函數，該函數生成一個長度爲27個字符的字符串，由 選擇字母表中的26個字母加上 空間中的隨機字母。我們將編寫另一個函數，通過將隨機生成的字符串與目標進行比較來對每個生成的 字符串進行評分。

第三個函數將重複調用generate和score，然後如果字母的100％正確，我們就完成了。如果這些字母不正確 那麼我們將生成一個全新的字符串。爲了使您的程序的進度更容易遵循 ，這個第三個函數應該輸出迄今爲止生成的最好的 字符串，並且每1000次嘗試它的得分。

自檢挑戰

看看你是否可以通過保持 字母是正確的，僅修改了最好的 串一個字符到目前爲止在在自檢程序改善。這是'hill '算法中的一種算法類型，也就是說，如果 比前一個更好，我們只保留結果。

我寫了一些代碼，用生成的和需要的字符串之間的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距離作爲啓發式的爬山算法，直到它產生一個特定的字符串？請概述過程。

Answer 1

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 

這就是所謂的爬坡，因爲潛在的解決方案只有如果下一個可能的解決方案是更好的被替換。這可能會導致其他類型的問題陳述出現問題，您會發現本地最大值或最小值，表現相對較好，但您將錯過全局最大值或最小值

Answer 2

請參閱：Python collective intelligence programming。

這本書帶來了關於IA算法，優化和啓發式（全部是我的IA算法）的例子和完整的程序，包括爬山算法。