約 1,822,069 件
https://w.atwiki.jp/fsharpmaster/pages/33.html
月謝3500円のそろばん塾で出たチャレンジ問題（動的計画法で） この記事の続きです。 Arigataさんが書かれたエントリをフムフムと呼んでいて、MSのソルバに興味を持ちつつ、そもそも「部分和問題」という言葉も「ナップザック問題」という言葉も知らなかった自分の不勉強に恥じ、ちゃんと勉強しないとなぁ・・・と考えているだけの日々を送っていたのですが、何の因果か「アルゴリズムを学ぼう」などという本が絶好のタイミングで出てしまい、この中にこの「ナップザック問題」の解説が乗っていたので、これを参考にF#で「動的計画法」を使った解法を試してみることにしました。 お題自体は前回のこのエントリと同じです。 動的計画法 まず基礎知識として、このそろばん塾の問題は、「部分和問題」という有名なカテゴリに属する問題で、金額の部分が整数でない場合には「NP完全」という、要素数が上がるにつれ幾何級数的に計算量が増えていく性質を持っているということです。 ただし、次のようないくつかの制限が許される場合は、劇的に計算量を減らすアルゴリズムが知られています。このアルゴリズムが今回のお題となっている「動的計画法（Dynamic Programming）」です。 金額の部分が整数でかまわない（重さのように少数点の値を考慮しない）。 とにかくひとつ解が見つかればよい。見つからない場合はリミットを超えない範囲で最大の値がわかればよい。 動的計画法については「アルゴリズムを学ぼう」や他のサイトに詳しい解説がありますので、そちらを参照してもらったほうがいいと思います。 「アルゴリズムを学ぼう」は、限られたページで沢山のアルゴリズムを紹介しようとするあまり、一つ一つの解説は少な目となっており、動的計画法もこの本を読んだだけではちょっとわかりづらいかもしれません。動的計画法はとても有名なアルゴリズムなので解説ページも多いのですが、僕は「Gushwell's C# Programming Page」や「Algorithms with Python」のの下半分にある説明が一番わかりやすい気がしました。下のサンプルも、この説明と「アルゴリズムを学ぼう」の説明を読んで頭に入れ、電車の中で書き起こしたものです。 実装 let goods = [ ("プロ野球", 19373) ("ディズニーランド", 20453) ～ 前回のものを使用 ～ let max3f x y z f = let max_xy = max x y in if z max_xy then f () ; z else max_xy let dp l target = let ar int array = Array.zeroCreate (target + 1) let g (string * int) array = Array.zeroCreate (target + 1) for gds in l do let wk = snd gds for w in [target..(-1)..1] do ar.[w] - max3f ar.[w] ar.[w - 1] (if w = wk then ar.[w - wk] + wk else 0) (fun () - g.[w] - gds) // printfn "%A" ar ar, g let rec pp (g (string * int) array) (ar int array) pnt = printfn "%A" g.[pnt] if ar.[pnt] (snd g.[pnt]) then pp g ar (ar.[pnt] - (snd g.[pnt])) let solve total = let res, g = dp goods total pp g res total solve 150000 実行結果は以下のようになります。 ("にくまん", 155) ("机いす", 67275) ("リポD", 1737) ("CDプレーヤー", 36307) ("電動歯ブラシ", 4282) ("たこ焼き", 534) ("ピアニカ", 3351) ("回転ずし", 15906) ("ディズニーランド", 20453) val dp seq string * int - int - int array * (string * int) array val pp (string * int) array - int array - int - unit val solve int - unit val it unit = () ざっくりとした解説 最初の関数max3fは、三つの数と関数(unit- unit)を引数にとります。三つの引数のうち、最大の値を返すのですが、最後の数が一番大きかった場合だけ、引数で渡された関数を実行する機能を持っています。 二つ目の関数dpがこのプログラムの心臓部です。金額（150000）ぶんの配列を用意し、それぞれの金額ごとにどのように商品を買うのが一番いいかを考えていきます。 forループが２段になっていますが、外側では商品リストについて、内側では金額ごとのループを回っています。内側のループが減数ループになっている点に注目してください。このプログラムは配列arを変えながら動くのですが、ループの中でar.[w - wk]を参照しているため、後ろから値を変えていかないとまずいのです。このあたりのことについては、上記の本と二つのサイトを読んでじっくり考えてもらえばわかると思います。 ループの中は、max3fを呼び出し、参つの値の最大値を取りつつ、最後の数が一番大きかった場合だけ商品購入配列gを更新しています。 最後にar,gで計算結果を返しています。ちょっと信じがたいですがこれで結果が得られるのです。 再帰関数ppはdpの結果として得られた二つの配列から、購入すべき商品の一覧を抜き出して出力する関数です。 最後のsolveは、dpを呼び出してppに渡すだけの関数です。 雑感 前回のエントリでは、「ちょっとコーヒーを淹れてるぐらいの時間」などと書いていますが、この「動的計画法」を使うと最初の解にたどり着くのに必要な時間は「Enterキーが戻るぐらい」になってしまいます。つまり0.1秒以下ということです。 とてつもない高速化と言えますが、動的計画法を知らなかった僕は前回のエントリのプログラムで満足していました。 もちろん、動的計画法が使えない場合（全部の解を列挙しなければならないなど）は、前回の方法が有効なのですが、アルゴリズムを知っているか知らないかでこれほどの結果の差が出るのですから、やはりプログラマは日々勉強しなければいけないということなのでしょう。 例によって上のプログラムは一例ですので、いろいろな方法（ArigataさんのようにSolverを使った方法など）や実装の流儀がありますので、上で挙げたサイト以外の情報も含めていろいろあたってみてください。 （文責：片山 功士 2012/06/06） 今日： - 人 昨日： - 人 トータル： - 人
https://w.atwiki.jp/vivid_turtle/pages/42.html
文字列は動的計画法で数え上げなどの題材とされることが多い。蟻本にもそれのページがある。 ここでは、蟻本にないはずの自分で見つけた知見を書く。 文字列の動的計画法のテーブルの定義 文字列の動的計画法のテーブルの定義は、dp[i]などをi文字目を使用した時の〇〇〇〇、とするとうまくいきやすい！ 蟻本にある例だけど、LCSの動的計画法のテーブルの定義も、dp(i, j) = Sのi文字目とTのj文字目まで使った時の最長であり、dp(k, l)(1 = k = i ,1 = l = j)までのすべてのベスト、という着眼点よりはこの定義の方がうまくいきやすいと思う。 最も、LCSの場合は前者は後者を含み、蟻本もその前提に立ってコードを書いてる。後者のような考え方を取らない場合は、二次元累積和配列を用意する必要がある。 認識としては、前者が普通で、LCSがたまたま後者にしても問題ない上に実装が楽になった、と考えたい。 例 ABC130 E(500) Common Subsequence https //atcoder.jp/contests/abc130/tasks/abc130_e この場合、 dp(i, j) = Sのi文字目、Tのj文字目を最後尾として作れる共通部分列の場合の数 とするとうまくいく。動的計画法では珍しく、その状態のみをピンポイント指し、それ以外を含むということはない。 遷移としては、S(i) != T(j)は当然０となる。S(i) == T(j)ならば、dp(a, b)(ただし、a, bはそれぞれi - 1, j - 1まで計(i - 1) * (j - 1)通りすべて)の総和となる。これはSのi - 1文字目,Tのj - 1文字目までのすべての部分列と定義できる。それに最後にSもTにもあるS[i]とT[j]を足せば、新しい文字列となる。 また、今までの文字列を採用せず、S[i]のみで構成することも可能で、これは1通り。 之の実装で、上記の二次元累積和を使用すれば高速に更新できるので、この定義特有のデータ更新時のデータ取得の難しさを解決できる。 例 ABC141 E(500) Who Says a Pun? https //atcoder.jp/contests/abc141/tasks/abc141_e この問題自体は、ローリングハッシュ、Z-algorithmでも解ける。それは次のページを参照してほしい。 ローリングハッシュ Z-algorithm この問題の計算量は2乗を許容しており、これを考えると、DPを少し考えたくなる。上の内容を踏まえたDPを考えると、次のような定義を思いつく。 dp(i, j) = i番目文字とj番目の文字を最後尾としたときの連続部分列の長さの最大 これを思いつけば更新式も難しくはない。 dp(i, j) = 0 (if S[i] != S[j]) = min(dp(i - 1, j - 1) + 1, j - i) 最後のminの意味は、これはあくまで[i, j]の範囲内での連続部分列の最大の長さであり、長さをj - iに最大でも抑える必要がある。 次のように、 aaaaaaaaaaaaaa ^ ^ | | i j でも、その添え字ではj - i個の長さまでしか見ておらず、最終的な答えに相当するもっと長いのはほかのもっとj - i大きい区間のDPの計算でわかる。
https://w.atwiki.jp/akitaicpc/pages/91.html
動的計画法(DP) フィボナッチ数列での動的計画法? 巡回セールスマン問題 TSP? ...
https://w.atwiki.jp/ce00582/pages/4938.html
class dp{ String str; String ph; int strlong,nlong; int sx,nx,nxs; int dicnumber; String[] dic=new String[100]; double[] p=new double[100]; double[][] v=new double[500][5]; int[] op=new int[500]; int[][] nextgo=new int[500][5]; double v1,maxv,supv; double p1; int t; void makedata(String str){ strlong=str.length(); ph=str.substring(0,1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } v[0][0]=p1; v[0][1]=1; for(t=1;t strlong-1;t++){ nlong=t; if(nlong 4)nlong=4; maxv=-999; nxs=0; for(nx=0;nx nlong+1;nx++){ ph=str.substring(t-nx,t+1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } v1=p1*v[t-1][nx]; if(v1 maxv)nxs=nx; if(v1 maxv)maxv=v1; } v[t][0]=maxv; nextgo[t][0]=nxs; for(nx=1;nx nlong+1;nx++){ v[t][nx]=v[t-1][nx-1]; nextgo[t][nx]=nx-1; } } t=strlong-1; nlong=strlong-1; if(nlong 4)nlong=4; supv=-999; nxs=0; for(nx=0;nx nlong+1;nx++){ ph=str.substring(t-nx,t+1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } v1=p1*v[t-1][nx]; if(v1 supv)nxs=nx; if(v1 supv)supv=v1; } op[t-1]=nxs; System.out.println(op[t-1]); t=strlong-2; while(t 1){ t=t-1; nx=op[t]; op[t-1]=nextgo[t][nx]; System.out.println(t); System.out.println(op[t-1]); } } }
https://w.atwiki.jp/ce00582/pages/4943.html
class makeword{ String[] dic=new String[100]; double[] p=new double[100]; double[] v=new double[100]; String[] word=new String[100]; String[] phx=new String[100]; int[] gototx=new int[100]; int strlong; String ph; int dicnumber,wordnumber; int t,tx,txs,sx; double p1,v1,maxv; void makedata(String str){ strlong=str.length(); ph=str.substring(0,1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } v[0]=p1; for(t=1;t strlong;t++){ ph=str.substring(0,t+1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } txs=0; maxv=p1; for(tx=0;tx t;tx++){ ph=str.substring(tx+1,t+1); p1=p[0]; for(sx=1;sx dicnumber+1;sx++){ if(ph.equals(dic[sx]))p1=p[sx]; } v1=p1+v[tx]; if(v1 maxv)txs=tx; if(v1 maxv)maxv=v1; } gototx[t]=txs; v[t]=maxv; } sx=0; t=strlong-1; while(t 0){ tx=gototx[t]; ph=str.substring(tx+1,t+1); t=tx; sx=sx+1; phx[sx]=ph; wordnumber=wordnumber+1; } sx=sx+1; phx[sx]=str.substring(0,t+1); wordnumber=sx; for(sx=1;sx wordnumber+1;sx++){ word[sx]=phx[wordnumber+1-sx]; } } }
https://w.atwiki.jp/wiki6_piro/pages/806.html
都市計画法 としけいかくほう 1968年に制定された都市計画に関する基本的な法律。 歴史 1888年 東京市区改正条例 1918年 大阪・名古屋・京都・横浜・神戸に準用 1919年 旧都市計画法、市街地建築物法 1968年 都市計画法 1980年 地区計画制度を新設 関連項目 17条縦覧 まちづくり条例 地区計画 地域地区 工業専用地域 市街地開発事業 建築・都市辞典 建築基準法 旅辞典 準防火地域 道路 都市再開発方針 都市施設 都市計画区域マスタープラン 都市計画決定 都市計画道路 都市計画関連法 防火地域
https://w.atwiki.jp/ce00582/pages/3161.html
1997 Uhlig A toolkit for analyzing nonlinear economic dynamic models easily 興味深い論文です。著者は、Humboldt大学の先生です。この論文のテーマは、対数線形近似法を紹介した論文である。実物的景気循環理論のモデルは、確率的動的計画法で表現できる。ただし、確率的動的計画法は、解析的に解くことはできない。そのため、数値解法により、解く必要がある。多くの経済学者が、いくつかの確率的動的計画法を解く数値解法を提案している。それらの手法は、「精度」と「スピード」のジレンマに悩まされる。「スピード」をとれば、「精度」を犠牲にする必要がある。「精度」を取れば、「スピード」を犠牲にする必要がある。対数線形近似法は、その中で、最も人気のある手法である。米国では、対数線形近似法に並んで、LQ法も人気がある。ただし、日本では、LQ法は人気がなく、対数線形近似法が圧倒的人気である。例示されたモデルは、労働供給は弾力的だが、準線形モデルを使用している。対数線形近似法は、局所モデルなので、「精度」に問題がある。関連文献として、Campbell(1994)等がある。
https://w.atwiki.jp/kojiharu1/pages/47.html
都市計画法（としけいかくほう） 昭和四十三年六月十五日法律第百号 最終改正：平成一八年六月八日法律第六一号 最終改正までの未施行法令：平成十八年六月二日法律第五十号 目次 第一章 総則 第二章 都市計画 第一節 都市計画の内容 第二節 都市計画の決定及び変更 第三章 都市計画制限等 第一節 開発行為等の規制 第一節の二 市街地開発事業等予定区域の区域内における建築等の規制 第二節 都市計画施設等の区域内における建築等の規制 第三節 風致地区内における建築等の規制（第五十八条） 第一章 総則 第二章 都市計画 第一節 都市計画の内容 （地域地区） 第八条 都市計画区域については、都市計画に、次に掲げる地域、地区又は街区で必要なものを定めるものとする。 一 第一種低層住居専用地域、第二種低層住居専用地域、第一種中高層住居専用地域、第二種中高層住居専用地域、第一種住居地域、第二種住居地域、準住居地域、近隣商業地域、商業地域、準工業地域、工業地域又は工業専用地域（以下「用途地域」と総称する。） 三 高度地区又は高度利用地区 四 特定街区 六 景観法（平成十六年法律第百号）第六十一条第一項の規定による景観地区 七 風致地区 十 古都における歴史的風土の保存に関する特別措置法（昭和四十一年法律第一号）第六条第一項の規定による歴史的風土地区特別保存地区 十一 明日香村における歴史的風土の保存及び生活環境の整備等に関する特別措置法（昭和五十五年法律第六十号）第三条第一項の規定による第一種歴史的風土保存地区又は第二種歴史的風土保存地区 十二 都市緑地法（昭和四十八年法律第七十二号）第五条の規定による緑地保全地域、同法第十二条の規定による特別緑地保全地区又は同法第三十四条第一項の規定による緑化地域 十五 文化財保護法（昭和二十五年法律第二百十四号）第百四十三条第一項の規定による伝統的建造物群保存地区 第二節 都市計画の決定及び変更 （公聴会の開催等） 第十六条 市町村は、前項の条例において、住民又は利害関係人から地区計画等に関する都市計画の決定若しくは変更又は地区計画等の案の内容となるべき事項を申し出る方法を定めることができる。 （都市計画の決定等の提案） 第二十一条の二 都市計画区域又は準都市計画区域のうち、一体として整備し、開発し、又は保全すべき土地の区域としてふさわしい政令で定める規模以上の一段の土地の区域について、当該土地の所有権又は建物の所有を目的とする対抗要件を備えた地上権若しくは賃借権（臨時設備その他一時使用のため設定されたことが明らかなものを除く。以下「借地権」という。）を有する者（以下この条において「土地所有者等」という。）は、一人で、又は数人共同して、都道府県又は市町村に対し、都市計画（都市計画区域の整備、開発及び保全の方針並びに都市再開発方針等に関するものを除く。次項において同じ。）の決定又は変更をすることを提案することができる。この場合においては、当該提案に係る都市計画の素案を添えなければならない。 まちづくりの推進を図る活動を行うことを目的として設立された特定非営利活動促進法（平成十年法律第七号）第二条第二項の特定非営利活動法人、民法（明治二十九年法律第八十九号）第三十四条の法人その他の営利を目的としない法人、独立行政法人都市再生機構、地方住宅供給公社若しくはまちづくりの推進に関し経験と知識を有するものとして国土交通省令で定める団体又はこれらに準ずるものとして地方公共団体の条例で定める団体は、前項に規定する土地の区域について、都道府県又は市町村に対し、都市計画の決定又は変更をすることを提案することができる。同項後段の規定は、この場合について準用する。 第三章 都市計画制限等 第一節 開発行為等の規制 第一節の二 市街地開発事業等予定区域の区域内における建築等の規制 第二節 都市計画施設等の区域内における建築等の規制 第三節 風致地区内における建築等の規制（第五十八条） （建築等の規制） 第五十八条 風致地区内における建築物の建築、宅地の造成、木竹の伐採その他の行為については、政令で定める基準に従い、地方公共団体の条例で、都市の風致を維持するため必要な規制をすることができる。 第五十一条の規定は、前項の規定に基づく条例の規定による処分に対する不服について準用する。
https://w.atwiki.jp/ce00582/pages/5400.html
線形計画法 （１）プログラム プロ １００ ＡＡ （２）コメント どうにかなるものです。 （４）作業記録 月日 ページ作成
https://w.atwiki.jp/ocw_reading/pages/2.html
メニュー MIT OpenCourseWare 6.001 Structure and Interpretation of Computer Programs, Spring 200501 6.001にとっての計算機科学とは 02 Schemeの基礎 6.170 Laboratory in Software Engineering, Fall 2001 (ソフトウェアの設計について。終了)01 導入 02 依存を解く1 03 依存を解く2 04 データ抽象化1 05 抽象型 06 不変表明と抽象関数 6.170 Laboratory in Software Engineering, Fall 2005 (ソフトウェアの設計について改訂版、テストおよび差分のユーザビリティについて。終了)05 テスト 16 ユーザビリティ1 17 ユーザビリティ2 6.231 Dynamic Programming and Stochastic Control, Fall 200201 動的計画法とは 必ずはじめにお読みください OCWリンク集 ご意見・コメントはこちらへ トップページ 連絡先：ocwreading "at" mail.goo.ne.jp 6.170 Laboratory in Software Engineeringのテキスト。和訳本はなさそうです。なんだったらこのWikiの中の人が和訳しますが…。 6.170 のユーザビリティの講義で出てくるニールセンさんの本。一度絶版になったのですが最近復刊しました。良書です。 6.231 Dynamic Programming and Stochastic Controlのテキスト。 ASINが有効ではありません。 更新履歴 取得中です。