多くの選択肢から最適解を見つける方法を勉強してみた!!

最適化問題とも言われ、たくさんある選択肢の中から、最適な解を選び出す手法で、「グリーディ法」と呼ばれている。

グリーディ法は近似アルゴリズムの一種で、最適解ではなくてもそれほど悪くない解を(近似解)を得る手順のことで、"BEST"より"BETTER"を探し出す手法と言うとわかりやすいと思う。

最適解を得るのに、膨大な計算を要する場合、短時間で解を得るために、近似アルゴリズムが用いられることがある。

実際において、近似解であっても無駄がなければ(誤差が一定以内)十分と判断できるはずであり、短時間で効率的に「解を得る」場合に用いられることになる。


まずは【硬貨の交換問題】から!

問題

あるお店で、、税込213円の商品を購入した場合、お客さんは1000円札を出しました。
お釣りは、

1000 - 213 = 787

です。
できるだけ少ない枚数でお釣りを返すには、どのような組み合わせにすべきでしょうか?

解答例

この問題の答えは、

  • 500円 x 1
  • 100円 x 2
  • 50円 x 1
  • 10円 x 3
  • 5円 x 1
  • 1円 x 2

となる。この解を得るためには、「できるだけ大きな硬貨を使う」と考えたと思う。

つまりこれが『グリーディ法』である。

グリーディ(Greedy)とは、「貪欲な」という意味で、「可能な限り大きな硬貨を使う」というアイデアを『貪欲』と表現しているのである。

プログラム例

ではこれを実際のプログラムにするとどのようになるのか?
例を以下に記してみる。

#include <stdio.h>

int main(int atgc, char* argv[]) {
    //お釣り、枚数、枚数の合計、ループカウンタ
    int change, n, sum, i;

    //硬貨の種類
    int val[] = {500, 100, 50, 10, 5, 1};

    printf("お釣りは?");
    scanf("%d", &change);

    sum = 0;
    for (i = 0; i < 6; i++) {
        n = change / val[i];
        printf("%d円硬貨 : %d枚", val[i], n);
        sum += n;
        change %= val[i];
    }

    printf("硬貨の合計枚数: %d枚\n", sum);

    return 0;
}

このように、"%"の計算を用いて、除算の余りを得る演算を繰り返すことで、より小さい硬貨へ交換するための残金を求めることができる。

現在の日本の硬貨であれば、「できるだけ大きな硬貨を使う」というグリーディ方で、最適解が得られる。

もしも新たにな硬貨が追加されたらどうなる?

グリーディ法では最適解が得られない場合が生ずる。

例えば、400円硬貨が追加された場合どうだろう?

先ほどのプログラム例で、

int val[] = {500, 400, 100, 50, 10, 5, 1};

for (i = 0; i < 6; i++)

の部分を

for (i = 0; i < 7; i++)

に健康して、お釣り800円を置き換える硬貨の枚数を求めてみる。

400円硬貨があるなら、

  • 400円 x 2

が、最適解となるが、プログラム実行の結果は、

  • 500円 x 1
  • 400円 x 0
  • 100円 x 3
  • 50円 x 0
  • 10円 x 0
  • 5円 x 0
  • 1円 x 0

となる。「できるだけ大きな硬貨を扱う」というグリーディ法では、最適解を得られないことがあるというのが特徴。
ただし、

  • 1円 x 800

といったおかしな解にもなりません。

これと比較した時、今回の例では、硬貨の枚数が2枚でも4枚でも大きな差はないと言え、「4枚という近似解は十分に実用的」と言える。

以上から、

「プログラミングをする以上、正確無比な最適解を常に求めなければならない!!」と思いがちではあるが、実生活において、「最適解を求めるまでに、時間を要するのであれば、近似解を1秒で求めた方が実用的だ!」と判断する場面は多い。

このことからプログラムにおいても、『実用性』を考慮した設計・仕様が重要と言える。