今日のトピックは「部分問題」と「最適部分構造」の概念です。これらの概念は、特に動的計画法や分割統治法といったアルゴリズムの設計において重要です。これらを理解することで、複雑な問題を効率的に解決するための基礎が築けます。
目次
基本概念の説明
部分問題
部分問題: 問題を解決するために、その問題をいくつかの小さなサブ問題（部分問題）に分解する手法です。各部分問題は、元の問題と同じ形式を持ち、それらを解決することで元の問題の解が得られます。
最適部分構造
最適部分構造: 問題が最適部分構造を持つ場合、その最適解は部分問題の最適解から構築できます。これにより、大きな問題を解決する際に、部分問題の解を組み合わせるだけで全体の最適解が得られることになります。
各言語でのサンプルコード
Python:
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 2:
return 1
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(10)) # フィボナッチ数列の例C#:
using System;
using System.Collections.Generic;
class Program
{
static Dictionary<int, int> memo = new Dictionary<int, int>();
static int Fib(int n)
{
if (memo.ContainsKey(n))
return memo[n];
if (n <= 2)
return 1;
memo[n] = Fib(n - 1) + Fib(n - 2);
return memo[n];
}
static void Main()
{
Console.WriteLine(Fib(10)); // フィボナッチ数列の例
}
}C++:
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> memo;
int fib(int n) {
if (memo.count(n))
return memo[n];
if (n <= 2)
return 1;
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
int main() {
cout << fib(10) << endl; // フィボナッチ数列の例
return 0;
}Java:
import java.util.HashMap;
public class Fibonacci {
private static HashMap<Integer, Integer> memo = new HashMap<>();
public static int fib(int n) {
if (memo.containsKey(n))
return memo.get(n);
if (n <= 2)
return 1;
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(fib(10)); // フィボナッチ数列の例
}
}JavaScript:
const memo = {};
function fib(n) {
if (n in memo) return memo[n];
if (n <= 2) return 1;
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
console.log(fib(10)); // フィボナッチ数列の例各言語の解説
Python: memoを用いた再帰的なアプローチで、部分問題をメモ化することで計算を効率化しています。
C#: Dictionaryを使って部分問題の結果を保存し、再帰的に解を求めます。
C++: unordered_mapを使用し、部分問題をメモ化しながら再帰的に計算します。
Java: HashMapを用いて部分問題をメモ化し、再帰で解を求めます。
JavaScript: オブジェクトを使って部分問題をメモ化しつつ、再帰的に計算します。
まとめ
今日学んだ「部分問題」と「最適部分構造」の概念は、効率的なアルゴリズムの設計に欠かせない要素です。これらを理解することで、動的計画法や分割統治法のような手法を活用できるようになります。
次回は「動的計画法」の具体的な応用例を学びましょう。
コメント
コメント一覧 （1件）
[…] 1-3-2. 部分問題と最適部分構造の概念 […]