アルゴリズム
タイトルについて 正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です Binary Indexed Tree とは 以下のクエリに時間O(logN)で答えることが出来るデータ構造. 初期化 サイズNの配列の要素を0に初…
平面tspの分岐限定法のコードをなんとなく書いてみたけれども,全然早くならなかった. Traveling Salesman Problem (TSP) N個の都市と都市間の距離が与えられる.全ての都市をちょうど一度ずつ巡って始点に戻る順回路の中で移動距離が最小のものを出力する…
2018/02/22 更新 文章を修正 区間スケジューリング問題 http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用. 区間スケジューリングは次の問題である.仕事が n 個与えられる.各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定さ…
※ 2017/12/11更新:指数時間アルゴリズムについて記述 ※ 2018/02/21更新:全体的に書き直し ※ 2018/11/02更新:2部グラフのケースのみ残し,タイトルを変更. 最小点カバー問題 辺集合E,頂点集合V,頂点重みw(v)から成るグラフGが与えられる. 頂点集合S⊆V…