気に入った記事をブックマーク
- 気に入った記事を保存できます
保存した記事の一覧は、はてなブックマークで確認・編集ができます
- 記事を読んだ感想やメモを書き残せます
- 非公開でブックマークすることもできます
エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
0
記事へのコメント0件
- 注目コメント
- 新着コメント
新着コメントはまだありません。
このエントリーにコメントしてみましょう。
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
いまの話題をアプリでチェック！
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Spaghetti Source - 巡回セールスマン問題
説明 巡回セールスマン問題とは，グラフが与えられたとき，全ての頂点を一度ずつ通る巡回路で，経路長が... 説明 巡回セールスマン問題とは，グラフが与えられたとき，全ての頂点を一度ずつ通る巡回路で，経路長が最短のものを求める問題である． この問題は（判定問題にして）NP 完全であることが知られているので，多項式時間の解法は期待できない．単純に全ての経路を試すアルゴリズムは O(V!) 程度の計算量がかかるが，動的計画法に基づくアルゴリズムでは O(V 2^V) 程度の計算量に軽減できる． X[j][S + {j}] = E[j][i] + X[i][S] ここで X[i][S] は始点から i に至る S のすべての頂点を通る最小重み巡回路である．状態 S をビットで管理することによってプログラムが簡潔になる． 計算量 O(n 2^n)． ソースコード void rec(vector< vector<int> >& Y, int i, int S, vector<int>& path) { if
ブックマークしたユーザー
すべてのユーザーの
詳細を表示します
詳細を表示します
