「ネタ」の記事一覧

二分ヒープと優先度付きキュー プライオリティキュー（優先度付きキュー）とは、優先度の高いデータから取り出すというデータ構造で、その代表的なものがヒープといわれる木構造です。ヒープの中にも単純な構造である二分ヒープを扱いま・・・

続きを読む

ハミルトン閉路とは？ 任意の頂点から出発してすべての頂点をちょうど 1 回ずつ訪問したのち、最初の頂点に戻ってくることができるようなグラフをハミルトングラフといいます。またそのような順番で頂点を並べた閉路をハミルトン閉路・・・

続きを読む

オイラーグラフとオイラー閉路 グラフ上の任意の頂点から出発して、すべての辺を使って一筆書きをすることができるようなグラフを準オイラーグラフと呼びます。またそのような一筆書きの順番で頂点を並べたパスをオイラー路と呼びます。・・・

続きを読む

ワーシャルフロイド法とは？ ワーシャルフロイド法は最短経路問題で使われるアルゴリズムの１つです。重みが負の辺があっても負閉路がない限り使えます。 下のようになっている場合、0 → 1 と直接移動する場合は 10 ですが、・・・

続きを読む

連続する区間の和 与えられたint型の配列において、長さが 1 以上で総和が与えられた値以下であるものを考えます。そのような区間がいくつあるか、区間の長さで最大のものを求めるにはどうすればいいでしょうか？ （例）int[・・・

続きを読む

累積和 累積和とは配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速に行うことができます。 配列と累積和 int型の・・・

続きを読む

最長増加連続部分列 最長増加連続部分列とは、配列があったとき単調増加になっている最も長い部分です。配列が {1, 2, 3, 4, 5} であるなら配列全体が単調増加しているので求める解は {1, 2, 3, 4, 5}・・・

続きを読む

動的計画法で2項間漸化式を解く 漸化式とは数列を再帰的に定める等式です。ある項とそれ以前の項の関係がはっきりしているなら、各項の値を求めることができます。 2項間漸化式を解く a_1 = 6，a_(n) = a_(n &・・・

続きを読む

今回も巡回セールスマン問題を解きます。 巡回セールスマン問題を2-opt法で解く 2-opt法とは以下のような方法です。 初期解を適当に作る。 一定の回数か、解があまり改善されなくなるまで以下を繰り返す 　巡回路を成す辺・・・

続きを読む

巡回セールスマン問題を最近傍法で解く 巡回セールスマン問題を最近傍法で解いてみることにします。やり方は以下のとおり。 始点となる都市を適当に1つ選ぶ。これが今いる都市。 今までに訪れたことのない都市のうち、今いる都市に最・・・

続きを読む