私はこの電子ブックをフォローしてきましたが、次のようなセルフ チェックの質問の 1 つに行き詰まっています。
セルフチェック
これまでのすべてを本当にカバーするセルフチェックです。無限猿の定理について聞いたことがあるかもしれません。この定理は、サルがタイプライターのキーボードで無作為にキーを無限に打てば、ほぼ確実に特定のテキスト (ウィリアム シェイクスピアの全作品など) をタイプすることを示しています。さて、サルを Python 関数に置き換えたとします。Python 関数がシェイクスピアの 1 文だけを生成するのにどれくらいの時間がかかると思いますか? 狙う文は「イタチのようだと思う」</p>
これをブラウザで実行したくないので、お気に入りの Python IDE を起動してください。これをシミュレートする方法は、アルファベット 26 文字とスペースからランダムな文字を選択して、27 文字の長さの文字列を生成する関数を作成することです。ランダムに生成された文字列を目標と比較して、生成された各文字列をスコアリングする別の関数を作成します。
3 番目の関数は generate と score を繰り返し呼び出し、文字が 100% 正しければ完了です。文字が正しくない場合は、まったく新しい文字列を生成します。プログラムの進行状況を追跡しやすくするために、この 3 番目の関数は、これまでに生成された最良の文字列と 1000 回の試行ごとのスコアを出力する必要があります。
セルフチェックチャレンジ
正しい文字を維持し、これまでのところ最適な文字列の 1 文字のみを変更することで、セルフ チェックでプログラムを改善できるかどうかを確認します。これは、「山登り」アルゴリズムのクラスのアルゴリズムの一種です。つまり、前の結果よりも優れている場合にのみ結果を保持します。
生成された文字列と必要な文字列の間のレーベンシュタイン距離を使用して、この課題の最初の部分を実行するコードをいくつか書きました。
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: 特定の文字列を生成するまで、レーベンシュタイン距離をヒューリスティックとして使用するヒル クライミング アルゴリズムを作成するにはどうすればよいですか? プロセスを概説してください。