Presentation is loading. Please wait.

Presentation is loading. Please wait.

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月21日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html.

Similar presentations


Presentation on theme: "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月21日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html."— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2011年7月21日

2 NP完全問題 (386ページ) アルゴリズムの開発 計算量の理論 第5章までは、効率のよいアルゴリズムの紹介
問題の大きさの2乗とか3乗くらいの計算量 計算量の理論 難しいかどうかわからない問題がたくさんある 問題の難しい程度を分類する 難しいことを証明し、無駄な努力を省く 効率のよいアルゴリズムを開発する

3 やさしい問題と難しい問題 (387ページ) 基準は、しらみつぶしが必要かどうか 問題の大きさnの多項式 問題の大きさnの指数関数
しかしながら、細かい基準を設けることも難しい… 問題の大きさnの多項式 やさしい問題 問題の大きさnの指数関数 難しい問題 難しさを決定不能 難しいかどうか現状では不明(NP完全問題)

4 クラスPとNP (389ページ) 決定性アルゴリズム 非決定性アルゴリズム 解く途中のどの段階でも手順が決まっている
普通のアルゴリズム それで解ける問題はクラスPに属する 非決定性アルゴリズム 適切な手を選べば解に至る 選択が正しいかどうかは神のみぞ知る 知る方法が無いから非決定性アルゴリズムということ 途中の手を適切に選択して多項式時間で解ければ その問題はクラスNPに属する、という

5 NP困難 (NP-hard) クラスNPに属するどんな問題よりも 難しいか同程度に難しい問題のこと
問題が多項式還元可能なら、同程度に難しい 問題がクラスNPに属さないこともある NP完全問題とは、クラスNPの問題のうち NP困難であるもの P=NP問題は、NP完全問題に効率のよい アルゴリズムがあるかどうか、という問題

6 最適化問題の解法 指数関数時間でも枝狩りにより実用になる 分枝限定法 動的計画法 6.1節から6.3節までの例
バックトラック法によるしらみつぶしを基本とする 最適解に至る見込みが無い場合は探索を打ち切る 動的計画法 部分的な解の状態を表の形で表す

7 0-1ナップザック問題 (396ページ) n個の品物があって、 それぞれ価値と重さが決まっている 重さの総和が制約として与えられる
重さは正の実数(計算機上では浮動小数点数) 392ページのナップザック問題と違うところ1 重さの総和が制約として与えられる 品物は選択する・しないの2とおり 392ページのナップザック問題と違うところ2 価値の総和が最大となる組み合わせを探す 重さあたりの価値で分枝限定法を使う

8 本来の0-1ナップザック問題 拡張ナップザック問題
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()); 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); }}}} 本来の0-1ナップザック問題 拡張ナップザック問題

9 public static void main(String[] args) { double limit;
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) }; public static void main(String[] args) { double limit; try { limit = Double.parseDouble(args[0]); }catch(Exception e){ limit = 9000; } Arrays.sort(items); maxsofar = Double.NEGATIVE_INFINITY; choice = new boolean[items.length]; backtrack(0, 0, limit); double p = 0, w = 0; int n = 0; for(int i = 0; i < items.length-1; i++){ if(result[i]){ p += items[i].getProfit(); w += items[i].getWeight(); n++; System.out.println(items[i]); System.out.print("重量の上限: " + limit); System.out.print("\t個数: " + n); System.out.print("\t重量の合計: " + w); System.out.println("\t価格の合計: " + p); bin]$ java complex.KnapsackBB 5000 チェリモヤ, , 200.0 パッションフルーツ, 300.0, 90.0 カニステル, 300.0, 100.0 マンゴー, 398.0, 300.0 メロン, , 800.0 パパイヤ, 298.0, 400.0 いちご, 200.0, 300.0 ぶどう, 333.0, 600.0 焼き芋, 100.0, 200.0 ドリアン, 980.0, 重量の上限: 個数: 重量の合計: 価格の合計: bin]$ java complex.KnapsackBB 4900 すもも, 20.0, 60.0 びわ, 10.0, 50.0 重量の上限: 個数: 重量の合計: 価格の合計:

10 変形ナップザック問題 n個の品物があって、 それぞれ価値と重さが決まっている 重さの総和が制約として与えられる 品物はいくら選択してもよい
重さは正の整数である 392ページのナップザック問題と違うところ 重さの総和が制約として与えられる 品物はいくら選択してもよい 価値の総和が最大となる組み合わせを探す

11 j-1までの品物を使って 重さの限界ごとに最適値を求める 重さの限界値のときの価値 重さの限界直前に選んだ品物
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); 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]++; j-1までの品物を使って 重さの限界ごとに最適値を求める 重さの限界値のときの価値 重さの限界直前に選んだ品物

12 [sakai@star bin]$ java complex.KnapsackDP 1200 とよのか, 297.0, 298, 4
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) }; public static void main(String[] args) { int limit; try { limit = Integer.parseInt(args[0]); }catch(Exception e){ limit = 9000; } int[] result = new int[items.length]; solve(items, limit, result); double p = 0; int w = 0, n = 0; for(int i = 0; i < result.length; i++){ if(result[i] > 0){ p += items[i].getProfit()*result[i]; w += items[i].getWeight()*result[i]; n += result[i]; System.out.println(items[i] + ", " + result[i]); System.out.print("重量の上限: " + limit); System.out.print("\t個数: " + n); System.out.print("\t重量の合計: " + w); System.out.println("\t価格の合計: " + p); bin]$ java complex.KnapsackDP 1200 とよのか, 297.0, 298, 4 重量の上限: 個数: 4 重量の合計: 価格の合計: bin]$ java complex.KnapsackDP 1190 とよのか, 297.0, 298, 3 あすかルビー, 288.0, 278, 1 重量の上限: 個数: 4 重量の合計: 価格の合計: bin]$ java complex.KnapsackDP 1170 とよのか, 297.0, 298, 2 あすかルビー, 288.0, 278, 2 重量の上限: 個数: 4 重量の合計: 価格の合計: bin]$ java complex.KnapsackDP 1150 とよのか, 297.0, 298, 1 あすかルビー, 288.0, 278, 3 重量の上限: 個数: 4 重量の合計: 価格の合計: bin]$ java complex.KnapsackDP 1130 あすかルビー, 288.0, 278, 4 重量の上限: 個数: 4 重量の合計: 価格の合計: bin]$ java complex.KnapsackDP 1110 ももいちご, 300.0, 398, 2 重量の上限: 個数: 3 重量の合計: 価格の合計: 897.0 bin]$ java complex.KnapsackDP 1093 ももいちご, 300.0, 398, 1 重量の上限: 個数: 3 重量の合計: 994 価格の合計: 894.0 bin]$ java complex.KnapsackDP 990 重量の上限: 990 個数: 3 重量の合計: 価格の合計: 891.0 bin]$ java complex.KnapsackDP 893 重量の上限: 893 個数: 3 重量の合計: 価格の合計: 882.0 bin]$ java complex.KnapsackDP 873 重量の上限: 873 個数: 3 重量の合計: 価格の合計: 873.0 bin]$ java complex.KnapsackDP 853 重量の上限: 853 個数: 3 重量の合計: 価格の合計: 864.0 bin]$ java complex.KnapsackDP 833 重量の上限: 833 個数: 2 重量の合計: 価格の合計: 600.0

13 近似アルゴリズム 最適値を求めるのではなく、 最適値に近い近似値を求める問題に変形 近似解法の時間計算量 近似解の精度
解くことをあきらめる必要がない程度 少なくとも指数関数時間ではない、など 近似解の精度 最適値に対して近似値がどれくらい近いか

14 Euclid的巡回セールスマン問題 (402ページ)
元の問題 グラフが与えられており、各辺に重みがついている。 このグラフの頂点を全て通り、重みの総和が最小の経路を求める。 変形した問題 グラフの各辺の重みは0以上 少なくとも重みの総和が減ることはない 任意の3頂点(A,B,C)間で AからCへ行くのに、Bを通らないほうが良い

15 貪欲解法 局所的 大域的 任意の頂点をひとつ選ぶ そこから到達可能な最小の重みの辺を選ぶ その辺の先の頂点から同様に次の辺を選ぶ
すでに通過した頂点へ至る辺を除去する そのうち最初に選んだ頂点に戻る道ができる 局所的 最小の重みの辺をグラフ全体から選ぶ この辺を除外する 次に最小の重みの辺を選ぶ このときひとつの輪にならない辺も除外する そのうちひとつながりの輪ができる 大域的

16 挿入法 どれか1つの頂点を選ぶ 輪の中に、輪の外の頂点を加える 輪を作る各頂点から最近の頂点を選ぶ(方法1)
輪を作る各頂点から最遠の頂点を選ぶ(方法2) 大局的には、遠い点どおしを先に結ぶほうがよさそう…

17 局所探索法 まず全頂点をどうにかして輪につなぐ 交差している2辺を繋ぎかえる つなぎかえができなくなったら終了 重さの総和の大小は気にしない
特に3本以上同時につなぎ替えるといいらしい つなぎかえができなくなったら終了

18 期末試験 教室: C101 日時: 2011年7月25日16時30分~18時00分 持ち込み可 学生証必携 入室限度: 16時50分まで
退出可能: 17時00分より 持ち込み可 教科書・資料(自筆・コピー問わず)は持ち込み可 人間・パソコン・携帯電話・PHSなど持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと


Download ppt "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月21日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html."

Similar presentations


Ads by Google