Eric Grimson, John Guttag, and Ana Bell. 6.0002 Introduction to Computational Thinking and Data Science. Fall 2016. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Lecture 1. Introduction and Optimization Problems
Optimization Modelとは，対象となる関数(Objective function)をある制限によってもとで最大化したり最小化したりする引数を探し，現実の問題に応用するモデルのこと．例えばKnapsack problemがある．
Knapsack Problem :
ナップサックに入れられるものの重さの総和が決まっていて，重さの異なる複数種類のものをできるだけ価値が大きくなるようにナップサックに入れたいとき，どうやって入れるものを選ぶか． という問題．
- Continuous or fractional varinant: 入れるものが粉や液体のようないくらでも分割できるものではほとんど意味がない．
- 0/1 variant: それぞれの種類のものは1つしかない –その一つを持っていくか持っていかないか
0/1 Knapsack Problem, Formalized
- それぞれの物品は
Brute Force Algorithm
- ありうる入れ方の組み合わせをすべて列挙する．(冪集合をとる操作)
- 組み合わせの重量の和がWを上回った組み合わせを取り除く
- 残った組み合わせそれぞれの価値の和を計算し，最大の価値の組み合わせを選ぶ
この方法だと組み合わせ爆発が生じる： 物品が100種類ある時，その冪集合の要素数は
より現実的な解法:
Greedy Algorithm(貪欲法) a Practical Alternative
while knapsack not full
put "best" avalilable item in knapsack- “bset”とは何か？が問題となる．
Example
| Food | wine | beer | pizza | burger | fries | coke | apple | donut |
|---|---|---|---|---|---|---|---|---|
| value | 89 | 90 | 30 | 50 | 90 | 79 | 90 | 10 |
| calories | 123 | 152 | 258 | 354 | 365 | 150 | 95 | 195 |
このようなメニューがあるとき，摂取カロリーを750kcal以下にしつつ，valueの和を最大化する．(ここでvalueというのは値段でなく好みの定量)
class Food(object):
def __init__(self, n, v, w,):
self.name = n
self.value = v
self.weight = w
def getValue(self):
return self.value
def getCost(self):
return self.calories
def density(self):
return self.getValue()/self.getCost()
def __str__(self):
return self.name + ': < ' + set(self.value) + ', ' +str(self.calories) +">"
def buildMenu(names, values, calories):
menu = []
for i in range(len(values)):
menu.append(Food(names[i], values[i], calories[i]))
return menu
def greedy(items, maxCost, keyFunction):
itemsCopy = sorted(items, key = keyFunction, reverse = True)
# "best"の基準をkeyFunctionで指定する．
# value, cost(calories), value/cost, cost^-1などを使う.
# ソートの問題だから，クイックソートを使えば計算量は O(nlog(n))
# (pythonはtimsort というクイックソートの一種を使っている)
resut = []
totalValue, totalCost = 0.0, 0.0
for i in range(len(itemsCopy)): # 計算量はO(n)
if (totalCost + itemsCopy[i].getCost()) <= maxCost:
result.append(itemsCopy[i])
totalCost += itemsCopy[i].getCost()
totalValue += itemsCopy[i].getValue()
return (result, totalvalue)
# 全体の計算量はO(n log n)
貪欲法は簡単に実装できるが，
ナップサック問題での貪欲法は，必ずしも最適解を与えないし，どれほど最適解に近いかわからないという欠点がある．
Lecture 2. Optimization Problems,
Definition Tree
Treeはデータ構造の一つで，ただ一つのルートノードから発生する子ノードがあり，その子ノードから更に孫ノードが発生し・・・という具合に，ループと合流を許さない階層構造が定義されている．あるノードがからn個のノードを遡るとルートノードに至るとき，そのノードはdepth nであるという(ルートはdepth 0)またdepth n であるノードたちをlevel nに属するという.treeのノードのたちのうち，最大のdepthをtreeのlevelという．
Search Tree Implementation
rootから木を構成する．物品は最初にテーブルに並んでいて，その順序関係は変わらないとする．
1. 最も若い番号の物品をナップサックに入れても重量オーバーにならないとき，それをナップサックに入れるときのノードと入れないときのノードを作り，重量オーバーになるとき，ナップサックに入れないときのノードのみ作る．どちらにせよその物品はテーブルから削除する．
2. 子ノードを持っていない全てのノードに1の操作を行う
3. テーブルが空になったら，最大の価値があるような末端ノードを選ぶ．
Computational Complexity
- 処理時間は生成されるノードの数に依存する
- level i にあるノードの個数は最大 個
最初にテーブルにn個の物品があるとき,ノードの総数は
=> すなわちO
Decision Tree Implementation
def maxVal(toConsider, avail): # これは効率の悪いアルゴリズムである．
"""
assumes toConsider a list of items,
avail a weight
Returns a tuple of the total value of a solution to 0/1 knapsack problem
and the items of that solution
"""
# toConsiderの左端をナップサックに入れるかどうかを考えている．
if toConsider == [] or avail == 0: # ノードを追加できない
result = (0, ())
elif toConsider[0].getUnits() > avail: # ナップサックには空きがあるが，
# 今考えている物品は入らない
result = maxVal(toConsider[1:], avail)
else: # ナップサックに今考えている物品が入る
nextItem = toConsider[0]
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getUnits())
withVal += nextItem.getValue()
vithoutVal, withoutToTake = maxVal(toConsider[1:], avail)
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return resultDynamic Programming(DP)
クロージャを使ったメモ化
でフィボナッチ数列の計算を高速化できたように，問題を解く仮定で同じサブ問題を何度も解く必要があるとき，最初に計算した答えを保存しておき，以下同じ引数が出てきたときには保存していた答えを取ってくるようにすると，高速に解けることがある．
メモ化が有効である条件は，
- Optimal substructure : 問題の最適な答えは，その問題をいくつかの小問題に分けたときの小問題の最適解たちに簡単な演算を施すことで得られて，小問題はもとの問題と同じ形をしている．
- Overlapping subproblems : 問題の最適解を得るために，同じ問題を複数書いといているとき
この基準からすると，fig.1の場合はDPはさほど有効でないが，fig.2の場合には計算量が半分以下になることが見て取れる．
def fastMaxVal(toConsider, avail, memo={}): # メモ化による高速版
"""
assumes toConsider a list of items,
avail a weight
Returns a tuple of the total value of a solution to 0/1 knapsack problem
and the items of that solution
"""
if (len(topConsider), avail) in memo.keys():
result = memo[(len(topConsider), avail)]
# toConsiderの左端をナップサックに入れるかどうかを考えている．
elif toConsider == [] or avail == 0: # ノードを追加できない
result = (0, ())
elif toConsider[0].getUnits() > avail: # ナップサックには空きがあるが，
# 今考えている物品は入らない
result = fastMaxVal(toConsider[1:], avail, memo)
else: # ナップサックに今考えている物品が入る
nextItem = toConsider[0]
withVal, withToTake = fastMaxVal(toConsider[1:],
avail - nextItem.getUnits(), memo)
withVal += nextItem.getValue()
vithoutVal, withoutToTake = maxVal(toConsider[1:], avail, memo)
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
memo[(len(toConsider), avail)] = result
return resultSummary of Lectures 1-2
- 多くの実践的な問題は最適化問題として定式化できる
- 多くの場合Greedy algorithm(貪欲法)は十分良い解を与えるが，最適とは限らない．
- 最適解を求めるのは指数的に困難
- optimal substructure とoverlapping subproblemsの性質を持っているなら，Dynamic Programmingによって，高速に最適解を得られる場合がある
0 件のコメント:
コメントを投稿