The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry.[1][2] However,
問題 空間に個の点がある.点から2つの点を選び,2点間のマンハッタン距離を最大化したい. ただし,マンハッタン距離とは,2点に対して で与えられる距離のことである. 単純に全通り試すとだけの計算量がかかるが,が大きいと計算コストがかなり大きくなる. そこで,に比例する計算量のアルゴリズムが知りたい.どうすればよいか. 制約条件 はに比べてとても小さい.(具体的にはくらい.) 解法 Step 1 まず,という距離を導入しておく. これは, …(1) で定義される. Step 2 マンハッタン距離は,定義より次のようにも表すことが出来る. [tex:||x||_{1} = \max\{ ; y \in \{-1,+1\}^k \}]…(2) ここで,[tex:]は通常のユークリッド空間における内積([tex:={x_1}{y_1}+...+{x_k}{y_k}]),は次ベクトルのうち各成分が-
気付けば夏休みが終わってました。blog全然更新してないね、うん… それはそうと先日サークルの合宿に行ってきました。*1 ということで成果物をひっそり公開してみる。 http://github.com/seikichi/tuitwi python + cursesで作ったTUIのtwitterクライアントです。*2 スクショ 操作方法はREADMEを見てやって下さい。上のgitのページでも見れます。 更新処理とかは別スレッドで動かしていたりするので、そこそこ快適なんじゃないでしょうか。 特徴としては 設定ファイルがYAML、タブ分けできる ぐらいかな? なんとなくgithubで公開してみたけど、svnしか使ったことない僕にはgitサッパリだぜ! (追記:2009/10/04 OAuthでの認証に対応) *1:「先日って言っときながら大分前じゃねえか!」とかいう突っ込み禁止 *2:Pytho
X×Y個のセルから成るグリッド上のスタート地点から出発し、全5種類のパチクリ(生物)を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを1つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です(全体の数は5000以下)。 最初に1つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG(Di
このエントリでは Ruby on Rails と MySQL を使って日本語の全文検索を行う方法を記述する。Ruby on Rails のバージョンは 2.0.2、MySQL のバージョンは 5.0.67、Tritonn のバージョンは 1.0.12、Hyper Estraier のバージョンは 1.4.10 を使用した。サンプルの文章データとして、あらゆる日本人にとって極めて身近な著作権切れ文章である『ドグラ・マグラ』と『黒死館殺人事件』を利用した。処理のために整形したデータは本エントリに添付しておく。またデータベースへアクセスするコードではマイグレーションを除きできるだけベンチマークを取るようにし、その結果は本エントリの最後に記載する。 ページネーション Rails でページネーションを実現する will_paginate という plugin は ActiveRecord に標準でつ
Connect to an IRC server and store messages into a file (Python recipe) by Gian Mario Tagliaretti You want to connect to an IRC server, join a channel and store private message into a file on your hard disk for future reading. I haven't tried but I think you can execute this code from an hosting always connected to the internet and read the message through a web browser. import socket, string #som
はてな認証API http://auth.hatena.ne.jp/ Rubyではてな Hatena::API::AuthのRuby版をid:secondlifeさんが公開してくれてる。 gem install hatenaapiauthrequire 'rubygems' require 'hatena/api/auth' require 'cgi' cgi = CGI.new params = { :api_key=>"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", :secret=>"xxxxxxxxxxxxxxxx" } auth = Hatena::API::Auth.new(params) begin hatena = auth.login(cgi['cert']) # hatena = { # "name" => "taslam", # "image_u
この文章の取り扱い この文章にはInternet communityのためのExperimental Protocolを定義し、改善のための意見と提案が寄せられています。 このプロトコルと標準化の状況については"IAB Official Protocol Standards"の最新版を参照して下さい。 この文章の配布は自由に行ってかまいません。 <訳者注:>これは原文の取り扱いです。日本語訳についてはセクション13.2 「日本語訳について」に準じます。 また、IRCプロトコルの定義はあくまで原文であることを断っておきます。 概要 最初にBBS上のユーザ間のチャットの方法として使われ初めてから4年間以上にわたって、IRCプロトコルは開発が進められています。 現在、このプロトコルはサーバ/クライアント方式で世界中のネットワークをカバーしています。そして、ネットワークの成長に伴って、プロトコルも
One of my all time IIDX favorites! It's perfect for DDR Supernova! Song is listed as speed rave but sounds like eurobeat to me, movie is hot cars and fast women, with some "Secret Live 2" concert footage as well. Music by Naoki Maeda and Tatsuya Shimizu (a.k.a. Tatsh). Video by Gyo Eguchi (a.k.a. VJ GYO)
If only Taka did "A" too Artist-DJ Amuro (A.K.A. dj TAKA) First Appearance-IIDX RED First DDR Appearance-DDR SuperNOVA
ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基本 テンプレート グラフ
軽量・高速なデータベースSQLiteをRubyから扱うためのライブラリ。 インストール Windowsの場合 RubyForgeから、 sqlite3-ruby(sqlite3-ruby-x.x.x.zip)をダウンロードする。 ダウンロードしたファイルを展開する。 インストールプログラムを実行する。 ruby setup.rb config ruby setup.rb setup ruby setup.rb install RubyGemsを使う場合 RubyGemsをインストールした後、 次のコマンドを実行する。 gem install sqlite3-ruby SQLiteのインストール SQLite Download Pageから、 sqlitedll-3_x_x.zipをダウンロードする。 ダウンロードしたファイルを展開する。 sqlite.dllをパスの通ったディレクトリにコピ
Original Document revision: 1.02 Original Last update: 2003-05-27 翻訳バージョン: 0.9.5 目次 はじめに 前準備 インストール 単純なDBIスクリプト 問合せ処理 結果セットを返さない問合せ処理 結果セットを返す問合せ処理 クオート、プレースホルダー、パラメータ束縛 メタデータの問い合わせ コードブロックつきのメソッド サーバ接続の補足 エラー処理とデバッグ トランザクションサポート ドライバに特化した機能 その他の便利な機能 参考情報 はじめに Ruby DBI を使うと、いろんな種類のデータベースを同じAPIでもってrubyから アクセスすることができます。これは、Perl DBI と perl の関係と同じです。 この記事では Ruby DBI を使用したRubyスクリプトの書き方を説明します。こ の文書は DB
本記事のおもな内容 いろいろあるSQLの規格 サンプルデータベースを操作してみる SELECT文の基本的な使い方 WHERE句の使い方 条件の指定方法 リレーショナルデータベースシステム(RDBMS)も、今や、システムの構築には不可欠なものとなりました。皆さんが目にしているシステムや、管理しているシステムでも、RDBMSが使われていないシステムを探すほうが大変ではないでしょうか。RDBMSの普及にともない、RDBMSへのアクセス手段であるSQLも、日常的によく見かけるものとなりました。 このSQL実践講座では、SQLの効率的な使い方をエッセンスにしてお伝えしていこうと考えています。SQLは、データを操作するために非常に簡単な構文で構成されているように見えます。ところが、実際に使い込んでいくと、一見簡単に取得できるように見えるデータが取得できない場面にぶち当たることがあると思います。また逆に
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く