最近アルゴリズムを勉強し始めて学んだことをアウトプットしようとおもいます。
基本から
アルゴリズムの大前提を5つ紹介します。
①アルゴリズムは、問題を解くための手順
②必要な結果を得るためのアルゴリズムは1つだけではない
③アルゴリズムは、作業者によらず、またどんな環境でも同じ結果が得られるもの
④アルゴリズムは「正当性」「有限性」「停止性」を満たしていなくてはならない
⑤アルゴリズムは組み合わせ爆発によって、実行に膨大な時間がかかることがある
①からみていきます
①アルゴリズムは、問題を解くための手順
よく聞く言葉だとおもいます。
たとえば、計算を考えてみればわかるとおもいます。
1+1という問題があったとしたら、1という数字に1を足してあげることでその問題は解決しますね。
②必要な結果を得るためのアルゴリズムは1つだけではない
たとえば、ある四角形があるとします。
欲しい結果は、その四角形を一周する、だとします。
これって必要な結果を得るためのアルゴリズムは2つ存在しますよね。
時計回りと反時計回りがあります。
このように、アルゴリズムが必要な結果を得るための方法は1個ではないんです。
③アルゴリズムは、作業者によらず、またどんな環境でも同じ結果が得られるもの
これはアルゴリズムを考える上での、大前提です。
たとえば、カレーを作るアルゴリズムを例にして考えてみましょう。
「まず、お肉を切って、火が通るまで炒めます」
という、処理があった場合、「火が通る」というのはどのラインを言うのかが人によってマチマチだったら味も多少なりとも変わってきてしまいますね。
これでは、「作業者によらず、またどんな環境でも同じ結果が得られるもの」にあてはまりません。
「火が通る」の定義を正しくしてあげることで、それを満たすことができます。
このように、いつ何時でも同じ結果を出せることが重要なんです。
④アルゴリズムは「正当性」「有限性」「停止性」を満たしていなくてはならない
正当性
まず正当性から見ていきましょう。
正当性とはその名の通り、ある課題に対して、要求してる結果が返ってくることをいいます。
1＋1の結果が、あるときは2になり、あるときは10になったり、あるときは100になっては困りますもんね。
決定性
次に決定性です。決定性とは、ある結果を決定してそれを出力してくれることです。
先ほどの1+1でいえば、この答えを決定できない、と出力されるとちょっと勘弁して欲しいですよね笑
有限性と停止性
アルゴリズムはいつ終わるのか、という有限性がないといけません。
Google検索のアルゴリズムで考えてみると、いつまでも検索し続ける検索エンジンってイヤですよね笑
つまり有限性と停止性はセットなんです。
⑤アルゴリズムは組み合わせ爆発によって、実行に膨大な時間がかかることがある
アルゴリズムの組み合わせがよくないと、実行時間がめちゃくちゃかかってしまうことがあるんです。
それが組み合わせ爆発ってやつです。
有名なものには、巡回セールスマン問題というのがあるので、興味がある方は調べてみてください
以上です。何か間違いがございましたら、ご教示いただけますと幸いです。
【参考資料】