タグ

関連タグで絞り込む (1)

タグの絞り込みを解除

tspに関するma38suのブックマーク (3)

  • 巡回セールスマン問題におけるLin-Kernighan法の実装

    2008/02/04 瀧川啓介 目次 巡回セールスマン問題とは何か 研究の背景 目標 アルゴリズムの概要 構造体に関して 実験結果 考察、まとめ リンク 参考文献 巡回セールスマン問題とは何か 英語ではTraveling Salesman Problemと言い、頭文字を取ってTSPとも呼ぶ。 多くの市と各市間の移動コストが与えられたとき、全ての市を一度だけ回って戻ってくるルートのうちコスト最小のものを求める(セールスマンが所定の数の都市を1回だけ巡回する場合の最短経路を求める)問題のことを指す。 [ index ] 研究の背景 よく知られるNP困難問題で、30年以上前から研究されてきた内容 単純に最適解を求めるには要素数n個のTSPグラフの場合、n!通りの場合について考えれば良いが、当然ながら膨大な計算量となる。 しかし、馴染みのないコマンドを利用するよりも、 近年においてはTSP自

    ma38su
    ma38su 2009/02/17
  • 6月11日研究報告

    6月11日研究報告 1. 2-Opt法 巡回路の中の何かの枝をλとする.λ-Opt法は,λの枝を切って,代わりに同じ数の枝でつなぎなおしてコストの低い巡回路ができる限り,その操作を繰り返す(Fig.1). 手順 1)巡回路を1つ作る. 2)巡回路の2の枝(ア,イ)と(ウ,エ)でcアウ+cイエ<cアイ+cウエとなる枝がなければ終了. 3)そのような枝があれば枝(ア,イ)と(ウ,エ)を枝(ア,ウ)と(イ,エ)とでつなぎ直して新しい巡回路をつくり2)に戻る. Fig.1 2-Opt法 λの大きさ λを大きくするほど解は良くなる.しかし,都市が8以上で,λがn/4であれば,λ-Opt法を問題Iに使って得られる近似解のコストAλ-Opt(I)が最適解のコストOPT(I)と比べて Aλ-Opt(I)/OPT(I)=2-2/n となる問題があることが知られている(Fig.2

    ma38su
    ma38su 2008/12/12
    近似解放の解説
  • 局所探索

    巡回セールスマン問題に対する局所探索法 巡回セールスマン問題について 複数箇所の訪問先(以下都市とよびます)をすべて一度だけ訪問するとき、 その訪問の総距離が最短となる巡回路(つまり出発地に戻らなくてはならない) を求める問題です。 都市はアプレットの右上端にあるプルダウンメニューから問題例を選ぶか、 画面上をクリックすることで配置することができます。 SOLVEボタンで局所探索法による求解の動作を開始します。 動作中にSTOPボタンまたは画面をクリックすると一時停止します。 SOLVEボタンで動作を再開します。 CLEARボタンで都市を消去します。 局所探索法について 局所探索は、すでに構成済み(1)の巡回路を改良するために用いられます。 なお、ここで紹介するアプレットでは巡回路の構成はNearest Neighbour 〜もっとも近いお隣さんをたどること〜によって実現して

    ma38su
    ma38su 2008/12/12
    or-optの解説
  • 1