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

Slides:



Advertisements
Similar presentations
山元進.  for 文  while 文  do ~ while 文  文のネスト  break 文  continue 文.
Advertisements

授業展開#12 コンピュータの扱いにくい問 題. 扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、
ACM/ICPC と アルゴリズム 「実践的プログラミング」 稲葉 一浩. 自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程1年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩ ﻯD.
アルゴリズムとデータ構造 2011年7月7日
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
動的計画法 表の作成 制約の追加 練習問題.
アルゴリズムとデータ構造 2012年6月27日
動的計画法 表の作成 制約の追加 練習問題.
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造1 2008年7月22日
コンパイラ 2011年10月17日
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
アルゴリズムとデータ構造 2012年7月26日
アルゴリズムとデータ構造1 2007年6月12日
アルゴリズムとデータ構造 2012年7月19日
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 2012年7月23日
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
9.NP完全問題とNP困難問題.
アルゴリズムとデータ構造 2011年7月14日
コンパイラ 2012年10月15日
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2013年7月18日
アルゴリズムとデータ構造 2012年7月12日
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
決定木とランダムフォレスト 和田 俊和.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2005年7月15日
第3回 アルゴリズムと計算量 2019/2/24.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造 2012年7月17日
離散数学 07. 木 五島.
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
アルゴリズムとデータ構造 2011年7月21日
オブジェクト・プログラミング 第8回.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
サポートベクターマシン Support Vector Machine SVM
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2012年6月25日
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
アルゴリズムとデータ構造 2010年6月17日
参考:大きい要素の処理.
13.近似アルゴリズム.
計算機プログラミングI 第2回 2002年10月17日(木) 履習登録 複習 ライブラリの利用 (2.6-7) 式・値・代入 (2.6-8)
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

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

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

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

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

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

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

本来の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ナップザック問題 拡張ナップザック問題

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); [sakai@star 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 パパイヤ, 298.0, 400.0 いちご, 200.0, 300.0 ぶどう, 333.0, 600.0 焼き芋, 100.0, 200.0 ドリアン, 980.0, 2000.0 重量の上限: 5000.0 個数: 10 重量の合計: 4990.0 価格の合計: 4909.0 [sakai@star bin]$ java complex.KnapsackBB 4900 すもも, 20.0, 60.0 びわ, 10.0, 50.0 重量の上限: 4900.0 個数: 11 重量の合計: 4900.0 価格の合計: 4839.0

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

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

[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); [sakai@star bin]$ java complex.KnapsackDP 1200 とよのか, 297.0, 298, 4 重量の上限: 1200 個数: 4 重量の合計: 1192 価格の合計: 1188.0 [sakai@star bin]$ java complex.KnapsackDP 1190 とよのか, 297.0, 298, 3 あすかルビー, 288.0, 278, 1 重量の上限: 1190 個数: 4 重量の合計: 1172 価格の合計: 1179.0 [sakai@star bin]$ java complex.KnapsackDP 1170 とよのか, 297.0, 298, 2 あすかルビー, 288.0, 278, 2 重量の上限: 1170 個数: 4 重量の合計: 1152 価格の合計: 1170.0 [sakai@star bin]$ java complex.KnapsackDP 1150 とよのか, 297.0, 298, 1 あすかルビー, 288.0, 278, 3 重量の上限: 1150 個数: 4 重量の合計: 1132 価格の合計: 1161.0 [sakai@star bin]$ java complex.KnapsackDP 1130 あすかルビー, 288.0, 278, 4 重量の上限: 1130 個数: 4 重量の合計: 1112 価格の合計: 1152.0 [sakai@star bin]$ java complex.KnapsackDP 1110 ももいちご, 300.0, 398, 2 重量の上限: 1110 個数: 3 重量の合計: 1094 価格の合計: 897.0 [sakai@star bin]$ java complex.KnapsackDP 1093 ももいちご, 300.0, 398, 1 重量の上限: 1093 個数: 3 重量の合計: 994 価格の合計: 894.0 [sakai@star bin]$ java complex.KnapsackDP 990 重量の上限: 990 個数: 3 重量の合計: 894 価格の合計: 891.0 [sakai@star bin]$ java complex.KnapsackDP 893 重量の上限: 893 個数: 3 重量の合計: 874 価格の合計: 882.0 [sakai@star bin]$ java complex.KnapsackDP 873 重量の上限: 873 個数: 3 重量の合計: 854 価格の合計: 873.0 [sakai@star bin]$ java complex.KnapsackDP 853 重量の上限: 853 個数: 3 重量の合計: 834 価格の合計: 864.0 [sakai@star bin]$ java complex.KnapsackDP 833 重量の上限: 833 個数: 2 重量の合計: 796 価格の合計: 600.0

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

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

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

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

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