[Ruby] フォード・ファルカーソン法でネットワークの最大フローを求める - うなの日記
フォード・ファルカーソンのアルゴリズム で、ネットワークの最大フローを算出してみます。 最大フローとは 以下のようなそうめん流しシステム(=ネットワーク)があるとします。 「→」は「竹とい」を示します。「○」は、「竹とい」の接点。 「→」の横の数値は、1分間に転送可能なそうめんの量を表します。 このシステムで、「1分間に 任意の二点間(例: a→f) に転送可能な最大そうめん量」が「最大フロー」となります。 ネットワークのデータ構造 例によって、構築と探索に必要な最低限の機能のみ用意。 Networkは、頂点(Vertex)と、頂点と頂点を結ぶ辺(edge)を持ちます。 各辺は「capacity」フィールドで最大転送量を持ちます。 各頂点は、頂点から出る辺(=edge.fromが頂点の辺 =前進辺)の集合(forward)と、頂点に入る辺(=edge.toが頂点の辺 =後退辺)の集合(ba
![[Ruby] フォード・ファルカーソン法でネットワークの最大フローを求める - うなの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/5fd98aa666c37c5661158e965f09a454fbc51b3e/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fu%2Funageanu%2F20110822%2F20110822135548.gif)
GPUによる数値計算
1．はじめに 2．GPU 3．GPGPU 4．CUDA 5．特異値分解 6．QR 分解 7．実験 8．考察・課題 近年のグラフィックスプロセッサ（以下 GPU）の性能向上は著しく理論ピーク性能が 500GFLOPS を超えるまでに成長している（図１）．GPU は本来グラフィックス処理専用のハードウェアであったがその処理能力の高さから汎用処理向けの研究が盛んに行われている． 一方，データマイニング，画像処理など広い分野で利用される数値線形代数アルゴリズムに特異値分解がある．各分野において扱う問題の大規模化に伴い，高速な実装が強く求められている． 本研究は現在データマイニングの分野などで需要の高い特異値分解をGPUによって高速化することを目的とした実験を行なった． ほとんどの GPU のハードウェアは現在 NVIDA 社と AMD 社の２大メーカによって作られている．GPU
マージ・ソート : 巨大データのソート法
はじめに まずはともあれ腕試し、この問題を解いてみてくださいな: 【問1】 デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。 ※各文字列は改行で区切られています。 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ: using System; using System.IO; using System.C
そのアルゴリズム、貪欲につき――貪欲法のススメ
そのアルゴリズム、貪欲につき――貪欲法のススメ：最強最速アルゴリズマー養成講座（1/3 ページ） アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。 動的計画法は本当に万能なのか？ 本連載ではこれまで、かなりの文量を割いて動的計画法について説明してきました。動的計画法はさまざまな問題で有効な解決手段ですが、動的計画法が使えるからといって、常に動的計画法を利用することが正しい選択である、というわけではありません。この理由は簡単で、動的計画法は計算量を大幅に削減できますが、その本質は、不要である要素を切り捨てることで問題全体を見渡すというアルゴリズムであるためです。 ここで問
Super Technique 講座～ザ・レトロ・アルゴリズム「コントロールブレーク」by OOP
以前書いた「バイナリサーチ」徹底解説の続編みたいなものである。筆者はこのところ、業務プログラムを書き倒しているのだが、その時に結構頻繁に遭遇するちょっとした問題を解決するにあたって、同僚たちがあまりうまいやり方を知らない....というのを、少し気にしているのである。その問題とはこういうタイプのものだ。 データベースのあるテーブルが、実際には階層構造になっているにも関わらず、フラットに定義されているために、実際に欲しい階層データを構築するのに何回も SQL を呼んでいる....サブキーを考慮して order by してやれば、正しい順番で１回で取れるのにねぇ... そういうデータで、階層ごとに合計が欲しいんだが、Map を使って合計やってるぞ...これも Map とか使わずに、１回ループさせるだけでできるのにね.... という問題だ。これ要するに、階層データがベタな SQL のテーブル１個で
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ページが見つかりません | 日本HP
大量データや新社会インフラを支える注目の技術「ストリームデータ処理」とは？