Bellman–Ford algorithm - Wikipedia
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.[1] It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.[2] The algorithm was first proposed by Alfonso Shimbel (1955), but is in
Nim - sigma425のブログ
Misere(正しくはMisère) Game とは,(多分)"最後の一個をとったら負け"みたいなゲームの事で,例えばNimに対して Misere Nimというものが考えられる. Nimの勝利条件がNimber(Grundy number)であることはwell known factだが,Misere Nimの勝利条件を知らなかったのでメモ.(2014年12月放送の頭脳王という番組に番組独自の問題として出てきた,後述) 実はNimとほとんど同じで基本的に相手にxorが0の状態を渡せばいいのだが,最後までそれをやるとこっちが負けるので,最後はちょっと変える.正確には,その状態で次に動かすプレイヤーの敗北条件は, となる. prf(の概略). 後半は自明(残り奇数個なら最後取ってしまうので). 前半はNimと一緒で,あとは前半から後半にうまく移行できるかだが,全て1以下の状態でこっちに帰ってくる
Shortest Path Faster Algorithm - PEGWiki
The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm whose origin is unknown[see references]. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the avera
SPFAの紹介 - hogloidのブログ
なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。 オーダーはO(VE)なんですが、これだけ聞くとベルマンフォードで十分です。 SPFAはqueueを使ってベルマンフォードと大体同じことをします。 始点のコストを0にしてqueueに詰み、 queueが空でない間、そこからつながっている辺について、最短距離を更新できるか考えます。(ダイクストラ法のように) また、ある頂点vがqueueに入っているかの配列を持っておき、すでにqueueに入っているなら最短距離を更新するだけです。 最短距離を更新できて、queueにないならqueueに入れます。 ちょっと想像すると、
Monte Carlo Tree Search - About
What is MCTS? Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search. Research interest in MCTS has risen sharply due to its spectacular success with computer Go and potential application to a number of other di
自動生成迷路
迷路自動生成アルゴリズム プログラムによる迷路の自動生成の解説ページです。 どちらかというと大きな迷路を生成する事に興味があり、ゲームソフトで使われる迷路とは観点が異なっています。 下記のソフトをダウンロードして実行すると、棒倒し法と穴掘り法と壁延ばし法の実際の迷路の生成動作を見ることができます。 ダウンロード（Windows用ソフト) 249Kバイト １．はじめに 自動生成迷路はの基本形は方形座標上で、各マスが壁または道から成り立っています。 このデータはプログラム上も２次元配列で簡単に作れ、各マスが壁か道かだけを覚えていればいいので、表現も簡単です。 またこれを画面に反映する際も、道や壁を適当なアイコンに置き換えればいいので、比較的簡単にゲームに使えます。 道の幅は通常１マスです。 ２．棒倒し法 棒倒し法は、比較的プログラミングの楽な迷路生成法です。 最初に基本となる四角の外壁と、その
クラスタリングによる迷路作成アルゴリズム
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
視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
Fast inverse square root - Wikipedia
Lighting and reflection calculations, as in the video game OpenArena, use the fast inverse square root code to compute angles of incidence and reflection. Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates , the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number in IEEE
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
geometry.txt
Advanced Algorithms and Applications
Site is undergoing maintenance
Site is undergoing maintenance
東京理科大、機械式アナログコンピュータ「微分解析機」を70年ぶりに再生 ～常設展示室で一般公開へ
SSSSLIDE
最適化超入門
計算量
Static hosting for Bitbucket by Aerobatic
CPUに適度に間違わせることで節電する技術
