ナンバープレース(数独）
ナンプレ（ＮｕｍｂｅｒＰｌａｃｅ）も有名なパズルですので、ルールの説明は割愛します。 ナンプレは、Hand Ｓｏｌｕｔｉｏｎ向きのパズルです。ナンプレの問題そのものをコンピュータで解くのは簡単ですので、あまり面白くありません。 ここでは、皆さんも一度は気にされた事があると思われる以下の話題を扱ってみます。 （１） 解法アルゴリズム 一般的な解法は、試行錯誤を用いたアルゴリズムでしょう。 しかし、答えは、ユニークになるのにどうして解法アルゴリズムには試行錯誤が必要なのでしょうか？ 確定的な解法アルゴリズム（試行錯誤を用いないで解く方法）は存在しないのでしょうか？ （２） 作図問題 枠だけを指定されたとき(枠の数とその位置）、その枠の数字をきめてナンプレの問題を完成させるという問題です。（これがうまくいくと、好みのレイアウトのナンプレ問題が簡単に作れてしまいます） 例えば、以下のような問題は作
画風を変換するアルゴリズム - Preferred Networks Research & Development
Deep Neural Networkを使って画像を好きな画風に変換できるプログラムをChainerで実装し、公開しました。 https://github.com/mattya/chainer-gogh こんにちは、PFNリサーチャーの松元です。ブログの1行目はbotに持って行かれやすいので、3行目で挨拶してみました。 今回実装したのは”A Neural Algorithm of Artistic Style”(元論文)というアルゴリズムです。生成される画像の美しさと、画像認識のタスクで予め訓練したニューラルネットをそのまま流用できるというお手軽さから、世界中で話題になっています。このアルゴリズムの仕組みなどを説明したいと思います。 概要 2枚の画像を入力します。片方を「コンテンツ画像」、もう片方を「スタイル画像」としましょう。 このプログラムは、コンテンツ画像に書かれた物体の配置をそのま
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
どう書く？org お題の一覧
文字列で＋を表示する number of comment: 34 評価3/3=1.00 年賀はがきの当せん番号 number of comment: 1 評価-8/8=-1.00 箱詰めパズルの判定 number of comment: 12 評価2/2=1.00 関数やメソッドのソースの平均行数 number of comment: 3 評価0/0=0.00 コレクションの実装 number of comment: 2 評価-4/4=-1.00 居眠り床屋問題 number of comment: 19 評価0/0=0.00 化学反応式の完成 number of comment: 6 評価1/3=0.33 復活 number of comment: 7 評価0/0=0.00 UTF-16をUTF-8に変換 number of comment: 9 評価0/0=0.00 シードを固定した乱
In-placeアルゴリズム - Wikipedia
in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。 in-place とは「その場で」といった意味であり、入力が出力で上書きされることが多いことから来る用語である。 in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。 in-placeの定義にはやや揺れがある。最も狭義にはポインタなども含めて一定の空間しか使用しないアルゴリズムを指す。しかし長さnの配列の添字を表すだけでも O(log n) の空間を必要とするため、この意味で in-place であるアルゴリズムはごく限られている。多くの場合、 O(log n) の空間を使うことが許される。より広く O((log n)const.) 程度まで認めることもあり、時には o
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
文字列データ圧縮ことはじめ | SlideShare
2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
麻雀ゲームが弱い理由（と羽生２冠が強い理由）～読みと見切り編～ - マッタリプログラミング日誌
先日の記事が割と評判が良かったようなので、続きを書いてみたいと思います。 前回は、局面の数に着目して麻雀の難しさについて書きましたが、今回は読みと見切り（探索と枝刈り）について紹介したいと思います。 将棋の場合：MIN-MAX法 将棋やオセロのようなゲームは、情報科学的には２人零和完全情報確定交互ゲームに分類されますが、このタイプのゲームではmin-max探索という先読みとαβ法という見切り（枝刈り）が有効であることが分かっています。 次の図のような感じです。 今、Ａという局面で先手の順番です。このとき先手にはＢ，Ｃという２つの手が考えられます。 先手がＢを指すと後手はＤとＥの２つの手が考えられ、先手がＣを指すと後手にはＦとＧという手が考えられます。 Ｄ～Ｇに書いてある数字はその局面で先手番からみた局面の有利さ（形勢判断）を数字化したものです。先手は出来るだけ数字が大きい局面に誘導したいで
untitled
概要 探索 • 逐次探索 • ２分探索 • 探索とデータ管理 – ２分探索木 – 平衡木 (Balanced tree) ここ 探索木と効率 ２分探索木 探索、挿入、削除の効率は木の形状に依存する 平衡木 最悪の場合が生じないように木を構成する バランスのとれた木構造 – – – – 平衡2分木 ( AVL木 ) 2-3木 2-3-4木 ( トップダウン2-3-4木 ) Red-Black 木( 2色木、赤黒木 ) ＊AVL木 : Adel‘son-VelskiiとLandis が提案した木 平衡２分木、 2-3 木 平衡２分木 ( AVL 木 ) バランスのほぼとれた２分木 – 子の個数が１以下のノードのレベルの差が１以下 レコードの挿入、削除時にバランスをチェック バランスがとれていなければ、木の形状を修正 2-3-4木、Red-Black木 2-3-4木 子ノードの個数が４個
Red–black tree - Wikipedia
In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary search trees, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising th
赤黒木 - Wikipedia
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nは木の要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。 この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree
ダイクストラ法
nには頂点数、dist[x][y]には、x→yの辺があるところにはその長さ、無いところは＋∞を入れておきます。実際に＋∞という記述は使えないので、具体的な値を設定します。全ての辺の長さの合計より大きければ問題無いでしょう。ただ、int型の場合あまり大きいと加算したときオーバーフローしてしまうので、２つ足してもOFしない10億くらいがよいでしょう。 この関数dijkstraを実行すると、cost[x]に目的地gまでの最短距離が入ります。xから目的地gまでいけないときは＋∞のままになります。 ちなみに、dijkstraは綴りミスじゃありませんよ。念のため。 #define INF 1000000000 int n; int dist[100][100]; int cost[100]; char used[100]; void dijkstra(int g) { int x, y, min; f
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
ダイクストラ法による最短ルートの求めかた
ダイクストラ法が何かを解説すると余計に難しくなるので省略しますが、 ダイクストラ法アルゴリズムを使う最大のメリットは、 「不要な経路が分かった時点で以降の計算を省略できる」 これに尽きます。 ではさっそく。一つ例を説明していきましょう。 さきほどの図です。スタート点をA、ゴール点をFとします。 青い数字は、それぞれの点間の移動に要する距離です。 ■Aの一つ隣の点を調べます Aの隣はBとCです。 BとCの各点にAからの検索がきたこと、そしてスタート地点から移動に要した距離をセットします。 両方とも「Aの10」になりますね。 さて次はAの隣、BとCについて調べていきましょう。 ■Bの一つ隣の点を調べます Bの隣はA,C,Dです。 Dにはこれまでと同じ方法で「Bの18」をセットできます。 ここからが大事なところです。 BからCへ向かうルートをたどるとき、Cはすでに一度探索が行われています。 Cが
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 概要[編集] A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際
ダイクストラ法 - Wikipedia
ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 概要[編集] ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 ほかのアルゴリズムとして、 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【またかよ】「Haskellでクイックソート」問題【何度目だ】
どう書く？org
サービス終了のお知らせ