YottaGin

[グラフ] プリム法

プリム法はクラスカル法と同じ最小全域木を探すアルゴリズムです。最短経路を探すダイクストラ法にとても良く似ています。プリム法プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象とな...

sklearn の GridSearchCV を LightGBM で使おうとした時、 GridSearch へ Categorical Feature を渡そうとすると “categorical_feature keyword has been found in params...

Python でクラスカル法を実装します。 SciPy で最小全域木を求める時はクラスカル法を使っています。 scipy.sparse.csgraph.minimum_spanning_tree Vertex と Edge 与えられた...

クラスカル法は、素集合データ構造を使い最小全域木の問題を解くアルゴリズムです。全域木ある無向グラフを考えた時、このグラフの全域木とは、グラフの頂点全てを使い構成される部分グラフで、木構造になるものです。全域木（ぜんいきぎ、英:Span...

以下のスライドがダントツで分かりやすいです。素集合データ構造素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割し...

DAG DAG とは Directed acyclic graph 有向非巡回グラフの略で、閉路のない有向グラフのことです。 DAGの例。有向グラフかつ閉路がない。有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんか...

ベルマンフォード法ベルマン–フォード法(英:Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキュー...

2020/2/14 雑記

TARGETの独自指数やその他外部指数として保存していた指数を、指定した期間内の全レース分をCSVファイルとして出力する方法です。 ZI や TGX を外部指数に設定以下の操作でZI や TGX といったTARGETの独自指数を外部指数に設定することができます。 ...

最短経路問題グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。出典: フリー百科事典『...

Python で深さ優先探索を実装します。ノードクラス幅優先探索と同じです。各ノードは自身の名前、隣接リスト、訪問済みかどうかのフラグを持ちます。 class Node(object): def __init__(s...