しっかり学ぶ数理最適化 ヒューリスティック編 - Qiita
これはどんな記事? 本記事は、私がヒューリスティック関連の知識をまとめることになった際に作成したJupyter Notebookを、Qiitaの記事へと改変したものです。 前提としてこれは梅谷俊治先生の「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」という本(以下、教科書と表記)の内容に準拠しています。 そしてその内容の多くは、ありがたいことにネット上の様々な形で公開されており、梅谷先生によるスライド1やスライド2、日本オペレーションズ・リサーチ学会(以下、ORと表記)での記事1や記事2、そしてORの他の方の記事1や記事2などでも類似した内容を見ることが可能です。 (そしてそれ故に、本記事を公開させて頂いています。流石に本家の方がネット上で公開されていない内容を書くのは、例え権利的に問題がないとしても気が引けるので……) また、この記事は、それらの内容を踏まえた上で、私がネット上の様
「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム― – Ono Laboratory
はじめに 最近，「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました（東北大学の江藤宏先生，九州大学の木谷裕紀先生との共同研究．国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表．2021年12月30日現在，pdfはここから取れます）． これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき，かつそれを一般化した場合，どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析したものです．今回「最適化技術の応用・実践」に関する記事を集めよう，ということになりましたので，ちょうどよい題材ということで，この研究をより一般向けに解説してみようと思います．一般向けですので証明自体には踏み込まず，既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします．ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象とし
エラトステネスの篩の高速化 - Qiita
世の中に多くあるエラトステネスの篩の実装、多くあるくせにちょっとしか高速化してないのが悲しいので高速化エラトステネスの篩を書いてみることにします。 エラトステネスの篩の高速化 (1) ← 今ココ エラトステネスの篩の高速化 (2) エラトステネスの篩の高速化 (3) エラトステネスの篩の高速化 (4) エラトステネスの篩の高速化 (5) エラトステネスの篩の高速化 (6) エラトステネスの篩の高速化 (7) 問題設定 とりあえず C++11 くらいで動く物を作りたいと思います。インラインアセンブラや SIMD、並列化は明示的には入れない方針です。あと、エラトステネスの篩自体の高速化を目指すので、結果は一部の具体的な素数の確認と $\pi(x)$ の値で確認することにしますし、その時間は考慮しないことにします。 また、ライブラリ的に使えるよう、将来的には区間篩 (大きな $x$ に対して $
機械学習の有益な書籍情報を共有します - EchizenBlog-Zwei
機械学習の有益な書籍情報を共有します。 初心者向け 最初に読む本としては「オンライン機械学習」「フリーソフトではじめる機械学習入門」「言語処理のための機械学習入門」がオススメです。 「オンライン機械学習」は3章までが入門的な内容になっています。4章以降は発展的な内容なのである程度力がついてからが良いです。オンライン機械学習という分野は実装が簡単で実用性が高いので最初に取り組むのに適しています。 広い範囲で機械学習を概観したい場合は「フリーソフトではじめる機械学習入門」がよいです。こちらは全体像がつかみやすい反面、数式の展開がわかりにくい箇所がちらほらあるので適当なスルー力が必要とされます。 「言語処理のための機械学習入門」はやや実装よりの本です。数式をみるより具体例をみたほうがわかりやすい、という人はこの本が良いと思います。 数学 何をやるにしても基礎体力は大切。数学の理解が深まれば深まる
何回で満点とれる？【ちょまど問題に挑む人々】
@chomado さんの「社内のセキュリティ研修のテスト(4択全10問)」を満点をとるまで延々とやらされる場合に何回やり直せば満点を取れるかという問題に立ち向かった人々の記録です。 ■ちょまど問題（引用・加筆） 4択問題10問のテストを全部埋めて提出すると正解数がわかります。 何回提出すればすべての正解を知ることができますか。 続きを読む
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
多腕バンディット問題とUCB解説
以下は登場する数式を(なるべく)直感的に(厳密性をけっこう犠牲にして)解釈したもの。数式多め。簡単のため台は２個とします（K=2）。 補足１ 収入をxとして、期待値がベストな台の収入の確率分布を、ベストでない適当な台iの収入の確率分布をとします。 このとき分布をもつベストな台があたかもベストでない台であるかのような振舞いを示す確率というのは漸近的に で与えられるという理論があります（大偏差原理。Dは相互情報量で、分布から見た分布の「遠さ」を表す）。 さて現状で平均収入がベストだったのが台0だったとして、そのプレイ回数を、(理論的な)期待値をとします。また、もう一方の台1のプレイ回数を、期待値をとします(基本的には平均収入が多い台をプレイしていくため)。ここで「台1が実はベスト」ということの「確率」はどれくらいか？ということを考えてみます。 台１に比べて台０は十分試行回数が大きいため、台０は
10兆までの素数リスト - 雷雲の変奏曲
プログラミングコンテストチャレンジブックを読んでいたら、素数リストの作り方が出てきた。 そういえば、１０兆までの素数リストを作ってみる、なんて記事があったな。 これだ http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/?ST=develop 読み返しているうちに、ついつい挑戦してみる気になってしまった。 色々試して意外だったのが、10億までの素数をリストアップした場合でも「試し割り」より「エラトステネスの篩」の方が100倍以上も高速だったことだ。リストが大きくなればその差はますます開いていく。 メモリ上の広い範囲をまんべんなくアクセスするエラトステネスの篩は、実際には効率が悪いのではないかと思ったりしたのだが、見当が外れてしまった。 考察してみるに 試し割りは意外と無駄が多い。まず素数の密度だがn/log(n)に従うらし
God's Number is 20
R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U Superflip, the first position proven to require 20 moves. New results: God's Number is 26 in the quarter turn metric! Every position of Rubik's Cube™ can be solved in twenty moves or less. With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown tha
C - で素数を数え直したら、範囲10億で10秒切ったお : 404 Blog Not Found
2010年07月28日01:30 カテゴリMath C - で素数を数え直したら、範囲10億で10秒切ったお というわけで数え直したら… 404 Blog Not Found:C - で私も素数を数えてみた はてなブックマーク - mohnoのブックマーク「Core i7 な iMac で、10億の範囲を検索するのに1プロセス300秒前後」←遅いってこと？ エラトステネスのふるいで、原田氏の記事でも10億なら2分（Core i7 920）、私の手元では20秒（Core 2 Duo E6850）だったんだけど。 10秒を切ってしまったので。 次にアルゴリズムであるが、いろいろいじってみた結果こうした。 まず p < 256 な小さな素数でエラトステネスのふるいにかけ 次にMiller-Rabin素数判定法を適用する これは「個々の64bit整数が素数かどうか」を判定するのには(素数表を引くこ
正規表現で素数判定 - NO!と言えるようになりたい
追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ この記事によると /^1?$|^(11+?)\1+$/ という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる． Rubyで書いた素数判定プログラムはこん
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Engadget | Technology News & Reviews