Python 巡回セールスマン問題

巡回セールスマン問題をpythonで解きます。
問題の概要はwikipediaをご覧ください。
巡回セールスマン問題 - Wikipedia


01整数計画法を使っても解けますが、今回は動的計画法を使用します。
f:id:inarizuuuushi:20170128162006j:plain

擬似コード f:id:inarizuuuushi:20170128162011j:plain (字が汚くて、ごめんなさい)



pythonコード
DPは配列ではなく、辞書を使用しています。



次回からはcpythonを使ってこのコードを高速化していこうと思います。