過去1年間で最も興味深いPythonの本の1つは、 DavidKopecによるPythonのClassicComputer ScienceProblemsです。
この本にまだ慣れていない方のために、2019年10月のオリジナル版に従って書かれたレビューを提供します。Redditに関する小さなディスカッションをチェックすることもでき ます。また、誰もが追加の印刷について意見を述べることができます-このために、記事の最後に投票投票があります。
DavidKopecの「ClassicalComputerScience ProblemsinPython」という本が本当に気に入りました。それは本当に多くの異なる問題、私が前に出くわしたことがない詳細な情報に対処します。ほんの数例：ニューラルネットワーク、制約充足問題、遺伝子アルゴリズム、ミニマックスアルゴリズム。アルゴリズムとプログラミングの問題に関する他の多くの本とは異なり、この本は、自分で簡単に探索できる完全な（しかし小さな）プログラムを示しています。
私はアルゴリズムの学習を楽しんでいます。私は「Programmer'sCareer」という本を 読み、いくつかのMOOCコース、特に教授から「アルゴリズムの設計と分析」を受講 しました。 ティム ラフガーデン。それにもかかわらず、コペックの本にはそのようなアルゴリズムもありましたが、その言及は私が前に見たことがありません。
私が最も好きだった章
ニューラルネットワーク。この本の中で私のお気に入りのセクションは、ニューラルネットワークについてです。著者は、本格的なニューラルネットワークの作成について説明します。その間、彼はそのすべての部分がどのように機能するかを説明します-一般的にそして特に。ニューロンとレイヤーがどのように配置されているか、アクティベーション機能がどのように機能するか、トレーニング中に逆伝播がどのように使用されるか、重みがどのように修正されるかについて説明します。
最後に、フィッシャーの菖蒲の例としてニューラルネットワークを使用します。これは1930年代に編集された古典的なデータセットで、さまざまな種類の菖蒲に属する花の150の標本（それぞれ50の標本）が含まれています。各標本には4つの数値が付いています。外側のペリアンスローブの長さ。外側のペリアンスローブの幅。内側のペリアンス葉の長さ;内側のペリアンスローブの幅。値は最初に正規化されます。次に、3層メッシュが作成されます。入力層には4つのニューロンがあり（サンプルからの入力値のカテゴリごとに1つ）、隠れ層には6つのニューロンがあり、出力層には3つのニューロンがあります（検討中の虹彩のタイプごとに1つ）。
150個のサンプルから140個がランダムに選択され、ネットワークのトレーニングに使用されました。トレーニングは、50回の反復で140サンプルを超えて実行されます。次に、ネットワークを使用して、残りの10個のサンプルが3つの虹彩種のどれに属するかを予測します。ほとんどの場合、ネットワークは10個のサンプルのうち少なくとも8個、そしてかなり頻繁に10個すべてを正しく識別します。
私はこの経験が本当に気に入りました。機械学習ライブラリに頼らずにニューラルネットワーク全体を最初からプログラムすることです。私はしばらくの間このプログラムを試しました（本のすべてのコードはGitHubに投稿され ています）。たとえば、ネットワークが完全にトレーニングされた後、すべてのニューロンのすべての重みのプリントアウトを印刷しました。異なる実行間の重みの間に類似性があるかどうかを確認したかったのです。重みは実行ごとに著しく異なることが判明しましたが、すべての場合の予測成功率は同じままでした。これは初歩的な真実かもしれませんが、私はこれを自分で見ることに非常に興味がありました。
敵対的検索..。この章では、ミニマックスアルゴリズムを紹介します。彼は2人の対戦相手が関与するゼロサムゲームで最高の動きを見つけます。アイデアは、一方または他方の対戦相手に代わって話し、潜在的な動きを分析することです。各対戦相手は、ゲームが終了するまで（または最大再帰深度に達するまで）行われた最後の動きに反応します。この本の最初の例では、AIはtic-tac-toeを再生しています。この場合、競技場のサイズは3 x 3セルしかないため、一連の動き全体を完全に分析できます。
他の章と同様に、一般的な構造は最初にここで開発され、次に複雑なケースに関連して検討されます。 tic-tac-toeの例の後、ゲーム " 4列に並んでいます。」この場合、動きの評価は「Tic-Tac-Toe」よりもはるかに難しいため、ここでは深度検索は3つの動きに制限されています。ミニマックスアルゴリズムの説明を見たことがなかったので、この章によく目を向けました。
満足度タスク..。一般的なフレームワークもここで開発され、いくつかの問題を解決するために使用されます。この構造の中心には、再帰的なバックトラックがあります。この章で解決される最初の問題は、オーストラリアの地図に色を付ける作業です。地域間の境界の両側にある隣接する領域の色が異なるように、3色だけで地図に色を付けることは可能ですか？ （回答：はい）。 2番目のタスクは、チェスボードに8つのクイーンを配置し、他のクイーンからの攻撃を受けていないことを確認することです。 3番目のタスクは、単語リストをグリッドに配置して、単語を検索するための正方形を形成することです。最後に、この構造を使用して、古典的な暗号算術パズルSEND + MORE = MONEYを解きます。目標は、結果として得られる算術的同等性が正しくなるように、各文字がどの桁に対応するかを見つけることです。
この章が気に入ったのは、非常に多様な例がたくさん含まれていることと、このような問題を（少なくとも体系的に）解決するためにこのアプローチを以前に使用したことがないためです。
遺伝的アルゴリズム。この章を読む前は、遺伝子アルゴリズムがどのように機能するかについての非常に一般的な考えしかありませんでした。この章のコードは、ランダムに選択された遺伝子によってインスタンス化される染色体クラスを示しています。染色体は、環境への自身の適応性を評価し、交配（同じタイプの別の染色体との組み合わせ）を実装し、変異（それ自体に小さな完全にランダムな変化をもたらす）もできます。
アルゴリズムはランダムな母集団から始まります。この母集団の各世代で、アルゴリズムは（適合度関数を使用して）十分に良い解があるかどうかをチェックします（適合度は指定されたしきい値を超えています）。そのような解決策がない場合は、個人のペアを交差させる操作を繰り返すことで新しい世代が作成されます（個々の個人の適合性が高いほど、これらの個人が行動を起こす可能性が高くなります）。さらに、突然変異のためにいくつかの個人が選択されます。今、これらの新しい個人は新しい人口を生み出し、再び、彼らのフィットネス機能がテストされます。このサイクルは、指定された世代数の間繰り返されます。
次の問題が例として考えられます：数式の最大化、上記の「SEND + MORE = MONEY」パズル、および圧縮時のリストのサイズを最小化するためのリスト内のアイテムの順序付け。この章の優れている点は、他の多くの章と同様に、すべての概念がコンパクトでありながら完全なソリューションのコンテキストで示されていることです。
探す..。この章のアルゴリズムは私にとって新しいものではありませんでしたが（A *を除く）、この章には例が含まれているため、それでも興味深いものです。著者は、迷路を抜ける例を使用して、幅優先検索と深さ優先検索の原則を示します。ラビリンスは通常の9x9グリッドセルで、障害物がランダムに配置されています。 ASCII文字のみを使用して画面に表示されます。アルゴリズムの助けを借りて、障害物を避けながら、斜めに進むグリッドを通るパスが見つかります。このようにして見つけられた道も迷宮を通り抜けます。
これらのプログラムを簡単に変更して、さまざまなシナリオでアルゴリズムがどのように機能するかをテストできます。Breadth First Searchに慣れた後、著者はA *について話します。違いは、パスがヒューリスティック（ユークリッド距離）を使用して描画されることです。これはガイドラインとして使用され、最初に描画するパスを示します。この章の最後の例では、検索機能を使用して、川を渡るカヌーで3人の宣教師と3人のオグレを取得します。制限は、人食い人種の数が海岸または船内の宣教師の数を超えることはできないということです。そうしないと、人食い人種は宣教師を食べてしまいます。これは、検索アルゴリズムの非常に巧妙で興味深いアプリケーションだと思います。
その他の章
他の章には、私がすでに精通しているアルゴリズムが含まれています。
簡単なタスク（最初の章）。最初の章には多くの小さな例が含まれています。最初に、フィボナッチ数を計算するさまざまな方法について説明します（特に、再帰的、メモ化、反復、およびPythonジェネレーターを使用）。次のセクションでは、圧縮およびXOR暗号のビット操作について説明します。最後に、ハノイタワーの問題を解決するには、この章で再帰を行う必要があります。
グラフの問題。第4章では、米国の地図を例として使用して、最短パスと最小スパンツリーを見つけるためのグラフアルゴリズムについて説明します。 Dijkstraのアルゴリズムも考慮されます。
K-Meansクラスタリング..。この章では、各ポイントからクラスターの中心までの相対距離に基づいて、データポイントを所定の数のクラスターにグループ化する方法を示します。この章の例は、他の章の例ほど面白くありませんでした。
その他のタスク。最後の章では、ナップザックの問題、旅行中のセールスマンの問題、電話番号のニーモニックについて説明します。
何を付けますか
すべてのプログラムはPythonのタイプヒントを使用します。私はそのようなヒントに対して2つの態度を持っています。一方では、タイプはプログラムのより良い理解に貢献します。しかし一方で、私はPythonでそれらを見ることに慣れておらず、プログラムのロジックを理解し始める前に、最初にこれらのヒントを理解しなければならないことがありました。
セクションについて文句を言う場合は、動的プログラミングについて説明しているセクションです。私の意見では、それは完全性に欠けています。動的プログラミングは注意が必要です。実際のソリューションで使用する場合は、このトピックに関する追加の例が必要になります。
結論
私がこの本を本当に気に入った主な理由は、検討されたアルゴリズムの幅広さ、自分で簡単に調査できる本格的な（同時にコンパクトなソリューション）、そしてアルゴリズムを説明するために選択された興味深い例です。