Алгоритм восхождения на холм для генерации строки с использованием расстояния Левенштейна как эвристического в Python?

Question

Я следил за этой книгой, и я застрял на одном из их вопросов самопроверки, который продолжается так:

Самопроверка

Вот самопроверка, которая действительно охватывает все до сих пор. Возможно, вы слышали о теореме бесконечной обезьяны? Теорема гласит, что обезьяна, произвольно нажимающая клавиши на клавиатуре пишущей машинки в течение бесконечного времени, почти наверняка наберет заданный текст, например, полное собрание сочинений Уильяма Шекспира. Хорошо, предположим, что мы заменили обезьяну функцией Python. Как вы думаете, сколько времени понадобится Python-функции, чтобы сгенерировать всего одно предложение Шекспира? Предложение, за которое мы будем стрелять: "Мне кажется, это как ласка"

Вы не захотите запускать его в браузере, так что запустите вашу любимую Python IDE. Мы будем имитировать это, написав функцию, которая генерирует строку длиной 27 символов, выбирая случайные буквы из 26 букв алфавита плюс пробел. Мы напишем другую функцию, которая будет оценивать каждую сгенерированную строку, сравнивая случайно сгенерированную строку с целью.

Третья функция будет неоднократно вызывать генерацию и оценку, а затем, если 100% букв верны, мы готовы. Если буквы не верны, тогда мы сгенерируем целую новую строку. Чтобы упростить отслеживание прогресса вашей программы, эта третья функция должна выводить лучшую сгенерированную на данный момент строку и ее счет каждые 1000 попыток.

Самостоятельная проверка

Посмотрите, сможете ли вы улучшить программу при самопроверке, сохранив правильные буквы и изменив только один символ в лучшей строке. Это тип алгоритма в классе алгоритмов "восхождения на гору", то есть мы сохраняем результат, только если он лучше предыдущего.

Я написал некоторый код, который выполняет первую часть этой задачи, используя расстояние Левенштейна между генерируемыми и необходимыми строками.

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: Как я могу написать алгоритм восхождения на холм, который использует расстояние Левенштейна в качестве эвристики, пока он не генерирует определенную строку? Пожалуйста, опишите процесс.

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.

В этой книге приведены примеры и полные программы об алгоритмах IA, оптимизации и эвристике (для меня это все алгоритмы IA), включая алгоритм восхождения на холм.

Answer 3

Вот полное решение для восхождения на холм, которое занимает менее 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()