アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
ミニマックス法 - Wikipedia
思考プログラムの基本は、局面がどの程度自分にとって有利か点数を付ける(評価する)ことである。局面の有利度を適切に評価することができれば、自分の打てる手のうち、最も評価の高い局面を出現させるような手を選択すればよいことになる。 局面に置かれている駒の位置・数などだけから算出した評価値を静的評価値、算出する関数を静的評価関数と呼ぶ。「静的」とはここでは先読みをしていないことを意味する。通常、静的評価関数だけで適切な局面評価を行うことは困難である。そのため、先読みを実現するのがこのミニマックス法である。 先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。 読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い（不利な）、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、次に出現するすべての局面の評
データ構造の選択次第で天国と地獄の差
データ構造の選択次第で天国と地獄の差：コーディングに役立つ！ アルゴリズムの基本（2）（3/3 ページ） この木何の木、木構造 「木構造（根付き木）」と呼ばれるデータ構造について説明します。リンクリストは直線的にノードがつながっているデータ構造でしたが、木構造は木のような形でノードがつながっているデータ構造です。 木構造はデータを持つノードで構成されています。 ノードの中には1つだけルート（根）というノードがあります。図にした場合、一般的に一番上に書かれます。 2つのつながっているノードを見たとき、ルートに近い方を親ノード、ルートから遠い方を子ノードといいます。 あるノードの親ノードは1つだけしかありません。子ノードは複数あります。子ノードは1つの場合もあり、1つもない場合もあります。 ルートノードには親ノードがありません。親ノードがないのはルートノードだけです。 最も末端のノードをリーフ
遺伝的アルゴリズム - 遺伝的アルゴリズム
このページでは遺伝的アルゴリズムの基礎を紹介します。 どのページも遺伝的アルゴリズムをなんの事前知識も無しで学習するのに役立つように作られています。 コンピュータプログラムに関しての少しの知識があることが前提となっていますが。 いくつかの遺伝的アルゴリズムに関するJava appletsによるデモンストレーションを見ることができます。 These pages introduce some fundamentals of genetics algorithms. Pages are intended to be used for learning about genetics algorithms without any previous knowledge from this area. Only some knowledge of computer programming is assu
ビンパッキング問題 - Wikipedia
ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。 様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。 8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べる
遺伝的アルゴリズム - Wikipedia
遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。 遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。 この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることであ
検索エンジンのアルゴリズムとは? 過去6年の変遷にみる順位決定の仕組み | Web担当者Forum
アルゴリズム検索の結果を相手に仕事をしている検索マーケティング担当者の大多数は、自分たちが少なくとも検索エンジンの「最新アルゴリズムを把握している」と主張しているし、僕がこれまでに聞いた（あるいは、そういう意味で言えば、担当した）クライアント仕事では、9割方この話が少なくとも1回は話題に上っていた。 しかし、この点については、まだ多くの点で本当のことがわかっておらず、最近SEOに手を染めたばかりの人たちにとっては、おそらく最も気の重い側面だろうと思う。 というわけで、みんなの苦労を少しでも軽くするため、しょっちゅう変わり続ける検索エンジンの検索結果算定式に、どうすれば遅れを取らずにいられるかという問題に関して、みんなが持つ共通の疑問に答えておいたほうがいいんじゃないかと思ったんだ。 アルゴリズムとは何か？ グーグル、ヤフー、マイクロソフトは、それぞれどのようにして、検索アルゴリズムを検索結
グーグル、検索アルゴリズムを少しずつ明らかに
Googleは、同社の検索エンジンの内部動作について、少し秘密にしすぎていたという結論に達した。 同社はこれまで、何を検索結果一覧の先頭に表示するかを決定するアルゴリズムについて、あえて公表を避けてきた。同社の検索品質に関するエンジニアリング担当バイスプレジデントを務めるUdi Manber氏は米国時間5月21日付けのブログ投稿で、その理由の1つは、競合他社による模倣を防止するためであり、また別の理由としてはそれを悪用するウェブサイトの出現を防ぐためであったと述べた。しかし今後は、もう少し公開していく予定である。 「完全な秘密主義を貫くのは理想的ではない。このブログ投稿は、今後はこれまでよりももう少し公開していこうという新たな決意を示すものである」とManber氏は述べている。「これからは定期的に新しい部分について語り、古い部分を説明し、アドバイスをし、情報を公開し、対話していくよう努力す
各種ゲームのプログラム解析
目次 はじめに 解析結果についての解説 ファイナルファンタジーIV ファイナルファンタジーV ファイナルファンタジーVI ドラゴンクエストV ドラゴンクエストVI ドラゴンクエストI・II ドラゴンクエストIII ロマンシング サ・ガ2 ロマンシング サ・ガ3 技術資料 ファイナルファンタジーIV ファイナルファンタジーV ファイナルファンタジーVI ドラゴンクエストV ドラゴンクエストVI ドラゴンクエストI・II ドラゴンクエストIII ロマンシング サ・ガ2 ロマンシング サ・ガ3 今後の予定 おわりに はじめに ゲームの内部で起こっている処理を推測するのはなかなか難しいものです。ユーザーサイドから見れば、ゲームの内部処理はほとんど「ブラックボックス」のようなものです。ユーザーサイドでは「(内部で複雑な処理が行われた末の)最終結果」しかわかりませんし、ゲーム中の様々な要素(各種パラメ
余剰CPU時間を使ってルービックキューブは23手以内で揃うと証明 | スラド サイエンス
3月に「ルービックキューブは25手以内で揃う！」というトピックがあったばかりですが、そのTomas Rokickiが今度は上限を一気に2手下げて23手としました。キューブフォーラムの記事によると、前回と同じ方法で、Sony Pictures Imageworksのレンダリングファームの余剰CPU時間を使い、約7.8コア・年分の計算時間をかけて、ルービックキューブのどんな状態からでも最大23手で完成できることを示したそうです。このレンダリングファームはスパイダーマン3やSurf's Upの制作に使われました。 今回の探索でも21手必要なキューブ状態は発見されていません。対称形の考察などから上限は20手だろうと予想されています。同じアルゴリズムでこれを証明するには、3500コア・年のCPU時間が必要になるとRokickiは見積っています。さらに速い探索手法が考案されるのが早いか、ムーアの法測で
いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
video blog ãã¼ã ãã¼ã¸ å¶ä½ it at pj-blog.net
Video Blogãã¼ã ãã¼ã¸ å¶ä½It æ±äººãã¼ã Pcã¦ã§ã ãã¶ã¤ã³ãã½ã³ã³ 販売ãã¼ã ãã½ã³ã³ãã½ã³ã³è³æ ¼ Itãã¼ã ãã¼ã¸ 製ä½ãã½ã³ã³ é販 ãã¹ãã£ã³ã° ãµã¼ãã¹Pc ã»ãã¥ãªãã£It ã¹ã¯ã¼ã«ãã¡ã¤ã³ãã¼ã ãã¼ã¸ å¶ä½ ä¼ç¤¾Web ãã¶ã¤ã³
Javaによるアルゴリズム辞典
奥村晴彦， 首藤一幸， 杉浦方紀， 土村展之， 津留和生， 細田隆之， 松井吉光， 光成滋生 『Javaによるアルゴリズム事典』 （技術評論社，2003年，ISBN4-7741-1729-3，2580円＋税） のサポートページです。 技術評論社の Javaによるアルゴリズム事典 のページ ソースコードのダウンロード 00README.txt java-algo.zip (約320K，Shift JIS / CRLF) java-algo.tar.bz2 (約130K，EUC-JP / LF) 更新記録 [2003-05-09] 公開 [2003-05-12] BDCbrt.java, BDSqrt.java, BDtoE_Form.java, BinarySplitE.java, BinarySplitPi1.java, BinarySplitPi2.java のコメントを修正しました [
今からでも遅くない！アルゴリズム入門---目次
高速なハードウエア，至れり尽くせりのユーザー支援機能を備えた開発ツール，高機能なクラスライブラリやフレームワークなどなど，近ごろのプログラムを書くためのお膳立ては，とても充実しています。しかし，どんなに環境が整っても，ソフトウエアを作るには何らかのアルゴリズムに従って問題を解きほぐし，プログラムにするという作業が相変わらず必要です。 そこで本特集では，まずPart1で身近な例からアルゴリズムというものに迫ってみます。皆さんが普段接している便利なソフトやサービスがどのような仕組みで動いているのか，その仕組みをのぞいてみましょう。教科書で勉強するようなアルゴリズムの話とはちょっと違うものも出てきます。中には，サービスの重要な要素をプログラムで処理せず，手作業に頼って実現しているものもあります。実用ソフトの世界で本当に使いやすいものを作るには，アルゴリズムだけわかっていてもダメなことが少なくない
Mastering Algorithms with Perl : 404 Blog Not Found
2006年11月02日19:00 カテゴリ書評/画評/品評 Mastering Algorithms with Perl 定番アルゴリズムを徹底理解！：ITproが もブクマされておりますが、それよりもこちらの方がおすすめ。 Mastering Algorithms With Perl J. Orwant / J. Hietaniemi / J. MacDonald 以前404 Blog Not Found:Hash != Associative Arrayでもちょこっと紹介しましたが、ここで改めて紹介しておきます。 本書"Mastering Algorithms with Perl"には「定番アルゴリズムを徹底理解！」のアルゴリズムは全て載っている上、それぞれのベンチマークもちゃんと取ってます。"with Perl"とありますが、Perl色はそれほど強くないので、他のLLのユーザーにも役
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Diary of Sacred Fox - January 25, 2003 - The Quintet
「アルゴリズムを知らない子ども達」の補足(?) - val it : α → α = fun
NaokiTakahashiの日記 - 乱数について
Rogue Engineer's Diary / やさぐれ日記(2005-11-13) / 「アルゴリズム＋データ構造＝プログラム」？ 本当に？