Optimization Problem

Optimization包含两部分

  • An objective function that is to be maximized or minimized.

    例如寻找Boston到Istanbul最便宜的机票

  • A set of constraints

比较典型的应用

  • Shortest path
  • Traveling salesman: 销售员要走过一些城市，如何最大程度避免重复
  • Bin Packing：如何把货物装入集装箱
  • Sequence alignment: two genetic strings. find a way to line them up to maximize the overlap.
  • Knapsack

Knapsack 背包问题

import pylab

class Item(object):
    def __init__(self, n, v, w):
        self.name = n
        self.value = float(v)
        self.weight = float(w)
    def getName(self):
        return self.name
    def getValue(self):
        return self.value
    def getWeight(self):
        return self.weight
    def __str__(self):
        result = '<' + self.name + ', ' + str(self.value) + ', '\
                 + str(self.weight) + '>'
        return result

def buildItems():
    names = ['clock', 'painting', 'radio', 'vase', 'book', 'computer']
    vals = [175,90,20,50,10,200]
    weights = [10,9,4,2,1,20]
    Items = []
    for i in range(len(vals)):
        Items.append(Item(names[i], vals[i], weights[i]))
    return Items

建立Item Class, 把所有的item组成一个Items List。

贪心算法

def greedy(Items, maxWeight, keyFcn):
    assert type(Items) == list and maxWeight >= 0
    ItemsCopy = sorted(Items, key=keyFcn, reverse = True)
    result = []
    totalVal = 0.0
    totalWeight = 0.0
    i = 0
    while totalWeight < maxWeight and i < len(Items):
        if (totalWeight + ItemsCopy[i].getWeight()) <= maxWeight:
            result.append((ItemsCopy[i]))
            totalWeight += ItemsCopy[i].getWeight()
            totalVal += ItemsCopy[i].getValue()
        i += 1
    return (result, totalVal)

三种不同的指标：

def value(item):
    return item.getValue()

def weightInverse(item):
    return 1.0/item.getWeight()

def density(item):
    return item.getValue()/item.getWeight()

取任意一个指标得出的结果：

def testGreedy(Items, constraint, getKey):
    taken, val = greedy(Items, constraint, getKey)
    print ('Total value of items taken = ' + str(val))
    for item in taken:
        print '  ', item

把三种综合在一块：

def testGreedys(maxWeight = 20):
    Items = buildItems()
    print('Items to choose from:')
    for item in Items:
        print '  ', item
    print 'Use greedy by value to fill a knapsack of size', maxWeight
    testGreedy(Items, maxWeight, value)
    print 'Use greedy by weight to fill a knapsack of size', maxWeight
    testGreedy(Items, maxWeight, weightInverse)
    print 'Use greedy by density to fill a knapsack of size', maxWeight
    testGreedy(Items, maxWeight, density)

testGreedys()

得到：

``` Items to choose from:

<clock, 175.0, 10.0> <painting, 90.0, 9.0> <radio, 20.0, 4.0> <vase, 50.0, 2.0> <book, 10.0, 1.0> <computer, 200.0, 20.0> Use greedy by value to fill a knapsack of size 20 Total value of items taken = 200.0 <computer, 200.0, 20.0> Use greedy by weight to fill a knapsack of size 20 Total value of items taken = 170.0 <book, 10.0, 1.0> <vase, 50.0, 2.0> <radio, 20.0, 4.0> <painting, 90.0, 9.0> Use greedy by density to fill a knapsack of size 20 Total value of items taken = 255.0 <vase, 50.0, 2.0> <clock, 175.0, 10.0> <book, 10.0, 1.0> <radio, 20.0, 4.0>


但这只是按照标准排序，并不是最佳方案。当然，我们可以用brutal force的方法来寻找最佳答案。把所有可能的组合都列出来，取符合限制条件的最大值。

首先写了一个helper function，把数字n转化为小于特定数字的二进制数。

```python
def dToB(n, numDigits):
    """requires: n is a natural number less than 2**numDigits
      returns a binary string of length numDigits representing the
              the decimal number n."""
    assert type(n)==int and type(numDigits)==int and n >=0 and n < 2**numDigits
    bStr = ''
    while n > 0:
        bStr = str(n % 2) + bStr
        n = n//2
    while numDigits - len(bStr) > 0:
        bStr = '0' + bStr
    return bStr

然后 Generate a list of lists representing the power set of Items。

def genPset(Items):
    """Generate a list of lists representing the power set of Items"""
    numSubsets = 2**len(Items)
    templates = []
    for i in range(numSubsets):
        templates.append(dToB(i, len(Items)))
    pset = []
    for t in templates:
        elem = []
        for j in range(len(t)):
            if t[j] == '1':
                elem.append(Items[j])
        pset.append(elem)
    return pset

然后，从中选择best

def chooseBest(pset, constraint, getVal, getWeight):
    bestVal = 0.0
    bestSet = None
    for Items in pset:
        ItemsVal = 0.0
        ItemsWeight = 0.0
        for item in Items:
            ItemsVal += getVal(item)
            ItemsWeight += getWeight(item)
        if ItemsWeight <= constraint and ItemsVal > bestVal:
            bestVal = ItemsVal
            bestSet = Items
    return (bestSet, bestVal)

def testBest():
    Items = buildItems()
    pset = genPset(Items)
    taken, val = chooseBest(pset, 20, Item.getValue, Item.getWeight)
    print ('Total value of items taken = ' + str(val))
    for item in taken:
        print '  ', item

testBest()

得到如下答案：

``` Total value of items taken = 275.0

<clock, 175.0, 10.0> <painting, 90.0, 9.0> <book, 10.0, 1.0>


当然，更好的办法是decision tree：

```python
def maxVal(toConsider, avail): 
    if toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getWeight() > avail:
        result = maxVal(toConsider[1:], avail)
    else:
        nextItem = toConsider[0]

        #Explore left branch
        withVal, withToTake = maxVal(toConsider[1:],
                                      avail - nextItem.getWeight())
        withVal += nextItem.getValue()
        #Explore right branch
        withoutVal, withoutToTake = maxVal(toConsider[1:], avail)

        #Choose better branch
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    return result

def smallTest():
    Items = buildItems()
    val, taken = maxVal(Items, 20)
    for item in taken:
        print(item)
    print ('Total value of items taken = ' + str(val))

smallTest()

Source Code

鉴于背包问题本质上的复杂性是指数型的，所以我们这里介绍一下另外一种可以saving redundant work的方法。思路主要是把partial solution保留下来，不用每次用到的时候都重新算。

最简单的Fibonacci算法：

def fib(x):
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

def testFib(n):
    assert type(n) == int and n >=  0
    for i in range(n):
        print ('fib of', i, '=', fib(i))

会越算越慢。如果把中间计算结果用dict存起来，就会快很多。Memoization

def fastFib(x, memo):
    assert type(x) == int and x >= 0 and type(memo) == dict
    if x == 0 or x == 1:
        return 1
    if x in memo:
        return memo[x]
    result = fastFib(x-1, memo) + fastFib(x-2, memo)
    memo[x] = result
    return result

def testFastFib(n):
    assert type(n) == int and n >=  0
    for i in range(n):
        print ('fib of', i, '=', fastFib(i, {}))

Source Code