IDA* -- Iterative Deepening A* - Qiita
自分は孫弟子にあたるらしいRichard E. Korf 先生の論文紹介です。 会ったことないですがKorf先生→ https://www.youtube.com/watch?v=EnX8cQPiB1M https://www.youtube.com/watch?v=TAjyI06Q1x8 IDAはAと同じく最適解を返すアルゴリズムですが、A*と異なり メモリ使用量が線形 であるという違いがあります。 Iterative Deepening Depth First Search だれだ反復深化深さ優先探索なんて長ったらしい名前を付けたのは。 反復Xは長いのでIDDFSと呼びましょう。 IDDFSは、ダイクストラの深さ優先版です。 ダイクストラやA*などの最良優先探索系、もとい幅優先探索系に共通する問題は、OPENリストを全部メモリに確保しておかないといけないという点です。 しかし、実際のコ
行列木定理の証明 - blogoid
0. はじめに 今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。 行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を証明してみたいと思います。 1. 定理の内容 頂点数$n$のループを含まない多重無向グラフ$G$が与えられたとします。対角成分に頂点の次数を並べた行列から、隣接行列*1を引いたものをラプラシアン行列といいます。つまり、$G$に対する$n$×$n$ラプラシアン行列$L=(l_{ij})$は$$\begin{aligned}l_{ij}=\begin{cases}\text{頂点iの次数}&(i=j)\\ \text{頂点iと頂点jの間の辺の数}\times (-1)&(\mathrm{otherwise}) \end{cases}
トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
Dijkstra法に関するn考察 〜前半〜 - Mister雑記
(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。) 競技プログラミングのグラフ問題でしばしば題材となるアルゴリズム「Dijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。 そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。 目次 目次 Dijkstra法の概要 何をするアルゴリズムか 具体例 イメージ？ 実装方法 パターンA パターンB (PFS) 計算量の比較 問題例 後半について Dijkstra法の概要 何をするアルゴリズムか Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められる
ダイクストラとポテンシャルのはなし - niuez’s diary
はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる. 選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する. を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う). #include <set> #include <queue> #include <vector> struct edge { int u,v; int dist; }; std::vector<int> dijkstra(const st
Graph Golf参加記
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。 前提知識として知っておいてほしい単語は以下の2つくらいです。 グラフ(点と点が繋がってるアレのこと) 次数(頂点に繋がってる辺の本数のこと) 問題内容 自然数nとdが与えられる。頂点数nでどの頂点の次数もd以下であるようなグラフのうち 1. 直径 2. ASPL が小さいものを構
最短経路の個数も一緒に数え上げる最短経路アルゴリズム - けんちょんの競プロ精進記録
ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 if (dp[e.to] < dp[e.from] + e.cost) { dp[e.to] = dp[e.from] + e.cost; } これをちょっと変えるだけで、最短経路の本数も一緒に数え上げられます。 // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 int num[MAX_V]; // num[v] := 始点 s から頂点
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
一般的なダイクストラ法 - kirika_compのブログ
概要 ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。 詳しく 少し天下り的だけど、以下の半環を考える。 (a, x) + (b, y) := a < b ? (a, x) : a > b ? (b, y) : (a, x + y), (a, x) * (b, y) := (a + b, x * y) この半環を使って、[Mohri2002]の方法でダイクストラ法を行うことにより、s-vの最短距離とs-vの最短経路の個数が全ての頂点vについて分かる。 ソースコードは以下の通り。 gist.github.com ARC090 E - Avoiding Collision で確かめた。 https://beta.atcode
競プロにおけるオイラー路とその応用について - Learning Algorithms
この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラー路の構築 ・実装 ・例題 ・追加問題 ・最後に はじめに この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。 最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。 説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。 また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。 例題で扱った問題は、はまや
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
(UPD 11/15) 下の記事を書くにあたってやらかしたこととか、 返ってきた辛辣な反応を見て、いろいろ言いたくなったんですが、 自分の過ちがどんどん浮き彫りになった気がします。それはまた今度書きます。 個人的にPSP経由の解法はカットが苦手な人にはオススメだと思うので、 そういう人はぜひ試してほしいです。 次記事とか次々記事あたりは面白いんじゃないでしょうか。 - こういうツイートをした。 『昨日のARCに関してなんですが、個人的には、『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProjectSelectionの形そのものを覚えれば瞬殺だからです。だからみんな http://tokoharu.github.io/tokoharupage/docs/formularization.pdf のp7とかwikipediaのページを読んでほしい』 珍しく腹が
Late Edges [CSAcademy #54] - はまやんはまやんはまやん
https://csacademy.com/contest/round-54/task/late-edges/ N頂点の無向グラフがある。 辺には利用可能になる時間が書いてある。 最初は時間0で頂点0スタート。 各時間で必ず隣接点に移動する必要があるときに、最短何秒で頂点(N-1)に到達できるか。 N,M≦5*10^3 解説 「mi[i][j] := 頂点iに到達できるパリティがjの時の最短時間」を使って最短距離を更新していく。 パリティがjとは最短時間のパリティのことである。 時間5に頂点iにいる それにつながっている利用時間が9である辺を渡れる最短時間は？ 横の頂点と行ったり来たりすれば5->7->9でピッタリに渡れる それにつながっている利用時間が10である辺を渡れる最短時間は？ 横の頂点と行ったり来たりすると5->7->9->11で1秒遅れで渡れる つまり、パリティが一致しているか
![Late Edges [CSAcademy #54] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/73e643d09c4ac53bdf9d5d562946c00598b96b6e/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F8599973812311355105%2F1508954392)
グラフ・ネットワーク分析で遊ぶ(3)：中心性(PageRank, betweeness, closeness, etc.) - 渋谷駅前で働くデータサイエンティストのブログ
ビジネス的に重要度が高いのがこの辺の話題ではないかな？ということで、今回は中心性(centrality)の話題を取り上げてみようと思います。参考文献はいつも通りこちら。 ネットワーク分析 (Rで学ぶデータサイエンス 8) 作者: 鈴木努,金明哲出版社/メーカー: 共立出版発売日: 2009/09/25メディア: 単行本購入: 5人 クリック: 62回この商品を含むブログ (9件) を見る データセットはこれまで通り前々回適当に生成したグラフのものと、C elegansと、さらに以前使った『レ・ミゼラブル』の人物相関図を対比のために併用しようと思います。 そもそも中心性とは 『ネットワーク分析』p.41にはこんなことが書いてあります。 中心性は、ネットワークにおける各頂点の重要性を評価したり、比較したりするための指標である。例えば、交通ネットワークでは、ある地点から他の地点へ移動するための道
2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致 - komiyamの日記
蟻本に載っていた事実だけど、理解するのに時間がかかった。 まず、前段階として|マッチング| <= |点被覆|であることを確認しよう(これは一般のグラフで成り立つ)。これは、マッチングに含まれる辺を被覆するのに最低限マッチングと同じだけの点が必要だから。なので|最大マッチング|<=|最小点被覆|となる。 具体的に最小点被覆を構成してみよう。2部グラフにsinkとsourceつなげて最大流を流し、最大マッチングを作る。このとき、残余グラフでsourceから到達不可能な左側の点集合と到達可能な右側の点集合の和集合Xが最小点被覆になっている。以下ではこれを示す。 もっと具体的に考えてみよう。図のように色を付ける。最大マッチングに含まれる辺は赤。そうでなければ黒。 左から右にいくときは黒だけ通れる。右から左にいくときは赤だけ通れる。赤い辺がついていない左の点を出発点にできる。 ここで次の2つを調べて
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サンタコンペで二度全完した話
組合せ最適化でクリークを解く - Qiita
CS Academy
あるごん on Twitter: "CSAにグラフエディタがあるのを見つけた(便利そう) https://t.co/Q12vuHu6uK https://t.co/wBWzFXrGrN"