アルゴリズムとデータ構造
2013年7月25日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html
NP完全問題
(386ページ)
• アルゴリズムの開発
– 第5章までは、効率のよいアルゴリズムの紹介
– 問題の大きさの2乗とか3乗くらいの計算量
• 計算量の理論
– 難しいかどうかわからない問題がたくさんある
– 問題の難しい程度を分類する
• 難しいことを証明し、無駄な努力を省く
• 効率のよいアルゴリズムを開発する
2
やさしい問題と難しい問題
(387ページ)
• 基準は、しらみつぶしが必要かどうか
– しかしながら、細かい基準を設けることも難しい…
• 問題の大きさnの多項式
– やさしい問題
• 問題の大きさnの指数関数
– 難しい問題
• 難しさを決定不能
• 難しいかどうか現状では不明(NP完全問題)
3
クラスPとNP
(389ページ)
• 決定性アルゴリズム
– 解く途中のどの段階でも手順が決まっている
• 普通のアルゴリズム
– それで解ける問題はクラスPに属する
• 非決定性アルゴリズム
– 適切な手を選べば解に至る
• 選択が正しいかどうかは神のみぞ知る
– 知る方法が無いから非決定性アルゴリズムということ
• 途中の手を適切に選択して多項式時間で解ければ
その問題はクラスNPに属する、という
4
NP困難
(NP-hard)
• クラスNPに属するどんな問題よりも
難しいか同程度に難しい問題のこと
– 問題が多項式還元可能なら、同程度に難しい
– 問題がクラスNPに属さないこともある
• NP完全問題とは、クラスNPの問題のうち
NP困難であるもの
– P=NP問題は、NP完全問題に効率のよい
アルゴリズムがあるかどうか、という問題
5
最適化問題の解法
• 指数関数時間でも枝狩りにより実用になる
– 6.1節から6.3節までの例
• 分枝限定法
– バックトラック法によるしらみつぶしを基本とする
– 最適解に至る見込みが無い場合は探索を打ち切る
• 動的計画法
– 部分的な解の状態を表の形で表す
6
0-1ナップザック問題
(396ページ)
• n個の品物があって、
それぞれ価値と重さが決まっている
– 重さは正の実数(計算機上では浮動小数点数)
• 392ページのナップザック問題と違うところ1
• 重さの総和が制約として与えられる
• 品物は選択する・しないの2とおり
• 392ページのナップザック問題と違うところ2
• 価値の総和が最大となる組み合わせを探す
• 重さあたりの価値で分枝限定法を使う
7
public class KnapsackBB { // 0-1ナップザック問題を分枝限定法で解く
private static double maxsofar;
private static boolean[] result;
private static boolean[] choice;
private static void backtrack(int i, double profit, double weight){
if(i >= (items.length-1)){
if(profit > maxsofar){
maxsofar = profit;
result = choice.clone(); // 現時点での最良の解
}
} else {
if(items[i].getWeight() <= weight){
choice[i] = true; // i番目の物を詰める
backtrack(i + 1, profit + items[i].getProfit(), weight - items[i].getWeight());
}
本来の0-1ナップザック問題
double z = 0;
double u = weight;
拡張ナップザック問題
int j;
for(j = i+1; items[j].getWeight() <= u; j++){
u -= items[j].getWeight();
z += items[j].getProfit();
}
z += u*items[j].getValue();
if((z + profit) > maxsofar){
choice[i] = false; // i番目の物は詰めない
backtrack(i+1, profit, weight);
}}}}
8
private static ItemBB[] items = {
new ItemBB("みかん", 10, 100),
new ItemBB("りんご", 98, 300),
new ItemBB("マンゴー", 398, 300),
new ItemBB("すいか", 1000, 6000),
new ItemBB("パイナップル", 398, 800),
new ItemBB("焼き芋", 100, 200),
new ItemBB("いちご", 200, 300),
new ItemBB("ドリアン", 980, 2000),
new ItemBB("パパイヤ", 298, 400),
new ItemBB("メロン", 1000, 800),
new ItemBB("びわ", 10, 50),
new ItemBB("すもも", 20, 60),
new ItemBB("文旦", 100, 300),
new ItemBB("バナナ", 20, 100),
new ItemBB("とうもろこし", 100, 250),
new ItemBB("パッションフルーツ", 300, 90),
new ItemBB("ぶどう", 333, 600),
new ItemBB("梨", 198, 300),
new ItemBB("カニステル", 300, 100),
new ItemBB("チェリモヤ", 1000, 200),
new ItemBB("番兵", 0, Double.POSITIVE_INFINITY) };
[[email protected] bin]$ java complex.KnapsackBB 5000
チェリモヤ, 1000.0, 200.0
パッションフルーツ, 300.0, 90.0
カニステル, 300.0, 100.0
マンゴー, 398.0, 300.0
メロン, 1000.0, 800.0
パパイヤ, args)
298.0,{400.0
public static void main(String[]
いちご, 200.0, 300.0
double limit;
ぶどう, 333.0, 600.0
try {
limit = Double.parseDouble(args[0]);
焼き芋, 100.0, 200.0
}catch(Exception e){
ドリアン, 980.0, 2000.0
limit = 9000;
重量の上限: 5000.0
個数: 10
重量の合計: 4990.0
}
Arrays.sort(items); [[email protected] bin]$ java complex.KnapsackBB 4900
チェリモヤ, 1000.0, 200.0
maxsofar = Double.NEGATIVE_INFINITY;
パッションフルーツ, 300.0, 90.0
choice = new boolean[items.length];
カニステル, 300.0, 100.0
backtrack(0, 0, limit);
マンゴー, 398.0, 300.0
double p = 0, w = 0;
int n = 0;
メロン, 1000.0, 800.0
for(int i = 0; i < items.length-1; i++){
if(result[i]){
パパイヤ, 298.0, 400.0
p += items[i].getProfit();
いちご, 200.0, 300.0
w += items[i].getWeight();
n++;
ぶどう, 333.0, 600.0
System.out.println(items[i]);
}
ドリアン, 980.0, 2000.0
}
System.out.print("重量の上限: " + limit);
すもも, 20.0, 60.0
System.out.print("\t個数: " + n);
びわ, 10.0, 50.0
System.out.print("\t重量の合計: " + w);
System.out.println("\t価格の合計: " + p);
重量の上限: 4900.0
個数: 11
重量の合計: 4900.0
}
価格の合計: 4909.0
9
価格の合計: 4839.0
変形ナップザック問題
• n個の品物があって、
それぞれ価値と重さが決まっている
– 重さは正の整数である
• 392ページのナップザック問題と違うところ
• 重さの総和が制約として与えられる
• 品物はいくら選択してもよい
• 価値の総和が最大となる組み合わせを探す
10
public class KnapsackDP { // ナップザック問題を動的計画法で解く
private static void solve(ItemDP[] items, int weight, int[] result){
double[] gain = new double[weight+1];
int[] choice = new int[weight+1];
Arrays.fill(choice, -1);
j-1までの品物を使って
for(int j = 0; j < items.length; j++){
for(int i = 1; i <= weight; i++){
重さの限界ごとに最適値を求める
int k = i - items[j].getWeight();
if(k >= 0){
if((gain[k] + items[j].getProfit()) > gain[i]){
gain[i] = gain[k] + items[j].getProfit();
choice[i] = j;
重さの限界値のときの価値
}
}
}
重さの限界直前に選んだ品物
}
int k;
for(int i = weight; choice[i] >= 0; i -= items[k].getWeight()){
k = choice[i];
result[k]++;
}
}
}
11
[[email protected] bin]$ java complex.KnapsackDP 1200
とよのか, 297.0, 298, 4
重量の上限: 1200
個数: 4 重量の合計: 1192
[[email protected] bin]$ java complex.KnapsackDP 1190
とよのか, 297.0, 298, 3
288.0,
1
public static あすかルビー,
void main(String[]
args)278,
{
個数: 4 重量の合計: 1172
int limit; 重量の上限: 1190
try {
[[email protected] bin]$ java complex.KnapsackDP 1170
limit = Integer.parseInt(args[0]);
}catch(Exception e){
limit = 9000;
とよのか, 297.0, 298, 2
}
288.0, 278, 2
int[] resultあすかルビー,
= new int[items.length];
重量の上限:
1170
個数: 4 重量の合計: 1152
solve(items,
limit, result);
bin]$ java complex.KnapsackDP 1150
double p =[[email protected]
0;
int w = 0, nとよのか,
= 0;
297.0, 298, 1
for(int i = あすかルビー,
0; i < result.length;
i++){278, 3
288.0,
if(result[i]
> 0){
重量の上限:
1150
個数: 4 重量の合計: 1132
p += items[i].getProfit()*result[i];
[[email protected] bin]$ java complex.KnapsackDP 1130
w += items[i].getWeight()*result[i];
あすかルビー, 288.0, 278, 4
n += result[i];
重量の上限: 1130
4 重量の合計: 1112
System.out.println(items[i]
+ ",個数:
" + result[i]);
[[email protected] bin]$ java complex.KnapsackDP 1110
}
とよのか, 297.0, 298, 1
}
System.out.print("重量の上限:
" + limit);
ももいちご, 300.0, 398,
2
System.out.print("\t個数:
" + n); 個数: 3 重量の合計: 1094
重量の上限: 1110
System.out.print("\t重量の合計:
" + w);
[[email protected] bin]$ java
complex.KnapsackDP 1093
System.out.println("\t価格の合計: " + p);
とよのか, 297.0, 298, 2
}
ももいちご, 300.0, 398, 1
private static ItemDP[] items = {
new ItemDP("とよのか", 297, 298),
new ItemDP("さちのか", 280, 298),
new ItemDP("レッドパール", 295, 335),
new ItemDP("さがほのか", 283, 350),
new ItemDP("紅ほっぺ", 291, 398),
new ItemDP("あまおう", 270, 350),
new ItemDP("あすかルビー", 288, 278),
new ItemDP("ももいちご", 300, 398),
new ItemDP("にょほう", 265, 298),
new ItemDP("とちおとめ", 290, 348)
};
価格の合計: 1188.0
価格の合計: 1179.0
価格の合計: 1170.0
価格の合計: 1161.0
価格の合計: 1152.0
価格の合計: 897.0
12
近似アルゴリズム
• 最適値を求めるのではなく、
最適値に近い近似値を求める問題に変形
• 近似解法の時間計算量
– 解くことをあきらめる必要がない程度
• 少なくとも指数関数時間ではない、など
• 近似解の精度
– 最適値に対して近似値がどれくらい近いか
13
Euclid的巡回セールスマン問題
(402ページ)
• 元の問題
– グラフが与えられており、各辺に重みがつ
いている。
– このグラフの頂点を全て通り、重みの総和
が最小の経路を求める。
• 変形した問題
– グラフの各辺の重みは0以上
• 少なくとも重みの総和が減ることはない
– 任意の3頂点(A,B,C)間で d AB  d BC  d AC
• AからCへ行くのに、Bを通らないほうが良い
14
貪欲解法
1. 任意の頂点をひとつ選ぶ
2. そこから到達可能な最小の重みの辺を選ぶ
3. その辺の先の頂点から同様に次の辺を選ぶ
•
すでに通過した頂点へ至る辺を除去する
局
所
的
4. そのうち最初に選んだ頂点に戻る道ができる
1. 最小の重みの辺をグラフ全体から選ぶ
• この辺を除外する
大
2. 次に最小の重みの辺を選ぶ
域
• このときひとつの輪にならない辺も除外する 的
3. そのうちひとつながりの輪ができる
15
挿入法
• どれか1つの頂点を選ぶ
• 輪の中に、輪の外の頂点を加える
– 輪を作る各頂点から最近の頂点を選ぶ(方法1)
– 輪を作る各頂点から最遠の頂点を選ぶ(方法2)
• 大局的には、遠い点どおしを先に結ぶほうがよさそう…
16
局所探索法
• まず全頂点をどうにかして輪につなぐ
– 重さの総和の大小は気にしない
• 交差している2辺を繋ぎかえる
– 特に3本以上同時につなぎ替えるといいらしい
• つなぎかえができなくなったら終了
17
ダウンロード

PPT