バイオインフォ学生あれこれ

有名な Traveling Salesman Problem (TSP) TSP の定義を簡単に述べると次のようになる。すなわち、 グラフ について、頂点 は辺 を持っており、各辺は重み を持っている。この時に巡回路の重みの総和が最小となるものを求めよ。 多項式時間定数近似アルゴリズム グラフ が与えられたとき、 最適解を で表すことにする。同…