問題タブ [hill-climbing]

私はPythonを学ぶための本を読んでいますが、その本には次のいずれかの課題があります:

セルフチェック

これまでのすべてを本当にカバーするセルフチェックです。無限猿の定理について聞いたことがあるかもしれません。この定理は、サルがタイプライターのキーボードで無作為にキーを無限に打てば、ほぼ確実に特定のテキスト (ウィリアム シェイクスピアの全作品など) をタイプすることを示しています。さて、サルを Python 関数に置き換えたとします。Python 関数がシェークスピアの 1 文だけを生成するのにどれくらいの時間がかかると思いますか? 狙う文は「イタチのようだと思う」</p>

これをブラウザで実行したくないので、お気に入りの Python IDE を起動してください。これをシミュレートする方法は、アルファベット 26 文字とスペースからランダムな文字を選択して、28 文字の長さの文字列を生成する関数を作成することです。ランダムに生成された文字列を目標と比較して、生成された各文字列をスコアリングする別の関数を作成します。

3 番目の関数は generate と score を繰り返し呼び出し、文字が 100% 正しければ完了です。文字が正しくない場合は、まったく新しい文字列を生成します。プログラムの進行状況を簡単に追跡できるようにするために、この 3 番目の関数は、これまでに生成された最良の文字列と 1000 回の試行ごとのスコアを出力する必要があります。

次のコードを使用して、課題のこの部分を実装することができました:(私はpythonが初めてです)

次に、次の追加の課題があります。

セルフチェックチャレンジ

正しい文字を維持し、これまでのところ最適な文字列の 1 文字のみを変更することで、セルフ チェックでプログラムを改善できるかどうかを確認してください。これは、「山登り」アルゴリズムのクラスのアルゴリズムの一種です。つまり、前の結果よりも優れている場合にのみ結果を保持します。

ただし、この山登りアルゴリズムが何であるか、既存のコードにどのように実装するかを理解することはできません。

この山登りアルゴリズムの実装方法を説明してください。どうもありがとうございました!

たとえば、次の問題があります。

適用できる唯一の演算子は次のとおりです。

• 構造物から一番上のブロックを下に置く
• ストラクチャーにないブロックをストラクチャーの一番上に配置する

私はヒューリスティック関数を持っています：

• h(n) = ブロックが正しく配置されている場合はサポート ブロックごとに +1、ブロックが正しく配置されていない場合はサポート ブロックごとに -1。

この例では、「A」ブロックが正しく配置されているため、A の下のサポート ブロックごとに +3 を取得します。「D」が正しく配置されていないため、-2 を取得します。C が正しく配置されている場合、別の +1 を取得します。したがって、ヒューリスティック関数は 3 + 1 - 2 = +2 の値を返すようになりました。

ここでのアルゴリズムに基づいて、アルゴリズムは目標状態に達したときにのみ終了し、より良いヒューリスティック値が得られた場合にのみ、現在の状態として次の状態を選択します。ただし、上記で作成したケースでは続行できなくなりました。構造から A を下に置くと、以前の値 (+2) よりも悪いヒューリスティック値 -1 が得られます。

例を変更した理由 Simple Hill Climbing アルゴリズムで極大問題に遭遇したときを示したいのですが、これは極大問題ですよね? 別の質問ですが、アルゴリズムは目標状態に達したときにのみ終了すると言っていますが、終了することはありません。それとも、近隣の他の州がもはやより良い結果を出さなくなったときに、それも終了すると仮定するのは正しいですか?

数値計算部分が大きいアルゴリズムを開発しています。私のプロジェクトのスーパーバイザーは、この理由から Fortran を使用するように勧めてくれました。そのため、ここ数週間、私は Fortran に取り組んできました (これまでのところ非常にうまくいっています)。それは彼のアルゴリズムの新しいバージョンであり、基本的には多くの数値計算です。

ただし、私の場合は、より多くの「ロジック」が必要です。詳しくは説明しませんが、ブルート フォース アプローチは fortran だけを使用して行われます。これは、ファイルからの読み取りと操作の実行の 95% にすぎないためです。しかし、このプロジェクトの目的は、これを行うための効率的なアルゴリズムを提供することです。私は方法について考えていて、貪欲なアプローチ (ヒル クライミングのようなもの) から始めたいと思っていました。 Fortran ではなく C++ でアルゴリズムを記述した方がよいでしょう。

基本的に、C++ でアルゴリズムの「ロジック」を開発し、数値計算の大部分を実行する必要があるたびに Fortran を呼び出すのはどれほど難しいと思いますか。それは価値があるでしょうか？それとも、2 つの言語のうちの 1 つに固執する必要がありますか?

非常に無知な質問で申し訳ありませんが、Hill Climbing などのアルゴリズムを C++ ではなく Fortran で作成した場合に作成するのがより難しくなるかどうか、またこの場合の Fortran の利点に価値があるかどうかはわかりません。

お時間をありがとうございました。良い一日を！