logo

TechCodeview

貪欲なアルゴリズム

貪欲なアルゴリズム は、次のようなアルゴリズムのクラスです。 局所的に最適な それぞれのステップで選択肢を見つけ、 全体最適 解決。これらのアルゴリズムでは、将来の決定の結果を考慮せず、現時点で入手可能な情報に基づいて決定が行われます。重要な考え方は、各ステップで可能な限り最善の選択肢を選択することであり、常に最適であるとは限りませんが、多くの問題に対して十分な解決策が得られることがよくあります。

この記事では、貪欲なアルゴリズムを例を挙げて理解します。また、貪欲なアプローチを使用して問題とその解決策についても見ていきます。

貪欲なアルゴリズム



Javaの休止状態とは何ですか

目次

貪欲なアルゴリズムとは何ですか?

あ 貪欲なアルゴリズム は、全体的に最適なソリューションを見つけるために各ステップで局所的に最適な選択を行う一種の最適化アルゴリズムです。長期的な影響を考慮せず、現時点で最善の選択肢を選択するという原則に基づいて運営されています。

貪欲なメソッドとは何か、および貪欲なアプローチの使用方法を学ぶには、貪欲なアルゴリズムに関する所定のチュートリアルを読んでください。

貪欲なアルゴリズムを作成する手順

貪欲アルゴリズムを定義する手順は次のとおりです。

Javaで文字列をintに変換する
  1. 問題を定義します。 解決すべき問題と最適化すべき目的を明確に述べます。
  2. 貪欲な選択を特定します。 現在の状態に基づいて、各ステップで局所的に最適な選択を決定します。
  3. 貪欲な選択をしてください。 貪欲な選択を選択し、現在の状態を更新します。
  4. 繰り返す： 解決策が見つかるまで、貪欲な選択を続けます。

指定された手順に従って、貪欲なアルゴリズムを使用して最適なソリューションを見つける方法を学ぶことができます。

貪欲なアルゴリズムの例

貪欲アルゴリズムの例は、アルゴリズムを理解する最良の方法です。貪欲なアルゴリズムの実際の例は次のとおりです。

  • フラクショナルナップザック : 容量が限られたナップザックに部分的に含めることができるアイテムの価値を最適化します。
  • ダイクストラのアルゴリズム : 加重グラフ内のソース頂点から他のすべての頂点までの最短パスを検索します。
  • クラスカルのアルゴリズム : 重み付きグラフの最小スパニング ツリーを見つけます。
  • ハフマン符号化 : より頻繁なシンボルに短いコードを割り当てることでデータを圧縮します。

貪欲なアルゴリズムの応用

沢山あります DAA における貪欲法の応用 。重要な貪欲アルゴリズムのアプリケーションには次のようなものがあります。

  • タスクをリソースに割り当てて、待ち時間を最小限に抑え、効率を最大限に高めます。
  • 限られた容量のナップザックに収めるのに最も価値のあるアイテムを選択します。
  • 画像を同様の特性を持つ領域に分割します。
  • 冗長な情報を削除してデータのサイズを削減します。

貪欲なアルゴリズムを使用するデメリットと制限

以下に、Greedy アルゴリズムの欠点をいくつか示します。

.netチュートリアル
  • 貪欲なアルゴリズムでは、常に最善の解決策が見つかるとは限りません。
  • 要素を考慮する順序は、結果に大きな影響を与える可能性があります。
  • 貪欲なアルゴリズムは局所的な最適化に焦点を当てており、より広範なコンテキストを考慮する必要があるより良いソリューションを見逃してしまう可能性があります。
  • 貪欲なアルゴリズムは、貪欲な選択によって最適な解決策が得られない問題には適用できません。

貪欲なアルゴリズムの基本:

  • 貪欲なアルゴリズム (一般的な構造と応用)
  • Greedy アルゴリズムと分割統治アルゴリズムの違い
  • 貪欲なアプローチ vs 動的プログラミング
  • Greedy、Divide and Conquer と動的計画法アルゴリズムの比較

標準的な貪欲なアルゴリズム:

  • アクティビティ選択問題
  • ジョブの順序付けの問題
  • ハフマンコーディング
  • ハフマンデコード
  • 水道接続の問題
  • ブラケットバランス調整のための最小スワップ数
  • エジプトの分数
  • 警察官が泥棒を捕まえる
  • 棚の取り付けの問題
  • マウスを穴に割り当てる

アレイ上の貪欲な問題:

  • 配列の最小積サブセット
  • ソートを使用して K 回の否定後の配列の合計を最大化する
  • 2 つの配列の積の最小合計
  • 2 つの配列のペアの差の絶対値の最小和
  • 配列を非増加にするための最小増分/減分
  • 配列を中央付近で反転して並べ替える
  • 配列で可能な長方形の面積の合計
  • 最大 K 回の連続スワップを伴う最大の辞書編集配列
  • 合計の差が最大になるように、長さ k と (N – k) の 2 つの部分配列に分割します。

オペレーティング システム上の貪欲な問題:

  • メモリ管理における First Fit アルゴリズム
  • メモリ管理におけるベストフィットアルゴリズム
  • メモリ管理におけるワーストフィットアルゴリズム
  • 最短のジョブを最初にスケジュールする
  • 一度に 2 つのジョブを許可するジョブ スケジュール
  • 最適なページ置換アルゴリズムのプログラム

グラフ上の貪欲な問題:

  • クラスカルの最小スパニング ツリー
  • Prim の最小スパニング ツリー
  • Boruvka の最小スパニング ツリー
  • ディカストラの最短経路アルゴリズム
  • ダイヤルのアルゴリズム
  • すべての都市を接続するための最小コスト
  • 最大流量問題の概要
  • 無向グラフ内の単一サイクル成分の数

NP Complete のおおよその貪欲アルゴリズム:

  • セットカバーの問題
  • ビンのパッキングの問題
  • グラフの色付け
  • K中心問題
  • 最短超文字列問題
  • MSTを用いた巡回セールスマン問題の近似解

DP の特殊なケースに貪欲:

  • 分数ナップザック問題
  • 最低限必要なコイン数

Greedy の簡単な問題 アルゴリズム :

  • n を最大の合成数に分割する
  • i 日に i 株が購入できる場合、最大株を購入します
  • N 個すべてのキャンディーを購入するための最小金額と最大金額を見つけます
  • 可能な最大合計は 3 つのスタックの合計に等しい
  • 体積の合計が最大になるように直方体を立方体に分割します
  • 指定された数量で満足できる顧客の最大数
  • 円形ロックを解除するための最小回転数
  • 指定されたスケジュールでの n バッチの m イベント用の最小部屋数
  • 大きい方のペアを削除して配列サイズを 1 にするための最小コスト
  • すべてのコインを取得するための最小コスト (各コインに許可される k 個の追加コイン)
  • すべての要素を等しくするための k 操作による最小増分
  • 指定された金額に合計される紙幣の最小枚数と価値を見つける
  • 合計が他のすべての要素より大きい最小のサブセット

Greedy における中程度の問題 アルゴリズム :

  • 停車できる最大列車数
  • 合計が K に等しい最小フィボナッチ項
  • 1 ～ n を合計の差が最小になる 2 つのグループに分割します
  • 紙を最小数の正方形にカットします
  • サイズ 2 のグループ間の最小差
  • 最小限のコストで n 本のロープを接続します
  • 鉄道/バス停留所に必要なプラットフォームの最小数
  • 与えられた条件で行列全体を横断するための最小の初期頂点
  • 桁を並べ替えた最大の回文数
  • 指定された桁数と桁の合計を持つ最小の数値を検索します
  • すべての文字が少なくとも k 回出現する、辞書編集上最大の部分列

Greedy の難しい問題 アルゴリズム :

  • k 回の更新で等しくできる最大要素数
  • 友人間のキャッシュフローを最小限に抑える
  • 基板を正方形に切断するための最小コスト
  • m 個のタスクを処理するための最小コスト (スイッチングコストが発生する)
  • 指定された制約の下ですべてのジョブを完了するまでの最小時間
  • タワーの高さの最大差を最小限に抑える
  • ソースから宛先までのパスを作成するために反転する最小エッジ
  • 数値から最小桁を削除して形成される最大の立方体を見つける
  • 隣接する 2 つの文字が同じにならないように、文字列内の文字を再配置します。
  • すべての同じ文字が d 距離離れた位置になるように文字列を並べ替えます。
  • データ構造とアルゴリズムを学ぶ | DSA チュートリアル
  • 貪欲なアルゴリズムに関する面接での質問トップ 20
  • 貪欲なアルゴリズムに関する「練習問題」
  • 貪欲なアルゴリズムに関する「クイズ」