ikarosの作業場

飛行機の設計もできる系のCshaper。「なおこの記事は個人的見解であり、所属する組織の意見とは一切関係がありません」と書かざるを得なくなった悲しみを知れ

アルゴリズム入門:動的計画法

突然ですが、予備校生という職業柄、こういった問題を日々の演習として解いております

Q.下の図においてAからBまでの最短ルートは何通り存在するか?
(ただし通れるのは黒線のところだけ)
f:id:ikarostech:20150514221731p:plain

でこういうときには、次のような書き込みをして答えを叩き出します
f:id:ikarostech:20150514221820p:plain

これは各地点にたどり着くための経路数(下の数字と左の数字を足していくのを繰り返し)を書き込んでいって
最終的にB地点まで足し合わせていくという方法です。

  • ある問題を細かい問題の塊だとみてその計算結果を保存して次の問題の答えを芋づる式に計算していく-

こういった手法を「動的計画法」といいます。
この手法は様々なプログラムのアルゴリズムでも用いられています

というわけでこの問題をプログラム上で解いてみましょう
とりあえずそのようなアルゴリズムを実装したものが以下になります

namespace dynamic_programming
{
    /// <summary>
    /// MainWindow.xaml の相互作用ロジック
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();

            //面倒くさいので正方形の塊として使わない変数があってもいいやって感じで定義
            int[,] block = new int[5, 5];

            //全てのブロックを初期化
            for (int i = 0; i < 5; i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    block[i, j] = 0;
                }
            }

            //一番下の列([0,k]番地)に1を代入
            for(int k=0; k<5; k++)
            {
                block[0, k] = 1;
            }
            //下から上へと足していくように計算していく
            //番地の表し方は[i,j]
            for(int i=1; i<5; i++)
            {
                for (int j = i - 1; j < 5; j++)
                {
                    if (j == i - 1)
                    {
                        block[i, j] = block[i - 1, j];
                    }
                    else
                    {
                        block[i, j] = block[i, j - 1] + block[i - 1, j];
                    }
                }
            }

            int result = block[4, 4];
        }
    }
}

最初に一番下に代入して言ってだんだん上に番地を上げていく・・・
blockという変数に次々とメモをしているのがお分かりいただけたでしょうか?
フィボナッチ数列とかもこういった類で解きやすいものの一つではないでしょうか。

で?何の役に立つのということですが、うまく使いこなせば計算量を減らすことができます。
特にプログラム上では「ナップザック問題」等が知られ最適解を求める方法の一つとして用いられる
古典的なアルゴリズムの一つです。
ex.
動的計画法(ナップサック問題) - アルゴリズム講習会


以上!

当サイトのソースコード及びその他の情報は個人・商用問わず自由に使っていただいてかかまいませんが、当サイトの情報が元で発生したいかなる結果・不利益については責任を負いかねますのでご了承ください