タグ検索の該当結果が少ないため、タイトル検索結果を表示しています。
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
僕は今エムスリーという企業でアルバイトをしている。 この企業をご存知ない人もいるかもしれない。医療従事者向けのサービスを主体としているからだ。だから医師はほとんどが知っている。 調べてみるとこの企業、東証一部に上場しておりグループ全体の従業員数が5000人、四半期の売上が800億円くらいあるかなり巨大な企業だ。 僕は（これでも）医学生なので企業の名前は知っていたが特に興味関心があるわけではなかった。 ある日 Twitterを見ているとエムスリーで機械学習をやっているエンジニアが採用募集のツイートをしていたので「インターン行ってもいいですか」と軽いノリでDMを送ったら軽いノリで承諾が返ってきた。以降業務内容は企業の機密上書けないがインターン採用までとインターン期間、インターン期間が終わった後のアルバイト期間について思ったことを書いていこうと思う。 採用まで まず「機械学習チームに限らずインタ
動的計画法(DP)の基礎知識から例題、考え方、解説コードまで記載した個人的メモ
実用的なソフトウエアを開発するにはアルゴリズムの知識は欠かせない。基礎から機械学習まで、厳選した10個のアルゴリズムをPythonによる実装とともに解説する。 ［7 動的計画法］ レーベンシュタイン距離 多くの人にとって、アルゴリズムの学習の最初の壁となるのが、「動的計画法」ではないでしょうか。動的計画法は、「問題の部分的な結果を記録・利用しながら、最終的な結果を求める」手法の総称です。クイックソートや深さ優先探索のような手法よりも、1 段か2段、抽象的な概念である点と、アルゴリズムを可視化しにくい点が、難しく感じる原因なのだと思われます。また、“動的計画法”という名称が内容に合っていないことも、動的計画法をわかりにくくしていると言えるでしょう。 しかし、多くの有用なアルゴリズムは動的計画法の手法を使っているので、避けて通ることはできません。 ここでは、動的計画法で「レーベンシュタイン距離
「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する ～TeX言語で動的計画法(DP)～ - TeX Alchemist Online
最近，巷では「サイゼリヤで1000円あれば最大何kcal摂れるのか」を計算するのが流行っているようです。 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。 - Qiita 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。 - Qiita 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。 - Qiita 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。 - Qiita 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をExcel のソルバーでで解いてみた。 - Qiita 【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法 - わえな
はじめに 最近、実生活で競技プログラミングが役に立ちました。 趣味の一環で長方形のQRコードであるrMQRコードを生成するPythonパッケージを作成しています。その中で「ビット列が最も短くなるようにデータをエンコードする」という処理に動的計画法を用いました。大学時代に競技プログラミングをやっていた身としては「競プロが役に立った！」と嬉しかったので、実例として共有したくてこの記事を書いています。動的計画法のDPテーブルの定義から遷移のしかた、解の復元までを図や実装とともに説明しています。動的計画法自体は説明していません。実装の全体はこちらでご覧いただけます。 この記事に出てくるrMQRコードの仕様に関する記述はISO規格1に基づいています。最適なエンコードを求めるアルゴリズム自体は仕様に含まれるものではなく、オリジナルのものになります。 ※QRコードは(株)デンソーウェーブの登録商標です。
Haskellで動的計画法を攻略する
Haskellで動的計画法を実装する２つの方法 出典： Easily Solving Dynamic Programming Problems in Haskell by Memoization of Hylomorphisms ザ圏論的やり方としては①Dynamorphism、手続き的な方法として②STモナドが挙げられる。 DynamorphismはHylomorphismをメモ化したようなもので、詳しくはlotz氏のサイトを参照してほしい。 Haskellerとしては、Dynamorphismはとても憧れる手法である。しかし、思ったよりも速度が出ない。。 このスクラップに二通りのLCSの解法を記載したが、いずれもTLEであった。 lotz氏によると、メモ化されたデータ構造にはO(n)でしかアクセスできないことが理由とのこと。 この記事では、STモナドによるメモ化再帰を用いた動的計画問題
動的計画法とナップサック問題について解説します。 動的計画法とは 直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算効率を上げる手法のこと。 「途中の計算結果を再利用」＝「同じ計算をしない」ということ 難しいように見えて考え方自体は単純 ICPC国内予選でもC問題～F問題くらいに何かしらの形で2,3題ほどでます 英語では「Dynamic Programming」と呼び、略して「DP」と呼ぶことが多いです。 動的計画法で効率的に解ける問題の一つに、ナップサック問題というものがあります。 ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？ という問題です。 具体的には、以下の図のようになります。ナップサックに書かれている「15kg」が容量で、周囲
うさぎでもわかるアルゴリズム 動的計画法
こんにちは、ももやまです。 動的計画法は、アルゴリズムでもかなり重要な内容です。AtCoderやらプログラミングコンテストとかでもよく出てきます。 ですが、動的計画法は「アルゴリズムを学ぶ上での壁・登竜門」とも呼ばれるとおり、かなり難易度の高いアルゴリズムとなっています。どの参考書を見てもなかなかわかりやすくは書かれていません。 そんな動的計画法を今回はうさぎでもわかるようにわかりやすくかみ砕いて説明したいと思います。 １．動的計画法とは 動的計画法とは、 問題をいくつかの簡単で小さな問題に分割 それぞれの問題の計算結果を表に記録 同じ問題に対しては表から計算結果を参照する の3つの特徴を持ったアルゴリズムです。 といきなり言われてもわけがわからないと思うので、動的計画法のイメージを説明しましょう。 動的計画法のイメージ 例えば、\[ 28 \times 37 \]の計算を解きなさい。 と
こんにちは。paizaラーニングでコンテンツ制作をしている学生スタッフの工藤です。 みなさん、「DP（Dynamic Programming、動的計画法）」って知っていますか？ DPは代表的なアルゴリズムのひとつで、競技プログラミングの問題を解く際にも多く用いられます。そのため耳にしたことはあるかもしれませんが、慣れるまでは扱いが難しく実用性が分からないという方も多いと思います。 ただし、ある程度問題を解いていくとパターンのようなものが見えてくるはずなので、たくさん問題に触れてみるのがおすすめです。 そこで今回は、paizaラーニングのレベルアップ問題集に追加された「DPメニュー」を使って、DPの問題に慣れるための学習法を紹介していきます！ DP（動的計画法）とは 本題の問題集の紹介に入る前に、DPとはどんなアルゴリズムなのか簡単にご紹介します。 こういうときはひとまずWikipediaを
これは、https://o-treetree.hatenablog.com/entry/DPL1B（明日投稿）の前段階の記事です。動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見ながらとりあえず解けるまでの初心者の思考をメモしたものです。 DPがわからん！ 最近暇なので（無職で外出自粛）競技プログラミングAtCoderをやっています。先日AOJにも登録しました。 BFSとかDFSは一応わかったのですが、頻出のDPがわからんので勉強しようと思いました。 ↓BFSとかDFSができるようになった記事 o-treetree.hatenablog.com o-treetree.hatenablog.com さて、いろいろ検索しましたが、一番わかりやすかったのはこちら。G
ビットDPとは ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 基本的には、以下のような DPを考えます。 漸化式の更新式としては、 $$dp[ S \cup \{v\} ] = dp[ S ] + cost(S, v)$$ のように集合を1つずつ増やしていく形になることが多いです。 この集合に対するDPによって、\(n\) 個のものに対して\(n!\) 通りの順序の中から最適なものを計算するのを高速化できる場合があります。 集合をビットで表現する 実際には集合を配列の引数にするために、集合を2進数で表現します。全体集合 {0,1,2,…,n-1} の部分集合 S を n 桁の2進数で表現するのです。 例えば、全体集合 {0,1,2,…,9} の部分集合 {0,3,5} については、0bit目と3bit目と5bit目が 1で、それ以外が0
強化学習はゲームやパズルを解く機械学習の手法であり、過去記事1にて、ハノイの塔を強化学習で解く方法を検証しました。 本記事では、ポールの数を3本から4本、5本、…と増やした一般化ハノイの塔について考察します。内容は、以下の2つです。 ・動的計画法による最短手順の導出 ・強化学習による求解 ※ソースコードをGitHubに公開しています。 → https://github.com/akih1992/qiita/tree/master/rl/generalized_hanoi 一般化ハノイの塔について ここでは、ポール数を増やしたハノイの塔を一般化ハノイの塔と呼ぶことにします。ポールが増えた場合、3本のときよりも短手順で求解できるのは明らかですが、最短手順はどうなるのでしょうか。本記事ではこの最短手順を考えます。 ※導出方法を考えるにあたり、一般化ハノイの塔についてまとめているこのWebページ2
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
動的計画法によるDVDのディスク分割の改善
企業で働くということ - (衝)動的計画法
響け！動的計画法 (DP) 入門〜個人的まとめ
実用アルゴリズムの基礎「動的計画法」と機械学習の基礎「類似度」を知る
動的計画法の実例: QRコードの最適なエンコードを求める - Qiita
動的計画法（ナップサック問題） - アルゴリズム講習会
定番アルゴリズム「DP（動的計画法）」をプログラミング練習問題集で学ぼう！ - paiza times
DP（動的計画法）でコイン問題を解くまでの過程メモ - おはやし日記
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~ | アルゴリズムロジック
ポールを増やしたハノイの塔の求解【動的計画法、強化学習】 - Qiita
aliproject.jp
qiita.com/kojix2
togetter.com
www.google.com
www.tkma.co.jp
limulu.weblog.to