untitled

アルゴリズムとデータ構造

アルゴリズムとデータ構造

アルゴリズムとデータ構造

アルゴリズムとデータ構造

2011

2011年

年

77月

月

21

21日

日

酒居敬一

酒居敬一

((

sakai.keiichi@kochi

[email protected]

tech.ac.jp

))

http://www info kochi

http://www info kochi--tech ac jp/k1sakai/Lecture/ALG/2011/index html

tech ac jp/k1sakai/Lecture/ALG/2011/index html

http://www.info.kochi

http://www.info.kochi--tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

ＮＰ完全問題

ＮＰ完全問題

（３８６ページ）

• アルゴリズムの開発

第

5章までは 効率のよいアルゴリズムの紹介

– 第5章までは、効率のよいアルゴリズムの紹介

– 問題の大きさの２乗とか３乗くらいの計算量

• 計算量の理論

– 難しいかどうかわからない問題がたくさんある

– 難しいかどうかわからない問題がたくさんある

– 問題の難しい程度を分類する

難し

とを証明し 無駄な努力を省く

• 難しいことを証明し、無駄な努力を省く

• 効率のよいアルゴリズムを開発する

2

やさしい問題と難しい問題

やさしい問題と難しい問題

（３８７ページ）

• 基準は、しらみつぶしが必要かどうか

しかしながら 細かい基準を設けることも難しい

– しかしながら、細かい基準を設けることも難しい…

• 問題の大きさｎの多項式

– やさしい問題

• 問題の大きさｎの指数関数

• 問題の大きさｎの指数関数

– 難しい問題

• 難しさを決定不能

• 難しいかどうか現状では不明（ＮＰ完全問題）

• 難しいかどうか現状では不明（ＮＰ完全問題）

3

クラスＰとＮＰ

クラスＰとＮＰ

（３８９ページ）

• 決定性アルゴリズム

解く途中のどの段階でも手順が決まっている

– 解く途中のどの段階でも手順が決まっている

• 普通のアルゴリズム

– それで解ける問題は

クラスＰ

に属する

• 非決定性アルゴリズム

非決定性アルゴリズム

– 適切な手を選べば解に至る

選択が正しいかどうかは神のみぞ知る

• 選択が正しいかどうかは神のみぞ知る

– 知る方法が無いから非決定性アルゴリズムということ

• 途中の手を適切に選択して多項式時間で解ければ

• 途中の手を適切に選択して多項式時間で解ければ

その問題は

クラスＮＰ

に属する、という

4

ＮＰ困難

ＮＰ困難

（ＮＰ

-ｈａｒｄ）

• クラスＮＰに属するどんな問題よりも

難しいか同程度に難しい問題のこと

難しいか同程度に難しい問題のこと

– 問題が多項式還元可能なら、同程度に難しい

– 問題がクラスＮＰに属さないこともある

• ＮＰ完全問題とは クラスＮＰの問題のうち

ＮＰ完全問題とは、クラスＮＰの問題のうち

ＮＰ困難であるもの

Ｐ

ＮＰ問題は ＮＰ完全問題に効率のよい

– Ｐ＝ＮＰ問題は、ＮＰ完全問題に効率のよい

アルゴリズムがあるかどうか、という問題

5

最適化問題の解法

• 指数関数時間でも枝狩りにより実用になる

６ １節から６ ３節までの例

– ６.１節から６.３節までの例

• 分枝限定法

– バックトラック法によるしらみつぶしを基本とする

– 最適解に至る見込みが無い場合は探索を打ち切る

– 最適解に至る見込みが無い場合は探索を打ち切る

• 動的計画法

– 部分的な解の状態を表の形で表す

6

０ １ナ プザ ク問題

０

-１ナップザック問題

（３９６ページ）

• ｎ個の品物があって、

それぞれ価値と重さが決まっている

それぞれ価値と重さが決まっている

– 重さは正の実数（計算機上では浮動小数点数）

• ３９２ページのナップザック問題と違うところ１

• 重さの総和が制約として与えられる

重さの総和が制約として与えられる

• 品物は選択する・しないの２とおり

３９２ペ ジのナ プザ ク問題と違うところ２

• ３９２ページのナップザック問題と違うところ２

• 価値の総和が最大となる組み合わせを探す

• 重さあたりの価値で分枝限定法を使う

7

public class KnapsackBB { // 0-1ナップザック問題を分枝限定法で解く private static double maxsofar;

private static boolean[] result; i t st ti b l [] h i private static boolean[] choice;

private static void backtrack(int i, double profit, double weight){ if(i >= (items.length-1)){ if(profit > maxsofar){f(p f f ){ maxsofar = profit; result = choice.clone(); // 現時点での最良の解 } } ls { } else { if(items[i].getWeight() <= weight){

choice[i] = true; // i番目の物を詰める

backtrack(i + 1, profit + items[i].getProfit(), weight - items[i].getWeight());( , p [ ] g (), g [ ] g g ()) } double z = 0; double u = weight; int j;

拡張ナップザック問題

本来の

0-1ナップザック問題

int j;

for(j = i+1; items[j].getWeight() <= u; j++){ u -= items[j].getWeight(); z += items[j].getProfit();

拡張ナッ

ック問題

[j] g () } z += u*items[j].getValue(); if((z + profit) > maxsofar){

choice[i] = false; // i番目の物は詰めない choice[i] = false; // i番目の物は詰めない backtrack(i+1, profit, weight);

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( 焼き芋 , 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) [sakai@star bin]$ java complex.KnapsackBB 5000_{チ リモヤ 1000 0 200 0} 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) チェリモヤ, 1000.0, 200.0 パッションフルーツ, 300.0, 90.0 カニステル, 300.0, 100.0 マンゴー, 398.0, 300.0 メロン 1000 0 800 0 new ItemBB( チェリモヤ , 1000, 200),

new ItemBB("番兵", 0, Double.POSITIVE_INFINITY) };

public static void main(String[] args) { double limit;

try {

limit = Double parseDouble(args[0]);

メロン, 1000.0, 800.0 パパイヤ, 298.0, 400.0 いちご, 200.0, 300.0 ぶどう, 333.0, 600.0 焼き芋 100 0 200 0 limit = Double.parseDouble(args[0]); }catch(Exception e){ limit = 9000; } Arrays.sort(items); f D bl NEGATIVE INFINITY 焼き芋, 100.0, 200.0 ドリアン, 980.0, 2000.0 重量の上限: 5000.0 個数: 10 重量の合計: 4990.0 価格の合計: 4909.0 [sakai@star bin]$ java complex.KnapsackBB 4900

チェリモヤ 1000 0 200 0

maxsofar = Double.NEGATIVE_INFINITY; choice = new boolean[items.length];

backtrack(0, 0, limit); double p = 0, w = 0; int n = 0; チェリモヤ, 1000.0, 200.0 パッションフルーツ, 300.0, 90.0 カニステル, 300.0, 100.0 マンゴー, 398.0, 300.0 メロン 1000 0 800 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]); } メロン, 1000.0, 800.0 パパイヤ, 298.0, 400.0 いちご, 200.0, 300.0 ぶどう, 333.0, 600.0 ドリアン 980 0 2000 0 } } System.out.print("重量の上限: " + limit); System.out.print("¥t個数: " + n); System.out.print("¥t重量の合計: " + w); System.out.println("¥t価格の合計: " + p); } 9 ドリアン, 980.0, 2000.0 すもも, 20.0, 60.0 びわ, 10.0, 50.0 重量の上限: 4900.0 個数: 11 重量の合計: 4900.0 価格の合計: 4839.0

変形ナップザック問題

• ｎ個の品物があって、

それぞれ価値と重さが決まっている

それぞれ価値と重さが決まっている

– 重さは正の整数である

• ３９２ページのナップザック問題と違うところ

• 重さの総和が制約として与えられる

重さの総和が制約として与えられる

• 品物はいくら選択してもよい

価値

総和が最大 なる組

合わ

を探す

• 価値の総和が最大となる組み合わせを探す

10

public class KnapsackDP { // ナップザック問題を動的計画法で解く private static void solve(ItemDP[] items, int weight, int[] result){

double[] gain = new double[weight+1]; i t[] h i i t[ i ht 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++){

ｊ

-１までの品物を使って

重さの限界ごとに最適値を求める

f ( ; g ; ){

int k = i - items[j].getWeight(); if(k >= 0){

if((gain[k] + items[j].getProfit()) > gain[i]){ in[i] in[k] it ms[j] tP fit();

重さの限界ごとに最適値を求める

gain[i] = gain[k] + items[j].getProfit(); choice[i] = j; } }

重さの限界値のときの価値

} } } int k;

for(int i = weight; choice[i] >= 0; i = items[k] getWeight()){

重さの限界直前に選んだ品物

for(int i = weight; choice[i] >= 0; i -= items[k].getWeight()){ k = choice[i]; result[k]++; }} } } 11

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)

[sakai@star bin]$ java complex.KnapsackDP 1200

とよのか

, 297.0, 298, 4

重量の上限

: 1200 個数: 4 重量の合計: 1192 価格の合計: 1188.0

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) {

[sakai@star bin]$ java complex.KnapsackDP 1190

とよのか

, 297.0, 298, 3

あすかルビー

, 288.0, 278, 1

p ( g[] g ) { int limit; try { limit = Integer.parseInt(args[0]); }catch(Exception e){ limit = 9000; }

重量の上限

: 1190 個数: 4 重量の合計: 1172 価格の合計: 1179.0

[sakai@star bin]$ java complex.KnapsackDP 1170

とよのか

, 297.0, 298, 2

あすか

ビ

288 0 278 2

}

int[] result = new int[items.length]; solve(items, limit, result);

double p = 0; int w 0 n 0;

あすかルビー

, 288.0, 278, 2

重量の上限

: 1170 個数: 4 重量の合計: 1152 価格の合計: 1170.0

[sakai@star bin]$ java complex.KnapsackDP 1150

とよのか

297 0 298 1

int w = 0, n = 0;

for(int i = 0; i < result.length; i++){ if(result[i] > 0){

p += items[i].getProfit()*result[i];

とよのか

, 297.0, 298, 1

あすかルビー

, 288.0, 278, 3

重量の上限

: 1150 個数: 4 重量の合計: 1132 価格の合計: 1161.0

[sakai@star bin]$ java complex KnapsackDP 1130

p [ ] g () [ ] w += items[i].getWeight()*result[i]; n += result[i];

System.out.println(items[i] + ", " + result[i]); }

[sakai@star bin]$ java complex.KnapsackDP 1130

あすかルビー

, 288.0, 278, 4

重量の上限

: 1130 個数: 4 重量の合計: 1112 価格の合計: 1152.0

[sakai@star bin]$ java complex KnapsackDP 1110

} }

System.out.print("重量の上限: " + limit); System.out.print("¥t個数: " + n);

[sakai@star bin]$ java complex.KnapsackDP 1110

とよのか

, 297.0, 298, 1

ももいちご

, 300.0, 398, 2

重量の上限

: 1110 個数: 3 重量の合計: 1094 価格の合計: 897 0

y p ( ) System.out.print("¥t重量の合計: " + w); System.out.println("¥t価格の合計: " + p); } } 12

重量の上限

: 1110 個数: 3 重量の合計: 1094 価格の合計: 897.0

[sakai@star bin]$ java complex.KnapsackDP 1093

とよのか

, 297.0, 298, 2

近似アルゴリズム

• 最適値を求めるのではなく、

最適値に近い近似値を求める問題に変形

最適値に近い近似値を求める問題に変形

• 近似解法の時間計算量

– 解くことをあきらめる必要がない程度

• 少なくとも指数関数時間ではない、など

少なくとも指数関数時間ではない、など

• 近似解の精度

最適値に対し 近似値がどれくら 近 か

– 最適値に対して近似値がどれくらい近いか

13

Ｅ

ｌｉｄ的巡回セ ルスマン問題

Ｅｕｃｌｉｄ的巡回セールスマン問題

（４０２ページ）

• 元の問題

グラ が与えられており 各辺に重みが

– グラフが与えられており、各辺に重みがつ

いている。

– このグラフの頂点を全て通り、重みの総和

が最小の経路を求める。

• 変形した問題

– グラフの各辺の重みは０以上

– グラフの各辺の重みは０以上

• 少なくとも重みの総和が減ることはない

任意の３頂点（Ａ Ｂ Ｃ）間で

_d

_d

_d

– 任意の３頂点（Ａ，Ｂ，Ｃ）間で

• ＡからＣへ行くのに、Ｂを通らないほうが良い

AB BC AC 14

d

d

d

+

≥

貪欲解法

貪欲解法

1. 任意の頂点をひとつ選ぶ

2. そこから到達可能な最小の重みの辺を選ぶ

3. その辺の先の頂点から同様に次の辺を選ぶ

局

所

• すでに通過した頂点へ至る辺を除去する

4 そのうち最初に選んだ頂点に戻る道ができる

所

的

4. そのうち最初に選んだ頂点に戻る道ができる

1 最小の重みの辺をグラフ全体から選ぶ

1. 最小の重みの辺をグラフ全体から選ぶ

•

この辺を除外する

大

2. 次に最小の重みの辺を選ぶ

•

このときひとつの輪にならない辺も除外する

大

域

的

15

このときひとつの輪にならない辺も除外する

3. そのうちひとつながりの輪ができる

的

挿入法

• どれか１つの頂点を選ぶ

輪の中に 輪の外の頂点を加える

• 輪の中に、輪の外の頂点を加える

– 輪を作る各頂点から最近の頂点を選ぶ（方法１）

– 輪を作る各頂点から最遠の頂点を選ぶ（方法２）

• 大局的には 遠い点どおしを先に結ぶほうがよさそう

大局的には、遠い点どおしを先に結ぶほうがよさそう

…

16

局所探索法

• まず全頂点をどうにかして輪につなぐ

重さの総和の大小は気にしない

– 重さの総和の大小は気にしない

• 交差している２辺を繋ぎかえる

– 特に３本以上同時につなぎ替えるといいらしい

• つなぎかえができなくなったら終了

• つなぎかえができなくなったら終了

17

期末試験

期末試験

• 教室: Ｃ１０１

• 日時: ２０１１年７月２５日１６時３０分∼１８時００分

入室限度

: １６時５０分まで

– 入室限度: １６時５０分まで

– 退出可能: １７時００分より

• 持ち込み可

– 教科書・資料(自筆・コピー問わず)は持ち込み可

教科書 資料

(自筆 コピ 問わず)は持ち込み可

– 人間・パソコン・携帯電話・PHSなど持ち込み不可

学生証必携

• 学生証必携

– 持っていない場合は教務で発行してもらうこと

18