最適化問題と局所探索の基本：病院配置問題の例から学ぶ

# **最適化問題と局所探索の基本：病院配置問題の例から学ぶ**

これまでにAIが知識ベースの問題（論理と推論を使って結論を導く）や確率モデル（不確実性を扱う）を用いる方法を学びました。この記事では、**最適化問題**に焦点を当て、特に**局所探索（Local Search）**アルゴリズムとその応用例をわかりやすく解説します。例として、病院の最適配置問題を扱います。

---

## **1. 最適化問題とは？**
最適化問題とは、多くの選択肢の中から**最適な選択肢**を見つけることを目的とした問題のことです。例えば、ゲームAIでは、最良の手を選ぶのが最適化問題の一例です。

一般的に最適化問題は次のように分類されます：
- **最大化問題**: 目的関数（Objective Function）の値を可能な限り最大化する。
- **最小化問題**: コスト関数（Cost Function）の値を可能な限り最小化する。

### **例：病院配置問題**
- **目標**: 地図上の病院を最適に配置し、すべての家から最も近い病院までの距離の合計（コスト）を最小化する。
- **制約**: 病院を配置できる場所は格子状の地図内で決まっている。

---

## **2. 局所探索とは？**
局所探索アルゴリズムは、現在の状態（配置）を基に、隣接する状態（配置）を探索し、解を改善していく手法です。

### **従来の探索アルゴリズムとの違い**
- **幅優先探索やA*探索**: 複数の経路を同時に追跡してゴールを目指す。
- **局所探索**: 現在の状態を保持し、1つの隣接状態を基に探索を進める。

### **局所探索の特徴**
- **経路ではなく解そのものに焦点を当てる**  
  解（病院配置）が最適であることが重要であり、経路は考慮しない。
  
- **初期状態から開始し、逐次的に改善する**  
  初期状態をランダムに生成し、そこから改善を図る。

---

## **3. 病院配置問題を局所探索で解く**

### **問題設定**
- 格子状の地図に家と病院を配置。
- コスト関数: 各家から最も近い病院までの距離の合計。
- **目標**: コストを最小化する病院の配置を見つける。

### **隣接状態の定義**
隣接状態は、病院の1つを上下左右に1マス移動した配置。

---

## **4. ヒルクライミングアルゴリズム**
ヒルクライミング（Hill Climbing）は、最適化問題を解くための単純な局所探索アルゴリズムです。

### **アルゴリズムの流れ**
1. **初期状態を設定**: 病院の位置をランダムに決定。
2. **隣接状態を生成**: 現在の配置から可能な隣接状態を全て列挙。
3. **最良の隣接状態を選択**: コストを最小化する隣接状態を選ぶ。
4. **状態の更新**: 最良の隣接状態に移動。
5. **停止条件**: 現在の状態がすべての隣接状態よりも良い場合、終了。

### **擬似コード**
```python
def hill_climb(problem):
    current = problem.initial_state()
    while True:
        neighbors = problem.get_neighbors(current)
        best_neighbor = min(neighbors, key=lambda state: problem.cost(state))
        if problem.cost(best_neighbor) >= problem.cost(current):
            return current
        current = best_neighbor
```

---

## **5. ヒルクライミングの実行例**
### **初期状態**
初期配置では、家と病院の位置がランダムに決定されます。

- 病院の初期配置: コスト72

### **状態の更新**
以下のようにコストを削減します：
1. 病院1を左に移動 → コスト69
2. 病院2を下に移動 → コスト63
3. 病院1をさらに左に移動 → コスト53

### **最終状態**
最終配置では、病院の位置が最適化され、コストが53に削減されました。

---

## **6. ヒルクライミングの限界**

### **局所最適解に陥る可能性**
- **局所最適解**: 隣接状態の中で最良だが、全体で見ると最適解ではない。
- **大域的最適解**: 全ての可能な解の中で最良の解。

ヒルクライミングは、局所最適解に陥りやすいという問題があります。

---

## **7. 改良版アルゴリズム**
ヒルクライミングの弱点を補うための手法があります。

### **改良版**
- **確率的ヒルクライミング**: 最良ではなく、ランダムに隣接状態を選ぶ。
- **ランダム再スタート**: 複数回ランダムに初期状態を生成して試行。
- **ビーム探索**: 複数の状態を同時に追跡し、最良のk個を選ぶ。

---

## **8. 実装例: 病院配置問題**

### **Pythonコード**
以下のコードは、病院配置問題をヒルクライミングで解く実装例です。

```python
import random

class HospitalProblem:
    def __init__(self, width, height, num_hospitals, num_houses):
        self.width = width
        self.height = height
        self.hospitals = []
        self.houses = [(random.randint(0, width - 1), random.randint(0, height - 1)) for _ in range(num_houses)]

    def initial_state(self):
        return [(random.randint(0, self.width - 1), random.randint(0, self.height - 1)) for _ in range(len(self.houses))]

    def get_neighbors(self, state):
        neighbors = []
        for i, (x, y) in enumerate(state):
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_state = state[:]
                new_state[i] = (x + dx, y + dy)
                neighbors.append(new_state)
        return neighbors

    def cost(self, state):
        total_distance = 0
        for house in self.houses:
            total_distance += min(abs(house[0] - hx) + abs(house[1] - hy) for hx, hy in state)
        return total_distance
```

---

## **9. まとめ**
局所探索は、最適化問題を効率的に解くための有力なアプローチです。ヒルクライミングはその基本ですが、改良手法を活用することで、より良い結果を得られます。この記事の内容を基に、自分の問題に適した最適化アルゴリズムを設計してみてください。