NTTが「一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか」という「ケーキ分割問題」を正しく解くアルゴリズムを開発したそうだ（日刊工業新聞）。 「ケーキ分割問題」とは、2人で1つのケーキを分割する際に、両者が満足するように分割するにはどうすれば良いか、という問題。2人が異なる価値観を持っているというのがポイント。今回発表された新アルゴリズムは「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」というものだそうだ。 今日・明日とケーキを食べる機会は多いかと思うが、さっそく応用してみてはいかがだろうか。しかし、3人以上で分割する場合はどうすれば良いのだろうか？
4月2日に情報処理学会が日本将棋連盟に「コンピュータ将棋」で挑戦状を送ったことが話題になった*1。日本将棋連盟は挑戦を受諾、女流棋界の第一人者、清水市代女流王将・女流王位が対戦相手と決まった。対戦は今秋から順次行われるという。 情報処理学会の挑戦状に関するFAQによれば、対戦ソフトウェアに関して次のように記されている。 Q：対戦ソフトウェアは既に決まっているか A：合議アルゴリズムを用いる方針になっています。複数のソフトウェアを疎結合で並列計算させて、それらの意見を集約して、次の一手を決定する手法です。現在のところ、限られた実験では効果が認められており、これを実際の対局に用いる方向で検討しています。個々の参加ソフトウェアの候補は、プロジェクトに現時点で参加しているGPS将棋、Bonanza、激指、YSS、TACOS、柿木将棋などです。これを実用的にどのように組みあわせるのかは、実験を元に決
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
「この発想はなかった！」と驚いた。genoTyp はフォント同士を交配させて新しいフォントを生み出す実験サイトだ。早速、試しにやってみた。1. 第一世代の親を決めるgenoTyp を開いて左上の [Breed] タブをクリックすると「交配ページ」が表示される。[add original font] ボタンをクリックして、祖先となるフォントを２つ追加してみた。交配させるために２つのフォントをドラッグしてくっつけた。くっついた状態になれば交配の準備は完了だ。2. 交配させてみる中央の [cross] ボタンを押すと第一世代が誕生する。４人の子供が誕生した。父親似だったり、母親似だったり、子供によって雰囲気が異なっている。3. 第一世代でも交配別の [original font] を追加させて、第一世代の中から気に入ったものと交配させてみた。３人の子供が第二世代に誕生した。4. さらに交配！今度
うん、ごめん。タイトルは釣り。っていうか今から書くことも間違ってるかもしれない。 識者のフォローを待ちたい。 http://b.hatena.ne.jp/entry/http://wiredvision.jp/news/200904/2009041523.html これの話なんだけど 「遺伝的アルゴリズム」って出たときに、もうこれは人工知能ではないと一応考えていい。それはソートプログラムが人工知能ではないのと同じみたいな。 「f(x,y)を最大にする整数x,yを求めよ」 これを遺伝アルゴリズムでやるとこうなる。 ランダムで(x,y)の組をいくつか作る。これが個体。xyは遺伝子になるすべての個体に対してf(x,y)を計算する。このときf(x,y)は評価関数という。評価の低い個体の何割かは子孫を残さず死ぬ。のこりの個体は以下の方法で子孫を作れる。 コピーを残す。自分のもってるx,yを交換した子
ＮＴＴコミュニケーションズ（ＮＴＴコム）は１９日、次世代光通信基盤「ＩＯＷＮ（アイオン）」で接続した３カ所のデータセンター（ＤＣ）に分散配置した画像処理半導体（ＧＰＵ）サーバーを用... マイクリップ登録する
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く