Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
JavaScriptで大量のオブジェクトの当たり判定を効率的にとる - Subterranean Flower Blog
ゲームなどのコンテンツにおいて、「当たり判定」から逃れることはできません。オブジェクトとオブジェクトが衝突したかどうかという判定は、インタラクティブコンテンツにおいて最も重要な部分になるからです。 当たり判定の実装自体は難しくありません。ですが、素朴な実装ですと、対象となるオブジェクトが大量である場合に、十分なパフォーマンスが出ません。これはオブジェクトの多い、現代的なゲームでしたり、弾幕シューティングなどを作るときに大きな障害となります。 この記事では、大量のオブジェクトの当たり判定を処理する、効率的な方法について紹介します。 まずは素朴に実装してみる 当たり判定の処理を語るには、ある程度ゲームの骨組みのようなものが必要になってきます。もちろんクラスなどを使わないベタ書きでもよいのですが、大変読みにくくなってしまいます。ですので、今回は、まず簡易的なゲームエンジンのようなものを作って、そ
読んだ直後から滅茶苦茶役に立つ──『アルゴリズム思考術:問題解決の最強ツール』 - 基本読書
アルゴリズム思考術:問題解決の最強ツール 作者: ブライアンクリスチャン,トムグリフィス,田沢恭子出版社/メーカー: 早川書房発売日: 2017/10/19メディア: 単行本（ソフトカバー）この商品を含むブログを見る『アルゴリズム思考術:問題解決の最強ツール』とは個人的にそそられる書名ではなかったので(ほぼ原題「ALGORITHMS TO LIVE BY」通り。)なかなか手が出なかったのだが、さらっと読み流すか……と手を出してみたらおもしろくて、その上読んですぐに役に立つ内容が満載なのであっという間に最後まで読んでしまった。 基本的にはアルゴリズム──より具体的な言葉でいえば「計算によってあらかじめ算出された、最適な手順」を知っていることが、いかに現実的な問題を解決する役に立つのかを紹介した一冊なのだが、なにしろ単なる手順なので、準備も何もいらないし読んだだけで「おーそうなんだ」とすぐに使
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
あらゆる数独パズルを解く
Peter Norvig / 青木靖 訳 このエッセイでは、 あらゆる数独パズルを解くという問題に取り組む。制約伝播と探索という2つのアイデアを使うと、ごく簡単に解けるということがわかる(主要なアイデアはコードにして1ページたらずで、補足的なコードが2ページある)。 数独の記法と予備概念 最初に記法をいくつか決めておこう。数独パズルは81個のマス(square)からなる盤面を使う。数独ファンの多くはカラムを1-9で、行をA-Iでラベル付けしており、カラム、行、ボックスのような9個のマスの集まりをユニット(unit)と呼び、ユニットを共有するマスをピア(peer)と呼んでいる。パズルではマスのいくつかが空いており、他は数字が入っている。パズルの目的はこうだ。 それぞれのユニットのマスが1から9の数字の順列によって埋められるようにする。 つまり、1つのユニットに同じ数字が2度現れてはならず、そ
SPFAの紹介 - hogloidのブログ
なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。 オーダーはO(VE)なんですが、これだけ聞くとベルマンフォードで十分です。 SPFAはqueueを使ってベルマンフォードと大体同じことをします。 始点のコストを0にしてqueueに詰み、 queueが空でない間、そこからつながっている辺について、最短距離を更新できるか考えます。(ダイクストラ法のように) また、ある頂点vがqueueに入っているかの配列を持っておき、すでにqueueに入っているなら最短距離を更新するだけです。 最短距離を更新できて、queueにないならqueueに入れます。 ちょっと想像すると、
Random Forestで計算できる特徴量の重要度 - なにメモ
(pixabay.comより) １．背景とか Random Forest[1]とは、ランダムさがもつ利点を活用し、大量に作った決定木を効率よく学習させるという機械学習手法の一種です。SVMなどの既存の手法に比べて、特徴量の重要度が学習とともに計算できること、学習が早いこと、過学習が起きにくいこと（追記注釈１）などの利点が挙げられます。Kinectの姿勢推定に使われているらしいです。 最近、Random Forestをカジュアルに使う例が多く（特にうちの研究室）、一部パラメータやら出力やらがわからない人も多いと思います。使い方はTJOさんの資料[2]を読んでもらえれば理解できると思うし、詳細は波部先生の資料[3]をよんでもらえればわかると思います。 それで、いろいろな日本語の資料をいくら読んでも、Random Forestがもつ特徴の１つである、特徴量の重要度の詳細に関してはほとんどノータッ
Google Developers: データ圧縮アルゴリズムの基礎 - ワザノバ | wazanova
「webサイトの平均サイズが2メガに近づき、Androidゲームが125メガになってきて、コンテンツと送信コストのトレードオフが深刻な問題になってきている。開発者にとって次の10年は、圧縮アルゴリズムを理解して、うまく使いこなすことが重要になる。」という紹介文に惹かれて、3回 (20分/10分/20分) のビデオシリーズを見ました。概要は下記の通りですが、図示が中心でわかりやすく説明してくれてますので、是非チェックしてみてください。（3回目の後半はちょっと素人には難解でした。。） Episode 1: Variable Length Codes モールス信号からバイナリコードに進化してきたが、共通しているのは、出現率の高い文字から順番に短い記号列 ("."もしくは"-") /数列 ("0"もしくは"1") をあてはめることで、記号列/数列全体の平均の長さを短くしようとする考え方。 この場合
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei
SAIS論文を読了した。これは賢いなあと思った。ので概要だけ書いておく。 参考: SACAs(Suffix Array Construction Algorithms) 本手法ではLMS-substringという可変長の部分文字列を使って再帰的にsuffix arrayを構築する。再帰時に文字列長は最大でも1/2のサイズになるため高速な構築が期待できる。ただし構築に必要なメモリ空間は従来のsuffix arrayと変わらない。 まず文字列S(長さはn)のそれぞれの文字にSまたはLというフラグを立てる。直後の文字より小さければS、大きければL、同じならば同じフラグを付ける。文字列の末尾には$という記号がついていて、これはあらゆる文字より小さく、フラグはSとする。例えば abracadabra$ SSLSLSLSSLLSとなる。ここで直前の文字がLで、自分がSであるような文字をLMS-char
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
世界で闘うプログラミング力を鍛える150問 〜トップIT企業のプログラマになるための本〜 - iwiwiの日記
先行発売のお知らせ (11/7 追記) 以下の店舗で先行発売が行われているらしいです． 紀伊國屋書店 新宿本店 (https://twitter.com/KinoShinjuku/status/265658160222724096) 紀伊國屋書店 新宿南店 (https://twitter.com/kino_Minami/status/265405470548844546) ジュンク堂書店 池袋本店 (https://twitter.com/junkudo_ike_pc/status/265677297430978562) 有隣堂 ヨドバシAKIBA店 (https://twitter.com/yurindo_akb/status/265648944745426945) 丸善 丸ノ内店 なお，電子書籍版の発売も予定しているそうですが，調整中とのことで少し後になりそうです． 原著は既に第5版
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
中里一日記: 正規表現マッチングはMap-Reduceできる
正規表現マッチングはMap-Reduceできる グレゴリオ暦で新年を祝われる皆様、あけましておめでとうございます。 今日のお題は正規表現。ただしチューリング完全なPCREではなく、有限オートマトンにもとづく本来の正規表現である。 一個の巨大な文字列に対する正規表現マッチングをMap-Reduceで分散計算することはできないと思い込んでいるマヌケな子はいねーがー？ できそうな気はするけれどアルゴリズムがわからないアホな子はいねーがー？ 大丈夫、このエッセイを読むまで私にもわからなかった。アホはあなただけではない。といってもなんの慰めにもならないが。 （このエッセイは正規表現のインクリメンタルマッチングの計算量について論じているが、分散計算のほうが例として自然と思ったのでそうした） 英語とHaskellができてモノイドとfingertreeが常識な人なら元のエッセイを読めばすべて一目瞭然だと思
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
一様乱数の積は一様乱数にはならない | wrong, rogue and log
Twitterのタイムラインに最近も出ていたのだが、1年位前にRコミュニティで流行ったこれは面白い。 Understanding “randomness” http://stackoverflow.com/questions/3956478/understanding-randomness I can't get my head around this, which is more random? rand() OR rand() * rand() I´m finding it a real brain teaser, could you help me out? これは質問者は"more random"と言っているように、この質問の時点では確率変数の概念を全く理解していなくて、その意味で教科書的というか額に入れて飾りたいようなナイスな間違えの一つである。一般的に普通のプログラム言語のra
最近のtrieの話（xbwなど） - Preferred Networks Research & Development
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Gamasutra: Amir Fassihi's Blog - "0 – 60 fps in 14 days!" What we learned trying to optimize our game using Unity3D.