交換法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 交換法の意味・解説 

貪欲法

(交換法 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/14 23:53 UTC 版)

貪欲法(どんよくほう、: greedy algorithm)は、アルゴリズムの一種、欲張り法(よくばりほう)、グリーディ算法(グリーディさんぽう)ともいう。

概要

貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。

このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、多くの問題に対して多項式時間での近似アルゴリズムとなる。

問題を複数に分割する方法は特に組合せ最適化問題と相性が良い。問題によっては厳密解(最適解)を得られたりするものや最低限の精度保証(近似度)が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。

厳密解(最適解)が求まる例

いくつかのアルゴリズムは貪欲法を基本戦略としているものの、厳密解が求まることが証明されている。

最適化問題で厳密解となるには、動的計画法同様、部分構造最適性(: optimal substructure)、つまり、部分問題を解き、それを利用して最適化問題の厳密解が解けることが必要である。

厳密解(最適解)が求まらない例

以下にナップサック問題での適用例を示す。この問題の場合は各荷物ごとに分割して評価することで適用可能である。

  1. ナップサック問題の各荷物の評価値を決定する。(価値)÷(容積)という数字がよく使われる。
  2. 評価値の一番高い荷物を選ぶ。
  3. その荷物をナップサックに入れても最大容量を越えないならナップサックに入れる。
  4. 全ての荷物を評価値の順に選び上記の操作を繰り返す。

なお、この問題に関しては貪欲法では最適解を得られない。

擬似コード

以下の擬似コードでは荷物の数を n とし、荷物 i の容量と価値はそれぞれ w[i]、c[i] に格納されているとする。評価値は e[i] ナップサックの現在の容量は W 最大容量は max に格納されており、返すコストを C とする。

for i := 1 .. n
  e[i] := c[i] / w[i]

e[i] の値を降順にソートして、 c[i], w[i] をそれに合わせて並び替える。

C := 0; W := 0
for i := 1 .. n
  if w[i] + W < max then
    W := W + w[i]
    C := C + c[i]
return C

「交換法」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「交換法」の関連用語

交換法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



交換法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの貪欲法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS