迷路の最短経路を求めるには？ - ザリガニが見ていた...。
相当、出遅れた感はあるが、以下の試験問題をやってみた。（Rubyで） さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************という入力に対し、 **************************
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
本文抽出ライブラリWebstemmerのblog本文抽出用特化スクリプト「blogstemmer」を書いてみた - FutureInsight.info
以前のエントリーで本文抽出ライブラリWebstemmerを使ってみました。 Webstemmerによるブログの本文抽出 - FutureInsight.info Webstemmerは非常に興味深い本文抽出ライブラリなのですが、ニュースサイトなどの複雑な階層構造を持っているサイトの本文抽出に特化しているため、逆にblogのようなシンプルなケースでの本文抽出に用いるには、ちょっとオーバースペックです。 Webstemmer Webstemmer はニュースサイトから記事本文と記事のタイトルをプレインテキスト形式で自動的に抽出するソフトウェアです。サイトのトップページの URL さえ与えれば全自動で解析するため、人手の介入はほとんど必要ありません。 そのあたりのことを考慮して、本文抽出ライブラリWebstemmerのblog本文抽出用特化スクリプト「blogstemmer」を作成してみました。
Logarithmic merging - naoyaのはてなダイアリー
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更
ルータとqueue:Geekなぺーじ
インターネットでは、ルータ(router)と呼ばれるネットワーク機器がパケットをバケツリレーのように宛先に届ける事で通信が行われます。 例えば、家にあるSOHOルータもルータです。 各ルータは、受け取ったパケットをどの接続インターフェースに転送するかだけを考えてパケットを次のルータ(ノード、ホスト)へと手渡します。 ルータは、パケットを受け取ってから次のルータに渡すまでqueue(キュー、待ち行列)に保持します。 例えば、回線容量(帯域)以上の転送要求を受け取った時には、queueにパケットが徐々に溜まっていきます。 そして、パケットによる混雑が「これ以上無理！」というレベルに到達するとパケットが破棄されてしまいます。 このような混雑している状況は輻輳(ふくそう)と呼ばれます。 輻輳状況をルータでどのような処理をするかという課題に対して、queue制御を行うという手法があります。 ここでは
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成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
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
