バックトラッキング法による組み合わせ最適化問題の解法 - Nクイーン問題と荷積み問題を中心に

1. バックトラッキング法による8クイーン問題の解法

1.1 アルゴリズムの概要

8クイーン問題は、8×8のチェスボードに8個のクイーンを配置し、どのクイーンも互いに攻撃できないようにする組み合わせ最適化問題です。バックトラッキング法は、体系的な探索と枝刈りを組み合わせることで、効率的に全ての解を求めることができます。

本手法の核心は、再帰的な深さ優先探索を行いながら、制約条件に違反する配置を早期に排除する点にあります。各行に一つずつクイーンを配置していく過程で、列や斜め方向の衝突をチェックし、矛盾が発生した時点でその探索パスを打ち切ります。

1.2 問題設定

8×8の盤面に8個のクイーンを配置する。ただし、以下の条件を満たす必要がある：

同一行に複数のクイーンが存在しない
同一列に複数のクイーンが存在しない
同一斜め線上に複数のクイーンが存在しない

全ての可能な配置パターンを列挙せよ。

1.3 実装コード

#include <iostream>
#include <cmath>
#include <vector>

static int solutionCounter = 0;

bool isValidPosition(int currentRow, int currentCol, int* boardState) {
    for (int prevRow = 0; prevRow < currentRow; ++prevRow) {
        int prevCol = boardState[prevRow];
        if (prevCol == currentCol || 
            std::abs(prevCol - currentCol) == std::abs(prevRow - currentRow)) {
            return false;
        }
    }
    return true;
}

void solveQueens(int currentRow, int boardSize, int* boardState) {
    for (int col = 0; col < boardSize; ++col) {
        if (isValidPosition(currentRow, col, boardState)) {
            boardState[currentRow] = col;
            
            if (currentRow == boardSize - 1) {
                ++solutionCounter;
                std::cout << "(" << solutionCounter << ") ";
                for (int i = 0; i < boardSize; ++i) {
                    std::cout << boardState[i] << " ";
                }
                std::cout << std::endl;
            } else {
                solveQueens(currentRow + 1, boardSize, boardState);
            }
        }
    }
}

void executeQueensSolver(int boardSize) {
    int* boardState = new int[boardSize];
    for (int i = 0; i < boardSize; ++i) {
        boardState[i] = -1;
    }
    solveQueens(0, boardSize, boardState);
    delete[] boardState;
}

int main() {
    executeQueensSolver(8);
    return 0;
}

2. バックトラッキング法による荷積み問題の解法

2.1 問題の定義

2艘の貨物船（積載容量c₁, c₂）とn個のコンテナ（重量w₁, w₂, ..., wₙ）が与えられる。全コンテナの重量の合計はc₁ + c₂以下である。各コンテナをどちらかの船に積載する配置を求め、可能かどうかを判定する問題。

本問題は、第一船に積載するコンテナの組み合わせを最適化することで、第二船への積載可能性を自動的に判定できる特徴を持つ。

2.2 最適化アプローチ

バックトラッキング法を適用する際の重要な戦略：

制約条件の適用: 第一船の積載重量がc₁を超えないことを常に確認
枝刈り関数: 残りのコンテナを全て積載しても既知の最良解を超えられない場合、探索を中止
深さ優先探索: 各コンテナについて「積載する/しない」の二分岐を再帰的に探索

2.3 実装コード

#include <iostream>
#include <iomanip>

template <typename WeightType>
class CargoOptimizer {
private:
    int containerCount;
    int* loadPlan;
    int* optimalPlan;
    WeightType capacityShip1;
    WeightType capacityShip2;
    WeightType* containerWeights;
    WeightType totalWeight;
    WeightType currentWeight;
    WeightType maxWeight;
    WeightType remainingWeight;

public:
    CargoOptimizer(WeightType* weights, int count, WeightType cap1, WeightType cap2) 
        : containerCount(count), capacityShip1(cap1), capacityShip2(cap2) {
        
        maxWeight = 0;
        currentWeight = 0;
        containerWeights = new WeightType[count + 1];
        loadPlan = new int[count + 1];
        optimalPlan = new int[count + 1];
        
        totalWeight = 0;
        for (int i = 1; i <= count; ++i) {
            containerWeights[i] = weights[i];
            totalWeight += weights[i];
        }
        remainingWeight = totalWeight;
    }

    ~CargoOptimizer() {
        delete[] containerWeights;
        delete[] loadPlan;
        delete[] optimalPlan;
    }

    void optimize(int index);
    void displayResult();
};

template <typename WeightType>
void CargoOptimizer<WeightType>::optimize(int index) {
    if (index > containerCount) {
        if (currentWeight > maxWeight) {
            for (int j = 1; j <= containerCount; ++j) {
                optimalPlan[j] = loadPlan[j];
            }
            maxWeight = currentWeight;
        }
        return;
    }

    remainingWeight -= containerWeights[index];
    
    // 左部分木の探索（コンテナを積載）
    if (currentWeight + containerWeights[index] <= capacityShip1) {
        loadPlan[index] = 1;
        currentWeight += containerWeights[index];
        optimize(index + 1);
        currentWeight -= containerWeights[index];
    }
    
    // 右部分木の探索（コンテナを積載しない）
    if (currentWeight + remainingWeight > maxWeight) {
        loadPlan[index] = 0;
        optimize(index + 1);
    }
    
    remainingWeight += containerWeights[index];
}

template <typename WeightType>
void CargoOptimizer<WeightType>::displayResult() {
    WeightType ship1Load = 0;
    for (int i = 1; i <= containerCount; ++i) {
        if (optimalPlan[i] == 1) {
            ship1Load += containerWeights[i];
        }
    }
    
    WeightType ship2Load = totalWeight - ship1Load;
    
    if (ship2Load > capacityShip2) {
        std::cout << "実行可能な積載方案が存在しません" << std::endl;
        return;
    }

    std::cout << "第一船積載計画: (";
    for (int i = 1; i < containerCount; ++i) {
        std::cout << optimalPlan[i] << ",";
    }
    std::cout << optimalPlan[containerCount] << ")" << std::endl;

    std::cout << "第二船積載計画: (";
    for (int i = 1; i < containerCount; ++i) {
        std::cout << !optimalPlan[i] << ",";
    }
    std::cout << !optimalPlan[containerCount] << ")" << std::endl;

    std::cout << "\n積載詳細:" << std::endl;
    std::cout << "第一船（容量: " << capacityShip1 << "）:" << std::endl;
    for (int i = 1; i <= containerCount; ++i) {
        if (optimalPlan[i] == 1) {
            std::cout << "  コンテナ" << i << ": " << std::setw(2) << containerWeights[i] << std::endl;
        }
    }
    std::cout << "総重量: " << ship1Load;
    if (capacityShip1 - ship1Load == 0) {
        std::cout << " （満載）" << std::endl;
    } else {
        std::cout << " （残り: " << capacityShip1 - ship1Load << ")" << std::endl;
    }

    std::cout << "第二船（容量: " << capacityShip2 << "）:" << std::endl;
    for (int i = 1; i <= containerCount; ++i) {
        if (!optimalPlan[i]) {
            std::cout << "  コンテナ" << i << ": " << std::setw(2) << containerWeights[i] << std::endl;
        }
    }
    std::cout << "総重量: " << ship2Load;
    if (capacityShip2 - ship2Load == 0) {
        std::cout << " （満載）" << std::endl;
    } else {
        std::cout << " （残り: " << capacityShip2 - ship2Load << ")" << std::endl;
    }
}

int main() {
    int testCases[3][6] = {
        {0, 22, 35, 24, 19, 4},
        {0, 22, 35, 24, 15, 4},
        {0, 22, 35, 24, 15, 3}
    };
    
    for (int i = 0; i < 3; ++i) {
        std::cout << "=== テストケース " << i + 1 << " ===" << std::endl;
        CargoOptimizer<int> optimizer(testCases[i], 5, 60, 40);
        optimizer.optimize(1);
        optimizer.displayResult();
        std::cout << std::endl;
    }
    
    return 0;
}

3. Nクイーン問題における独立解の抽出

3.1 問題の背景

8クイーン問題には92通りの基本解があるが、これらの多くは回転や反転による変換で相互に生成可能。本質的に異なる独立解は12通りのみである。本節では、全解から対称性を考慮して独立解を抽出する方法を示す。

3.2 対称変換の種類

独立解の判定には以下7種類の幾何学的変換を適用する：

90度回転
180度回転
270度回転
上下反転
左右反転
y=x対角線に関する反転
y=-x対角線に関する反転

新しい解は、既存の独立解に対してこれらの変換を施した結果と比較し、いずれとも一致しない場合にのみ独立解として登録する。

3.3 実装コード

#include <iostream>
#include <cmath>
#include <iomanip>

class QueenSolver {
private:
    int boardSize;
    int* currentBoard;
    int** uniqueSolutions;
    int* transformedBoard;
    int uniqueCount;
    
    bool isValidPlacement(int row, int col);
    bool matchesExisting(int solutionIndex);
    bool isUniqueSolution(int newIndex);
    void searchSolutions(int currentRow);
    void printSolution(const int* board, const char* label);

public:
    QueenSolver(int n);
    ~QueenSolver();
    void solve();
    void displayUniqueSolutions();
};

QueenSolver::QueenSolver(int n) : boardSize(n), uniqueCount(0) {
    currentBoard = new int[boardSize];
    transformedBoard = new int[boardSize];
    uniqueSolutions = new int*[20];
    for (int i = 0; i < 20; ++i) {
        uniqueSolutions[i] = new int[boardSize];
    }
}

QueenSolver::~QueenSolver() {
    delete[] currentBoard;
    delete[] transformedBoard;
    for (int i = 0; i < 20; ++i) {
        delete[] uniqueSolutions[i];
    }
    delete[] uniqueSolutions;
}

bool QueenSolver::isValidPlacement(int row, int col) {
    for (int prevRow = 0; prevRow < row; ++prevRow) {
        int prevCol = currentBoard[prevRow];
        if (prevCol == col || std::abs(prevCol - col) == std::abs(prevRow - row)) {
            return false;
        }
    }
    return true;
}

void QueenSolver::searchSolutions(int currentRow) {
    for (int col = 0; col < boardSize; ++col) {
        if (isValidPlacement(currentRow, col)) {
            currentBoard[currentRow] = col;
            
            if (currentRow == boardSize - 1) {
                for (int i = 0; i < boardSize; ++i) {
                    uniqueSolutions[uniqueCount][i] = currentBoard[i];
                }
                
                if (isUniqueSolution(uniqueCount)) {
                    ++uniqueCount;
                }
            } else {
                searchSolutions(currentRow + 1);
            }
        }
    }
}

bool QueenSolver::isUniqueSolution(int newIndex) {
    // 90度回転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[uniqueSolutions[newIndex][i]] = boardSize - 1 - i;
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // 180度回転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[boardSize - 1 - i] = boardSize - 1 - uniqueSolutions[newIndex][i];
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // 270度回転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[boardSize - 1 - uniqueSolutions[newIndex][i]] = i;
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // 上下反転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[boardSize - 1 - i] = uniqueSolutions[newIndex][i];
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // 左右反転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[i] = boardSize - 1 - uniqueSolutions[newIndex][i];
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // y=x対角線反転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[uniqueSolutions[newIndex][i]] = i;
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    // y=-x対角線反転
    for (int i = 0; i < boardSize; ++i) {
        transformedBoard[boardSize - 1 - uniqueSolutions[newIndex][i]] = boardSize - 1 - i;
    }
    for (int k = 0; k < newIndex; ++k) {
        if (matchesExisting(k)) return false;
    }
    
    return true;
}

bool QueenSolver::matchesExisting(int solutionIndex) {
    for (int i = 0; i < boardSize; ++i) {
        if (transformedBoard[i] != uniqueSolutions[solutionIndex][i]) {
            return false;
        }
    }
    return true;
}

void QueenSolver::solve() {
    searchSolutions(0);
}

void QueenSolver::displayUniqueSolutions() {
    std::cout << boardSize << "-クイーン問題の独立解（" << uniqueCount << "個）:" << std::endl;
    for (int i = 0; i < uniqueCount; ++i) {
        std::cout << std::setw(3) << i + 1 << " (";
        for (int j = 0; j < boardSize - 1; ++j) {
            std::cout << uniqueSolutions[i][j] << ",";
        }
        std::cout << uniqueSolutions[i][boardSize - 1] << ")" << std::endl;
    }
}

int main() {
    QueenSolver solver(8);
    solver.solve();
    solver.displayUniqueSolutions();
    return 0;
}

タグ: バックトラッキング法 Nクイーン問題荷積み問題組み合わせ最適化再帰アルゴリズム

7月4日 17:42 投稿

異端開発室