【C言語】第8章第8回：再帰とバックトラッキング

再帰とバックトラッキングは、複雑な問題を簡潔に解くための強力な手法です。本記事では、これらの基本概念から実践的なプログラム例まで詳しく解説します。

0. 記事の概要

この記事を読むメリット

• アルゴリズムの基礎理解：再帰とバックトラッキングを学ぶことで、複雑なアルゴリズムへの理解が深まります。
• 問題解決能力の向上：再帰的なアプローチで複雑な問題を分割して解けるようになります。
• 効率的な設計：バックトラッキングを利用して効率的に解を探索する方法が学べます。

この記事で学べること

• 再帰アルゴリズムの基本構造と応用例
• バックトラッキングの仕組みとその応用
• 効率的なアルゴリズム設計のポイント

活用のイメージ

再帰とバックトラッキングは、迷路探索、パズル解法、組み合わせ最適化などの幅広い分野で利用されています。

1. 再帰の基本

1.1 再帰とは？

再帰（Recursion）は、関数が自分自身を呼び出す手法です。このアプローチを使用することで、複雑な問題を簡潔なコードで表現できます。

例：階乗の計算を再帰的に行う。

1.2 再帰の構造

• 基本ケース（Base Case）：再帰を終了する条件
• 再帰ケース（Recursive Case）：関数が自分自身を呼び出すロジック

1.3 階乗の計算（例）

#include <stdio.h>

// 階乗の計算
int factorial(int n) {
    if (n == 0) {
        return 1; // 基本ケース
    }
    return n * factorial(n - 1); // 再帰ケース
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

動作解説

1. 基本ケース：n == 0で1を返し、再帰が終了します。
2. 再帰ケース：関数が自分自身を呼び出し、問題を分割します。
3. 結果の組み立て：各計算結果を積み上げて最終結果を出力します。

2. バックトラッキングの基本

2.1 バックトラッキングとは？

バックトラッキング（Backtracking）は、試行錯誤を繰り返しながら解を探索する手法です。解が不適切と判断された場合に、直前の状態に戻ってやり直します。

2.2 バックトラッキングの構造

• 探索：可能なすべての選択肢を試す
• 制約条件：不適切な選択肢を排除する
• バックトラック：誤った道筋を元に戻す

2.3 ナップザック問題（例）

#include <stdio.h>

// 最大値を返す関数
int knapsack(int weights[], int values[], int n, int maxWeight) {
    if (n == 0 || maxWeight == 0) {
        return 0; // 基本ケース
    }

    if (weights[n - 1] > maxWeight) {
        return knapsack(weights, values, n - 1, maxWeight);
    }

    int include = values[n - 1] + knapsack(weights, values, n - 1, maxWeight - weights[n - 1]);
    int exclude = knapsack(weights, values, n - 1, maxWeight);

    return include > exclude ? include : exclude;
}

int main() {
    int weights[] = {1, 2, 3};
    int values[] = {6, 10, 12};
    int maxWeight = 5;
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("Maximum value: %d\n", knapsack(weights, values, n, maxWeight));
    return 0;
}

動作解説

1. 基本ケース：アイテムがないか、容量が0になったら0を返します。
2. 再帰ケース：アイテムを選ぶ場合と選ばない場合の最大値を比較します。
3. 結果の組み立て：最適な選択肢を積み上げて最大値を計算します。

3. 練習問題

以下の課題に挑戦して、再帰とバックトラッキングの理解を深めましょう。

1. 再帰を使ってフィボナッチ数列を生成するプログラムを作成してください。
2. 8クイーン問題をバックトラッキングで解くプログラムを実装してください。
3. 迷路探索問題を解くプログラムを作成してください。

4. 練習問題の解答と解説

問2の解答

#include <stdio.h>

#define N 8

int board[N][N];

int isSafe(int row, int col) {
    for (int i = 0; i < col; i++) {
        if (board[row][i]) return 0;
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) return 0;
    }
    for (int i = row, j = col; i < N && j >= 0; i++, j--) {
        if (board[i][j]) return 0;
    }
    return 1;
}

int solve(int col) {
    if (col >= N) return 1;

    for (int i = 0; i < N; i++) {
        if (isSafe(i, col)) {
            board[i][col] = 1;
            if (solve(col + 1)) return 1;
            board[i][col] = 0;
        }
    }
    return 0;
}

int main() {
    if (solve(0)) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
    } else {
        printf("Solution does not exist");
    }
    return 0;
}

このプログラムでは、8クイーン問題をバックトラッキングで解決し、安全な配置を探索します。

5. まとめ

本記事では、再帰とバックトラッキングの基本的な構造とその応用について学びました。次回は、さらに高度なアルゴリズムについて掘り下げます。