SPFAの紹介 - hogloidのブログ
なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。 オーダーはO(VE)なんですが、これだけ聞くとベルマンフォードで十分です。 SPFAはqueueを使ってベルマンフォードと大体同じことをします。 始点のコストを0にしてqueueに詰み、 queueが空でない間、そこからつながっている辺について、最短距離を更新できるか考えます。(ダイクストラ法のように) また、ある頂点vがqueueに入っているかの配列を持っておき、すでにqueueに入っているなら最短距離を更新するだけです。 最短距離を更新できて、queueにないならqueueに入れます。 ちょっと想像すると、
クラスタリングによる迷路作成アルゴリズム
Japanese / English はじめに クラスタリングとは アルゴリズム 迷路作成アルゴリズム 迷路作成例 Rubyによるサンプルコード はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 注意：ここで言う「クラスタリング」は同値関係をつなぐもので、 データ解析で良くでてくるクラスタリング、つまり情報空間上に散らばっているデータ点を 適当に似ているもの(近いもの)同士で分類する手法ではありません。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループは
木(tree)で遊ぶ - 連載 Haskellプログラミング（『情報処理』46巻5号 2005年5月）
46 5 2005 5 564 n 1 4 4 -1 5 n data data DumbTree = Empty | Fork DumbTree DumbTree data DumbTree Empty ( ) 2 DumbTree Fork nobsun@sampou.org IPSJ Magazine Vol.46 No.5 May 2005 565 DumbTree ( ) Empty Fork ( ) -- trees (>0)DumbTree trees :: Int -> [DumbTree] trees 1 = [Empty] trees n = concat [ joins ls rs | (ls,rs) <- [ lrs xs ys | (xs,ys) <- splits1 n ]] -- splits1 (>0)(>0)2 splits1 :: Int -> [(In
PROJECT LOP
プロジェクトのあらまし ＪＲの最長片道きっぷのルートを自力で求める 募金により実際に最長片道きっぷを買い、旅行する 旅行のようすをほぼリアルタイムで報告する プロジェクトの総括を「プロシン」で発表する 余った募金で「四国最長片道きっぷ」を買い、旅行する プロジェクトの産物 PROJECT LOP Report（実乗の記録） 最長片道きっぷ奮闘記（コンピュータサイエンス誌「bit」2001年２月号掲載） 最長片道きっぷ −理論と実践−（2001年プログラミング・シンポジウム発表、 共同研究者あり）→「山内奨励賞」を受賞 毎日新聞夕刊に掲載（2000年10月14日） 「だから LOP って何やねん」というあなたへ。LOP は Longest One-way ticket Problem の略です。実はさらにオチがあるんですけどね。 最長経路の導出過程をトレースした人には分かります。 Index
External Memory - FC2 BLOG パスワード認証
ブログ パスワード認証 閲覧するには管理人が設定した パスワードの入力が必要です。 管理人からのメッセージ 閲覧パスワード Copyright © since 1999 FC2 inc. All Rights Reserved.
ALENEX'14 に論文採択 - iwiwiの日記
国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです． 今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'
蟻本P191 最大流 - 最小カット定理 - WARush
蟻本に載ってることそのまま書くだけ 蟻本の最大流で使われたグラフをそのままサンプルで使います。 ↓↓ グラフのカットとは、ある頂点集合Sに対して、Sから出ていく辺の集合の事をいい、 カット(S V/S)のように表します。また、その辺の容量の和をカットの容量といいます。 さらに、Sの中にsを、V/Sの中にtを含むようにカットすることを、 s-tカットといいます。 最小カット問題とは・・・ ネットワークにに対して、sからtへのパスが存在しなくなるために（つまりs-tカットで） 除去しなければいけない辺の容量の和の最小値はどれだけか という問題である。 フロー流量とカット容量の関係 まず、任意のs-tフロー f と任意のs-tカット(S, V/S)を考えてみましょう。 ↓こんなフローとカット↓ sについては( fの流量 ) = ( sから出る辺の流量 )であり、 それ以外のSの頂点vについては(
グラフ理論（Graph theory） - kanetaiの二次記憶装置
(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重グラフ(multigraph) : 多重辺(multiple edges)または自己ループ(roop)を含むグラフ ※多重辺やループのない多重グラフをグラフと定義している。 部分グラフ(subgraph) : induced subgraph : 両端点がにある辺を全てが含むならば、をによって生成された(generated)部分グラフと呼ぶ。 次数(degree) 次数(degree) : に接続する辺の個数 孤立点(isolated vertex) : 次数0の頂点 の倍数
TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism - torus711 のアレ
概要 N 人の市民がいて、それぞれの友達関係が与えられる。 友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民（友達同士でなくてもよい）の所持金の差の最大値はいくらになるか求めよ。 解が無限大になる場合は -1 で示せ。 解法 友達関係をグラフとして考えます。 このとき、全体が連結でない場合は異なるグループ間で所持金をいくらでも離すことができるので解はありません。 解が存在する状況下で解を得る方法について考えます。 辺の重みを 1 とすれば、距離 1 について d だけ所持金の差を広げることができます。 また、ある市民からある市民へのパスが二つ以上存在する場合、最短でないものを採用すると最短パスで辿ってきた場合の所持金の差が d を超えてしまうので、採用されるパスは最短経路のみであることがわかります。 最低の所持金額をもつ市民を一人仮定
推移関係 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Transitive relation|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
SRM580 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし
Beam search - Wikipedia
Beam search with width 3 (animation) In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is a modification of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, onl
First improvement of fundamental algorithm in 10 years
*Terms of Use: Images for download on the MIT News office website are made available to non-commercial entities, press and the general public under a Creative Commons Attribution Non-Commercial No Derivatives license. You may not alter the images provided, other than to crop them to size. A credit line must be used when reproducing images; if one is not provided below, credit the images to "MIT."
様々な全域木問題
1. 2013 年 3 月 20 日 ＠ NTT DATA 駒場研修センター 第 12 回日本情報オリンピオック春季トレーニング合宿 様々な全域木問題 前原 貴憲 (@tmaehara) 国立情報学研究所 2. 自己紹介 • 前原 貴憲（まえはら たかのり） • Twitter: @tmaehara • Web: http://www.prefield.com (Spaghetti Source) • 略歴： 2004 沼津工業高等専門学校卒 2007 東京大学 工学部 計数工学科卒 2012 東京大学大学院 情報理工学系研究科卒 現在 国立情報学研究所 • 専門分野：連続・離散最適化，数値計算 2/ 71
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
一段階在庫管理（single stage inventory control）
WUPC2nd E問題
グラフ理論の紛らわしい言葉
Artificial Intelligence/Search/Heuristic search/Beam search - Wikibooks, open books for an open world
Site Under Maintenance
PathFinding.js