退屈なアカデミックな本に時間を浪費しないでください！ コンピュータサイエンスの学習は楽しくてやりがいのあるものです。
Vladston Ferreira Filoが計算思考を導入し、複雑な問題を解決できるようにします。 コードの書き方を学ぶのは簡単です-コースで数週間、あなたは「プログラマー」ですが、いつでもどこでも需要があるプロになるには、基本的な知識が必要です。 ここでは、すべての開発者とプログラマーが毎日必要とする最も重要な情報のみを見つけます。
3.5。 発見的アルゴリズム
通常のチェスでは、6種類の32個のピースと、それらが移動する64個のセルがあります。 最初の4回の動きの後、さらなるポジションの数は2,880億に達し、世界で最も強いプレーヤーでさえ完璧な動きを見つけることができません。 彼らは直観に頼って十分であることが判明します。 アルゴリズムでも同じことができます。 ヒューリスティック手法、または単にヒューリスティック手法は、最良または最適であることを保証せずにソリューションに導く方法です。 網羅的検索やリターン検索などの方法が遅すぎる場合、ヒューリスティックアルゴリズムが役立ちます。 多くの優れたヒューリスティックアプローチがありますが、最も単純なものに焦点を当てます。
貪欲なアルゴリズム
問題を解決するための非常に一般的な発見的アプローチは、いわゆる「貪欲な」アルゴリズムの使用です。 彼らの主なアイデアは、以前のオプションにロールバックしないことです。 これは、リターン検索の正反対です。 言い換えれば、すべてのステップで、私たちは最良の選択をしようとしますが、それを疑問視することはありません。 バックパックの問題を新しい方法で解決するために、この戦略を試してみましょう（「フルバスト」セクションから）。
貪欲な強盗とバックパック。 強盗があなたの家に忍び込み、売りたいアイテムを盗みます。 彼はあなたのバックパックを使って盗まれたアイテムを運ぶことにしました。 彼は何をしますか？ 彼がより速く去るほど、彼が赤毛で捕まる可能性が低くなることに留意してください。
本質的に、ここでの最適なソリューションは、バックパックの問題とまったく同じでなければなりません。 しかし、強盗はバックパックの梱包のすべての組み合わせを整理する時間がないため、バックパックにすでに梱包されているものを常にロールバックして取り出す時間はありません！ 貪欲な人は、最も高価なアイテムがいっぱいになるまでバックパックに突っ込みます：
function greedy_knapsack(items, max_weight) bag_weight ← 0 bag_items ← List.new for each item in sort_by_value(items) if max_weight ≤ bag_weight + item.weight bag_weight ← bag_weight + item.weight bag_items.append(item) return bag_items
ここでは、現在のアクションが将来の選択にどのように影響するかを考慮していません。 このような「貪欲な」アプローチにより、完全な検索方法よりもはるかに高速にアイテムの選択を見つけることができます。 しかし、彼は選択の総費用が最大になるという保証はしません。
計算思考では、欲は大罪だけではありません。 立派なトレーダーとして、あなたはバックパックで最大額を押したり、旅行に出かけたいと思うかもしれません。
セールスマン。 セールスマンは、指定されたn個の都市を訪問し、開始した地点でルートを終了する必要があります。 総旅行距離を最小化する旅行プランは何ですか？
Combinatoricsセクション（第1章を参照）で見たように、このタスクで可能な組み合わせの数は爆発的な成長を示しており、都市が数個しかない場合でも、非常に大きな値に達します。 数千の都市で巡回セールスマン問題の最良の解決策を見つけることは、非常に高価です（または不可能ですらあります）。
それでも、ルートが必要です。 このタスクの簡単な欲張りアルゴリズムは次のとおりです。
1）行ったことのない最も近い都市を訪れます。
2）すべての都市を回るまで繰り返します。
貪欲なアプローチを使用するものよりも優れたヒューリスティックアルゴリズムを思い付くことができますか？ コンピューターサイエンスの専門家は、この問題について頭を悩ませています。
欲が力を征服するとき
古典的なアルゴリズムの代わりに発見的アルゴリズムを選択すると、妥協します。 結果があなたを満足させるために、あなたは完璧なソリューションからどれくらい離れることができますか？ 特定の状況に依存します。
ただし、完璧なオプションを確実に見つける必要がある場合でも、ヒューリスティックを無視しないでください。 ヒューリスティックなアプローチが最善のソリューションにつながる場合があります。 たとえば、完全な検索アルゴリズムと同じソリューションを見つけることができる「貪欲な」アルゴリズムを開発できます。 これがどのように行われるかを見てみましょう。
電気ネットワーク。 遠隔地の村は電化されていませんでしたが、そのうちの1つでは発電所を建設し始めました。 エネルギーは電力線を介して町から町へ行きます。 最小限の配線を使用してすべての村をネットワークに接続する方法は？
この問題は非常に簡単に解決できます。
1.まだネットワークに接続されていない村の中から、電化された村に最も近い村を選択して接続します。
2.すべての村が接続されるまで繰り返します。
各ステップで、接続のためにいくつかの村を選択します。これは現在、最も良く見えます。 このオプションが将来の選択にどのように影響するかを分析していないという事実にもかかわらず、電気なしで最も近い村に参加することは常に正しい選択です。 ここで幸運です。問題の構造は、「貪欲な」アルゴリズムによる解決に最適です。 次のセクションでは、優れた司令官の戦略が必要なソリューションのタスクの構造を見ていきます。
»本の詳細については、出版社のウェブサイトをご覧ください
» コンテンツ
» 抜粋
habrozhitelamiクーポンの20％割引-Computer Science