鳩でもわかるC#

ハミルトン閉路とは？ 任意の頂点から出発してすべての頂点をちょうど 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つ選ぶ。これが今いる都市。 今までに訪れたことのない都市のうち、今いる都市に最・・・

続きを読む

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。 どのようにして解を求めればよいのでし・・・

続きを読む