実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
「巡回セールスマン問題」を解くアルゴリズムを可視化したムービー
by Gaël Sacré いくつもの都市を移動するセールスマンが、すべての都市を最も効率よく(最小の移動コストで)移動できる方法を求める問題を「巡回セールスマン問題」といいますが、その解き方をビジュアル化したムービーがYouTubeで公開されています。 Traveling Salesman Problem Visualization - YouTube たとえば8つの都市があるとき、これを結ぶルートは5040通りが考えられます。 解法の一つが「欲張り法(Greedy Algorithm)」という、1つの都市から常に最寄りの都市へ移動しようと考える方法。 「最適」ではないものの、最適に近い答えを導き出してくれます。 ここで、組み合わせて使うのが「2-opt法」という方法。かなり単純なアルゴリズムで、2辺を繋ぎ直していきます。このとき、ルートに重なりがあると解消して新しいルートを作ります。
ナップサック問題でマラソンマッチ入門 - notブログ
マラソンマッチって？ 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。 この記事ではナップサック問題を例にしてこの２つのアルゴリズムを解説します。 もちろん、この２つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。 ビームサーチ まずは順番にナップサックに入るだけ入れるコードを書いてみます。 #include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 in
キー毎に値を集計する方法 - ひしだまの変更履歴
ひしだまＨＰの更新履歴。 主にＴＲＰＧリプレイの元ネタ集、プログラミング技術メモと自作ソフト、好きなゲームや音楽です。 irofさんとdaiksyさんがTwitter上でキーブレイク処理について話していました。 （リストを項目ごとに集計する→「ブレイク処理」を定形のアルゴリズムとして習いました→こんな解りにくいの、なんで好んで書くんだろう） キーブレイク処理というのは、データをキーでソートしておいて順番に読み込み、キーが同じ値の間に処理（よくあるのが集計）を続ける。キーが違う値になったら（キーがブレイクしたら）集計値を出力し、集計用変数をクリアしてまた処理を続ける。というアルゴリズムです。 ひとつ前のキーの値を保持しておく変数が必要で、最初はそれをどういう値にしておくか、また、ループを抜けた後に最後のキーの集計値を出力する必要があるか、といった辺りも考慮しないといけないので、慣れないと分か
世界で闘うプログラミング力を鍛える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版
モバイルゲームの歴史を年代別にご紹介します。モバイルゲームの成長と今後について詳しく解説していきます。
モバイルゲーム 物凄い勢いで勃興したモバイルゲーム業界は、いろいろな課題や問題に直面しながらも巨大化し、今日の時点でのスマートフォン向けゲームの市場へと継承されていきます。 モバイルゲームの歴史 2001 Javaアプリと3Dゲームの登場 Javaが利用できるようになったことにより、ダウンロード型のゲームが供給できるようになりました。 2002 携帯電話端末の大容量化・3D化競争 Java搭載携帯電話端末が登場してからごく僅か1年の間に、アプリのサイズに関しては10倍に広大化し、表現方法も2Dから3Dにシフトし始めました。J-PHONEは『ゼビウス』や『スペースハリアー』などといった昔のアーケードゲームを、ドコモはSIMCITYなどパソコンで世界的規模のヒットを飛ばしたゲームを主力商品としていました。 2003 モバイルゲームの一般化 メモリの制限が厳しいJava仮想マシン上ではなく、OS
機械学習 はじめよう 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
データマイニングで使われるトップ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
作るプログラムの機能や性能で勝負したい。そうだ、データベースを勉強しよう - きしだのはてな
さて、アルゴリズムの勉強のしかたと、ラムダ計算の勉強のしかたの目星をつけました。 アルゴリズムの勉強のしかた - きしだのはてな ラムダ計算の勉強のしかた、プログラム意味論 - きしだのはてな これでここで書いたプログラムの理論の基礎は勉強できたことになるんじゃないかと思います。 プログラムの理論とはなにか - きしだのはてな ところで、プログラムの勉強地図としてこういう図を書きました。 で、ハードウェアまわりについても、プロセッサを支える技術やネットワークはなぜつながるのかでひととおり勉強したとしましょう。 じゃあ次は、アジャイルか？テストか？UIデザインか？となるわけですが、やはりプログラマなら、プログラムの作り方や使いやすさの前に、作るプログラムの機能や性能で勝負したいじゃないですか。 いい感じに関数が分割できるよとか、読みやすい名前がつけれるよとか、効率よく仕事して定時に帰れるよと
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
プログラミングコンテストでの動的計画法
2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います． • 略して「DP」とよく呼ばれます． • スライドでも以後使います． 4. ナップサック問題とは？ • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は？ 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
秋元@サイボウズラボ・プログラマー・ブログ: 各ソート技法をアニメーションで表示するAnimated Sorting Algorithm Demo
ソートアルゴリズムのアニメーションデモでは、様々なソート手法(挿入、選択、バブル、シェル、マージ、ヒープ、クイック、三分割クイック)について、ソート対象のデータが完全ランダムの場合、ほぼソートされている状態、逆順にソート […] ソートアルゴリズムのアニメーションデモでは、様々なソート手法(挿入、選択、バブル、シェル、マージ、ヒープ、クイック、三分割クイック)について、ソート対象のデータが完全ランダムの場合、ほぼソートされている状態、逆順にソートされている場合、同じ値のものが多数ある場合のデータをソートする様子を、Javascriptを使ったアニメーションで見せてくれる。 それぞれのソートアルゴリズムがどのようなものか見せるというだけでなく、ソートのアルゴリズムに「常にこれが最適」というものはない、というのを示すのも目的、ということだ。 各アルゴリズムのリンクからは、そのアルゴリズムのコー
「ブログのエントリーは多い方がページビューが稼げる」という説を統計学的に検証してみた
ここのところ統計学を少しまじめに勉強しているのだが、そこで身につけたばかりのregression analysis（回帰分析）の手法を使って、「ブログのエントリーは多い方がページビューが稼げる」という説が本当かどうかを検証してみることにした。 まずは、このブログの過去２４週間の週ごとのエントリーの数とページビューの数を調べ、エントリーの数をX軸に、ページビューの数をY軸においてプロットしてみる。それだけでもなんとなく傾向があることが分かるのだが、これを最小二乗法を使って、直線で近似してみるとこんな感じになる。 直線の方程式は、Y = 44109 + 3405*X （Y:ページビュー、X:エントリー数）。つまり、このブログの場合、エントリーを書こうが書くまいが、週あたり約４４０００のページビューがあり、エントリーを一つ書くごとに約３４００ページビューづつ増えて行くということになる。 もちろん
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
処理並列は、必ず処理速度が向上するのか
はじめに CPUは、コンピューターの頭脳です。単純に考えると、頭脳が2つあれば、1つの時と比べて、同じ時間でたくさんのことを考えることができそうです。10年ほど前、Intel製プロセッサーPentium IIの頃から、1枚のボードに複数のCPUを載せて高速化する試みがなされました。Intel製CPUでは2ユニットまででしたが、SUN Microsystems製のコンピューターでは、もっとたくさんのユニットを載せることができていました。今では、CPU自体に複数の「コア」を載せ、1ユニットで同時に別々のことを実行できるようになっています。 ハードウェアが、同時に複数のことを実行できるようになったため、ソフトウェアもそれに対応する必要が出てきました。本記事では、昨今あちらこちらで声高に繰り返される、「並列処理化すれば速くなる」に疑問を持ったため、それを検証することにします。 対象読者 なんといっ
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IDEA * IDEA
各ソートアルゴリズムの違いを視覚で理解できる動画 | スラド IT