知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
コンピュータグラフィックス特論Ⅱ 講義情報ページ
レポート課題 レポート課題は、講義に合わせて公開する。 レポートは、授業用Moodle の「コンピュータグラフィックス特論II （2020）」コースから提出すること。 LaTexテンプレートを使用してレポートを作成することを推奨する。 本テンプレートでは、プログラムリストを含めるために listings, jlisting パッケージを使用している（要インストール）。 第1回 視点操作 第3回の授業のサンプルプログラム（view_sample.cpp）に、以下の処理を追加したプログラムを提出せよ。 Scrollモード（媒介変数） Walkthroughモード（直接更新） Scrollモード（直接更新） Walkthroughモード（媒介変数） レポート課題 テンプレート [LaTex] [PDF] 第2回 影の描画 第5回の授業のサンプルプログラム（shadow_sample.cpp）に、
３点の座標から簡単に角度と回転方向を求める．(2・3・N次元，外積を用いる方法)
S ≡ (Px - Cx) * (Qy - Cy) - (Py - Cy) * (Qx - Cx) とする．S＞0 なら左回り，S＜0 なら右回り，S＝0 ならば C，P，Q は一直線上にある．(注) なお，この判別方法は，CP と CQ が同じ長さである必要はない． θを求めたい場合はこちらへ． この問題を見て，逆三角関数 tan-1 (Ｃ言語では atan() や atan2()) を使って CP と CQ の角度をそれぞれ求め， 両者を比較しようと考えた方が多いのではないでしょうか． しかしこの問題では，角度そのものではなく角度差の符号を求めればよいので， 逆三角関数を使う方法よりも簡単で優れた，外積を使う方法を紹介します． ２つの２次元ベクトル A＝(Ax, Ay), B＝(Bx, By) の外積を次のように定義する． A × B ≡ Ax * By － Ay * Bx ここで O
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
分布推定アルゴリズム - yukobaのブログ
分布推定アルゴリズム。遺伝的アルゴリズムを改良した物です。個体の集合を交叉・突然変異させるのではなく、個体の生成確率を進化させます。最適化問題のアルゴリズムです。以下、自分へのメモです。わかったことが増えたら追記するかも。 ビットストリング 計算量に関しては、ビット数をn、反復数をTとしています。 Population-Based Incremental Learning (PBIL) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108 Population-ba
diffのアルゴリズム - Plan9日記
ふと見つけた「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」を読んで、diffのアルゴリズムを調べてみた。2つのファイルの違いを見つけるには、共通する部分が最長になるペアを見つければよい。これはLCS (Longest Common Subsequence)問題と呼ばれる。LCS問題の最適解は動的計画法を用いて求めることができるが、計算時間、メモリ使用量ともにO(MN)になる*1。これより早く、また小メモリで実行できるようにいろいろなアルゴリズムが提案されている。 テキストを比較するdiffというUnix系のコマンドがありますが、これは実は高度に数学的なエディットグラフというアルゴリズムが使われています。 [1] E.W.Myers, "An O(ND) difference algorithm and its variations"
グレゴリオ暦／ユリウス暦 ⇔ ユリウス日 (または一般の通算日数) 変換アルゴリズム
●お知らせ グレゴリオ暦／ユリウス暦計算用Ｃ言語のソースコード・ ライブラリ Calendrier を販売しています． (\1,000 (個人用ライセンス) ほか) Calendrier リファレンス (Ver.1.0) 公開しました． このページの主な更新は Blog でお知らせします． このページでは， グレゴリオ暦またはユリウス暦の日付と，ユリウス日などの通算日数 (通日) を相互変換するアルゴリズムについて説明する． これらは1989年頃に自分で考えたアルゴリズムを再度整理したものである． 一応「ユリウス日」と書いてはいるが，これは通算日数の代表として挙げているだけであり， 基準日注１ (通算日数の第０日とする日付，epoch) は自由に選択できるので，ユリウス日 (Julian Day，JD) や 修正ユリウス日 (Modified JD, MJD) 以外にもさまざまな通算日数を
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
Mathematics and Computing - Martin Baker
This site looks at mathematics and how it can be computed. The name of the site 'EuclideanSpace' seems appropriate since Euclid made one of the first attempts to document and classify the mathematics known at the time. We now know, through the theorems of Kirt Gödel, that there is no definitive way to classify mathematics so the organisation here is arbitrary in some ways and reflects my own inter
3DCGプログラミング - FreeStyleWiki
初歩の初歩から「3DCGとは？」と言ったことを説明していきます。 3Dの仮想的な世界を「シーン」と言ったりしますが、これをとある視点からとある方向を見て「２次元の絵」として描画することを「レンダリング」と言います。 シーン内には以下のような要素が存在しています。 視点 自分自身がいる位置と向いている向き、スクリーンのサイズ（幅と高さ）、視野角度などを持ちます。「カメラ」とも言います。 光源 呼んで字のごとく、光の元となる要素です。良く知られているものとしては、「平行光源」（Shadeで言う無限遠光源）、「点光源」「スポットライト」があります。これらは光源としての大きさを持ちません。これを拡張したものとしてはエリアライト（面光源）があります。エリアライトは、面積を持っています。その他、線光源・物体自身を発光させて光源にしてしまう、など、いうなれば何でも光源にできてしまいます。 物体 「オブジ
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
四元数で回転 入門
★このページの対象読者 三次元での回転を、ＣＧとかで定量的に取り扱いたい人 オイラー角(Euler Angles)を使っていたら、わけがわからなくなってきた人 カルダン角とオイラー角(Cardan Angles)の見分けが付かない人 ジンバルロックに困っている人 だけど、数学とかメンドクサイことが嫌いな人 サンプルプログラムが欲しい人 ★回転篇： 四元数（しげんすう, quaternion）を使った回転の取り扱い手順だけ説明します （１）四元数の実部と虚部と書き方 四元数とは、４つの実数を組み合わせたものです。 ４つの要素のうち、ひとつは実部、残り３つは虚部です。 たとえば、Qという四元数が、実部 t で虚部が x, y, z から成り立っているとき、下のように書きます。 また、V = (x, y, z)というベクトルを使って、 Q = (t; V) とも書くことがあります。 正統的
第1回UEC杯５五将棋大会(UEC55-2007)公式サイト
このサイトは、通常の将棋をコンパクトにした「５五将棋」というゲームと電気通信大学５五将棋大会を広く知っていただくために開設されたサイトです。 ５五将棋については５五将棋のルールのページを、５五将棋大会については、大会概要のページをご覧ください。 将棋には、９×９の通常の将棋のほかに、様々な亜種のゲームが存在します。 歴史的に見ると、「中将棋（１３×１３の大きな将棋）」や「平安将棋（飛車角がない将棋）」のような将棋が遊ばれていた時期があることが知られています。色々な将棋の亜種が混在していた時期から、現在の将棋が最も親しまれ、普及してきたものと思われます。 近年でも、新しい将棋の亜種が生まれる機運はあります。「四人将棋（四人で対戦する将棋）」や「取る一手将棋（取れる駒があれば、必ず取らなければならない将棋）」など、通常の将棋以外のルールで遊ぶゲームが生まれています。５五将棋は、その亜種の将棋ゲ
高速フーリエ変換 Excel VBA用FFTプログラム - 研究と教育と追憶と展望
ちまたには高速フーリエ変換（FFT）のプログラムが出回っているが、これをExcel VBA（いわゆるマクロ）で使えるようにしたところ、机上作業の効率が飛躍的にアップした。下記にプログラム等をノートしておく。ちまたに出回っているFFTのプログラムは利用者の知らないうちに窓関数がかけられていたり、周波数を自動的に計算したりするので、あまり教育的ではない。一番シンプルなFFTのプログラムで、生の処理を体験すべきである。 ちなみに、フーリエ変換とは、理工系の大学で習う数学的処理の方法の一つで端的に言えば、横軸が時間となっているグラフをフーリエ変換すると、横軸が周波数のグラフとなるもの。 例えば左図は横軸が時間で、周波数の異なるサインカーブを３つ足し合わせたグラフである。0.001秒毎に（サンプリング周波数1 kHz）、1024個のデータを取得したもの。横軸が時間だと、この波の周波数を読み取るのに一
tips - MD5のコスト : 404 Blog Not Found
2007年03月27日23:30 カテゴリTips tips - MD5のコスト 同一ファイルかどうかを調べるのにMD5を使うというのは、比較するファイルが両方手元にある場合はおすすめ出来ません。 重複ファイルを消すPythonスクリプト 「ファイル名が違っても中身が同じファイルを探してくれる『NoClone』 | P O P * P O P」と 「404 Blog Not Found:perl - File::Find::Identical」にインスパイヤされた話ですが、 プログラム自体は数年前にPerlとmd5sumで書いて、 去年Pythonで書き直しました。 ダウンロードはこちら。その一番の理由は、コストです。 ファイルどおしの単純比較の倍以上します。 以下は、FreeBSD 6.2、Xeon 2.66GHz x 2、400GB ATAPI 7200rpmにおいて、FreeBSD
今日の井原.
オープンソースな画像解析ライブラリであるところのOpenCVには、顔認識の機能がある。これの使い方を簡潔にメモしておく。 ダウンロードはここから。複数のバージョンが提供されているが、ここではbeta5というのを選ぶ。また、Windows版とLinux版が提供されているが、ここから先は、Windows版を用いた場合のやり方を書いていく。 OpenCV_b5a.exeのダウンロードが完了したら、実行してマシンにインストールする。インストールでは、特に迷う箇所はないだろう。以後の説明は、デフォルトのパス(C:\Program Files\OpenCV)にインストールしたものとして書いていく。 インストールが終わったら、"C:\Program Files\OpenCV\bin"にパス(環境変数のPATH)が通っているかを確認する。通っていなければ通しておく。 OpenCVには、インストール
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
プログラム・プロムナード
会誌「情報処理」連載の「プログラム・プロムナード」（2002年4月〜2005年3月掲載）と「Haskellプログラミング」（2005年4月〜2006年3月掲載）はどなたでもご覧になれます。ファイルはすべてPDF形式です。 「Haskellプログラミング」に掲載されたプログラムは http://www.sampou.org/haskell/ipsj/ から取ることができます.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.jaist.ac.jp/~t-nakada/