2012年4月30日星期一

Travelling Salesman Problem

在前作Travelling Salesman介紹了一套十分期待的電影,以一例子介紹最優路徑問題,但沒有答案,因為例子中城市有五個,總共5! = 120個組合,要逐一加數來找答案,非常辛苦差,亦不符programmer本色。一個成功的programmer首要條件是懶。第二是不能做重覆的事情,故寫program解決。

import itertools

def tsp(table):
    """Travelling Salesman Problem, return lowest cost tuple (path, cost) in table.

    City names are key of table and table is dictionary of source and
    destination dictionary, destination dictionary
    is city name and cost {'source': {'destination':1000}}.

    >>> tsp({'a':{'b':1,'c':2},'b':{'a':3,'c':4},'c':{'a':5,'b':6}})
    (('a', 'b', 'c'), 5)
    """
     best_path = ''
    best = 10000000000000
    for i in itertools.permutations(table.keys()):
        cost = 0
        src = i[0]

        for dest in i[1:]:
            cost += table[src][dest]
            if cost >= best:
                break
            src = dest
        else:
            best_path = i
            best = cost
    return best_path, best

if __name__ == '__main__':
    table = {'a':{'b':5000, 'c':6000, 'd':8000, 'e':4000},
             'b':{'a':5000, 'c':1200, 'd':2500, 'e':3200},
             'c':{'a':6000, 'b':2500, 'd':3100, 'e':5600},
             'd':{'a':8000, 'b':4000, 'c':4800, 'e':7200},
             'e':{'a':4000, 'b':9000, 'c':7300, 'd':4900},
            }

    p, i = tsp(table)
    print('The best path is {}, cost is {}.'.format('->'.join(p), i))

在解決這問題時,花了很多時間思考,table用什麼data type儲存,用flat dictionary,即是table[source+dest]好呢,還是現在的方法比較節省RAM呢?現在的儲存方法,table size是n×(n-1)。

另外,也找尋了一些網上解決方法,當中建基於問題中的城市距離,然後找尋最接近的城市解決來計算最短距離,但我並沒有以距離為前題,而以cost,可以是車費,或時間為data,所以問題變成Statistics問題中的Standard Deviation (σ),若σ少,即是城市間的cost分別小,那麼最差路徑和最優路徑分別不大,未必值得花時間計算,只有大σ的情況下才需要。運行時最壞情況會是loop n!×(n-1)次,故只能從programming角度找尋較快方法。加thread或multi-process會提高多少速度呢?但multithread要lock variable "table",反而會減慢速度。

其中一個提升速度最快捷方便的方法是用轉用PyPy ,在一部老爺機上運行,data加至十個城市,用Python 3.2.3 Profile結果如下:
The best path is a->g->b->c->j->d->h->e->i->f, cost is 578.
         2055 function calls (1984 primitive calls) in 6.982 seconds

PyPy 1.8結果:
The best path is a->g->b->c->j->d->h->e->i->f, cost is 578.
         3142 function calls (2961 primitive calls) in 2.766 seconds

快一倍有多。

沒有留言:

發佈留言