BFS（幅優先探索）の簡単な説明
幅優先探索（BFS：Breadth-First Search）は、グラフやツリーなどのデータ構造を探索するためのアルゴリズムの一つです。BFSは、開始ノードから近いノードから順に、同じレベルのノードをすべて探索してから次のレベルに進むという方法で動作します。BFSは通常、キュー（FIFO）を使用して実装されます。
BFSの主な特長は以下の通りです：
- 最短経路探索：BFSは無加重グラフでの最短経路探索に適しています。最初に到達した解が最短であることが保証されます。
- レベル順探索：BFSはノードをレベル順に探索するため、ノード間の距離を簡単に把握できます。
問題の解法の説明
以下は、与えられたシングルリンクリストを0を基準に値をマージする問題の解法をBFSを用いて説明したものです。
問題説明
- 入力：異なる額面の硬貨を表す配列 coins と総額 amount
- 出力：指定された金額を作るために必要な最小の硬貨の数。もしその金額を作ることができない場合は -1 を返す。
制約条件
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
改善されたBFSコード（Setを使用した訪問チェック）
import java.util.*;
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) return 0;
// 訪問チェックを行うためのセット
Set<Integer> visited = new HashSet<>();
Queue<Node> que = new LinkedList<>();
// キューの初期化
for(int coin : coins){
if (coin <= amount) {
que.add(new Node(coin, 1));
visited.add(coin);
}
}
int res = Integer.MAX_VALUE;
while(!que.isEmpty()){
Node current = que.poll();
if(current.sum == amount){
res = Math.min(res, current.count);
break;
}
for(int coin : coins){
int newSum = current.sum + coin;
if(newSum > amount) continue;
if (!visited.contains(newSum)) {
que.add(new Node(newSum, current.count + 1));
visited.add(newSum);
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
class Node {
public int sum;
public int count;
Node(int sum, int count){
this.sum = sum;
this.count = count;
}
}
コードの説明
-
入力検証：
- amountが0であれば、硬貨は必要ないため0を返します。
-
訪問チェックのためのSetの初期化：
- Set visited = new HashSet<>();を使用して、各金額に対して訪問したかどうかを追跡します。
-
キューの初期化：
- 各硬貨を使用して初期キューを設定します。金額が amount 以下の硬貨のみをキューに追加し、訪問チェックセットに追加します。
-
BFS探索：
- キューが空になるまでノードを探索します。
- 現在のノードの金額が目標金額と等しければ、結果を更新し探索を終了します。
- 各硬貨を使用して新しい金額を計算し、訪問していない金額であればキューに追加し、訪問チェックセットに追加します。
-
結果の返却：
- 結果が初期値のままであれば、目標金額を作成できないため -1 を返します。それ以外の場合は結果を返します。
BFSアプローチの利点と注意点
利点：
- 最短経路探索：BFSは最短経路を見つけるのに適しています。問題の解が最短であることを保証します。
- 全ての可能性を探索：全ての可能な経路を一度に広げて探索するため、最適解を見つけやすい。
注意点：
- メモリ使用量：BFSは多くのノードを一時的にメモリに保持する必要があるため、大きな探索空間ではメモリ使用量が増加します。
- タイムアウト：探索空間が大きい場合、タイムアウトが発生する可能性があります。適切な最適化が必要です。
Summary
上記のコードはSetを使用して訪問チェックを行うことで、メモリ効率を高め、探索の重複を避けています。
繰り返される値をキャッシングすることが重要だった問題でした。