13．近似アルゴリズム

内容

1. スライド　1 13．近似アルゴリズム
2. スライド　2 １３．１　　近似アルゴリズムの種類
3. スライド　3 ヒューリスティックと近似アルゴリズム
4. スライド　4 α近似アルゴリズム
5. スライド　5 β近似アルゴリズム
6. スライド　6 ＡＰＸ
7. スライド　7 PTASとFPTAS
8. スライド　8 近似アルゴリズムの存在
9. スライド　9 １３−２．巡回セールスマン問題
10. スライド　10 　三角不等式を満足しないようなネットワーク型の巡回セールスマン問題は、近似アルゴ...
11. スライド　11 ハミルトン閉路問題と巡回セールスマン問題
12. スライド　12 巡回セールスマン問題への帰着
13. スライド　13 幾何巡回セールスマン問題（GTSP）
14. スライド　14 　2次元（ユークリッド）平面上の点集合を考えれば、2点間の離は自動的に三角不等式...
15. スライド　15 NTSPとGTSP
16. スライド　16 ２近似アルゴリズム
17. スライド　17 ２近似アルゴリズムの動作
18. スライド　18 近似率の解析
19. スライド　19 また、アルゴリズムで得られる閉路では、最小木を2重化したものより小さいので、次が...
20. スライド　20 １．５近似アルゴリズム
21. スライド　21 ２近似アルゴリズムの動作
22. スライド　22 近似率の解析
23. スライド　23 　奇点が偶数個しかないことに注意すると、いつもきちんと２分割することができること...
24. スライド　24 　　また、三角不等式がなりたっているので、 パスで結ぶより直接辺でたどったほう...
25. スライド　25 一方、アルゴリズムより、
26. スライド　26 　このように、いろいろな技法を組み合わせて、近似率の改善が 行われる。 ...
27. スライド　27 １３−３．ナップザック問題
28. スライド　28 ナップザック問題における欲張り法（グリーディ法、Greedy法）
29. スライド　29 ナップザックに対する欲張り法
30. スライド　30 欲張り法の性能
31. スライド　31 よって、
32. スライド　32 以上より、次の関係式が導ける。
33. スライド　33 欲張り法で悪い評価値を出すインスタンス
34. スライド　34 ナップザックの1/2近似アルゴリズム
35. スライド　35 近似率
36. スライド　36 ナップザック問題に対するFPTAS
37. スライド　37 FPTASの評価
38. スライド　38 よって、
39. スライド　39 計算時間
40. スライド　40 ナップザック問題の近似可能性