動的計画法を用いるアルゴリズムの開発
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG教えて頂けないでしょうか？
日頃からアルゴリズムについて御詳しい、プログラマの方々
なら、お分かりになるかなあ？と思います。
問題
n個の整数の列i_1,i_2,.....,i_nがある。この整数列をk個の「仕切り」
によって、k+1のグループに分割し、グループに含まれる整数の和を最小
にしたい。
動的計画法により最適な分割を求めるアルゴリズムゐ開発せよ。
例
15,3,7,6,10,4
という整数が与えられた場合は、
15|3,7,6|10,4
が最適な分割で、和が最大のグループは２番目で
16である。
00021
NGNG----------------- 糸冬 -----------------
0003デフォルトの名無しさん
NGNG動的計画法ってなんですか？
0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNG0006デフォルトの名無しさん
NGNG圧縮関連の話？
0007デフォルトの名無しさん
NGNG臨機応変な家族計画
0008デフォルトの名無しさん
NGNGK個の箱に､箱の中の総和が一番小さい箱に､一番大きい数を入れるな
15,10,7,6,4,3
10,7,6,4,3-15||
7,6,4,3-15|10|
6,4,3-15|10|7
4,3-15|10|7,6
3-15|10,4|7,6
15|10,4|7,6,3
て事になるんだが､このアルゴリズムが動的計画法かどうかは知らんし
つか、問題が単純すぎるんじゃないの？こんなの最適解は小学生でも
判るだろ。もーっと難しい問題に適用すべき計画法じゃないのか？
とりあえず動的計画法について教えろや
0009トリッキーの１
NGNG問題を解くとき、全体を小さい単位の問題に分割して、それぞれを
解決することによって全体としての解を得る、という方法が一般的です。
８クィーンを例に挙げると、「チェス盤に８つクィーンを置く」という
目的を達成するために、１つのクィーンが置けるかどうかを８回判断して、
最終的な解を得る、という方法を（無意識に）考えますよね。
＃例が悪いかもしれない
それに対し、動的計画法とは、あらかじめその小さい問題を全て解いておいて、
必要に応じて解いた答えを索引し、最終的な答えを得る考え方です。
具体的な例、必要ですかね？そこまで行くと、なんかスレ違いの気分もします。
0010デフォルトの名無しさん
NGNG15,10,7,6,4,3の総和は45なので、三つに分割すると､15になる
ただしこれは最適な解がそうなわけで、要素によってはそうならない
可能性がある。で、各箱が15に近付くように（超えない範囲で）数を入れる。
15,10,7,6,4,3-
10,7,6,4,3-15
7,6,4,3-15|10
7,6,3-15|10,4
6,3-15|10,4|7
6-15|10,4|7,3
この時点で､最後の数なので､一番総和の小さい箱に入れる
15|10,4|7,3,6
この考えも動的計画法かはわからんが、思考自体は､
「想定される最適解に近付くように、解を組み立てていく」
というもの。
やっぱり問題が簡単すぎるな。１は動的計画法のアルゴリズム自体を
知りたいのか､設問を解きたいのか､どっちなのだ？
0011デフォルトの名無しさん
NGNG0012デフォルトの名無しさん
NGNGなんで？つか、数字の順番変える事に意味は無いだろ。
単に整頓されてるかされてないかの違いなだけで。
こういうのは、問題の本質を抽出する（ソートが本質かそうでないかを
判断する）事が肝要だから､11はこういう話には向いてないんじゃない？
0013デフォルトの名無しさん
NGNGNをそれぞれの数に対して積分してから変数変換してフーリエ変換してから偏微分。
0014デフォルトの名無しさん
NGNGもはやあわれ。
0015デフォルトの名無しさん
NGNG数列の要素には順番があるんだよ？
00161
NGNGすみません。
まず、数字の順番を入れ換えてはいけません。
説明ぶそくで済みませんでした。
この問題のヒントみたいなのが載っていたのですが、
(これってヒントになるのか？ってレベルですが)
ヒント
例によって、木状に探索していく。整数列に仕切りをいれて２つに
分割することで木を一段深くする。その時、元の列がi個の分割
なら一段下がったところは、i_1個とi_2個の分割(ただしi_1＋i_2＝i)
になっている)
というヒントがついていました。
僕が考えるに動的計画法は、
１、同じことの繰り返しによる、無だを省く
２、ボトムアップ
ということが指針だということなので、
00171
NGNG1,2,3,4,5(数字はアイテム番号とする)
というアイテムを分割することを考える。
ここで、
(1,2)(3,4,5)と(1),(2,3,4,5)
という分割を考え、
さらにこれから先の分割を考えるとき、
一つ目の分割で、
1+2 < 3+4+5
とすると、
明かに(3,4,5)を次は分割しようとするはずである。
ここで、２つ目の分割
(1)(2,3,4,5)
をさらに分割しようとすると、
すでに最初の分割(1,2)(3,4,5)
で
1+2 < 3+4+5
ということが分かっているから、
(1)(2)(3,4,5)
という分割パターンは最初から、考えなくていいということになり、
計算時間が短縮できる。
ということだと思います。
これをアルゴリズムとして、気持のいい形にかきたいんだけど、
どうやったらいいのかな？って思って悩んでいます。
(もっといい考え方＋拡張があれば教えてください！)
001811
NGNGお前の方が向いてないんだよ。
00191
NGNGあと、有益なヒントとして、以下の情報を持っています。
動的計画法を適用できる多くの問題にもれず,
この問題も部分問題によって(定式化にしたがった)木を構成できます.
そこでこの木の根に相当する問題の解を求めるというのが
我々の目的なんですが,
動的計画法ではこの木の一番下の子の部分から
ボトムアップ式に解を覚えつつやっていこうというのが
方針だと思われます.
ちなみに O(kn^2) でできました.
(たぶんこれが正解でしょう)
0020デフォルトの名無しさん
NGNG「グループに含まれる数の和を最小」ってどういうこと？
文面通り受け止めると、
1,2,3,4,5,6,7,8→1|2|3|4|5|6|7|8
グループに含まれる最小の数：１、最大の数：８
00211
NGNG難解な感じで、説明しにくいです。
でも、これが、与えられた問題で、一字たりとも変えていません。
まず、
k個の「仕切り」のkは定数です。
また、nも定数です。
プログラマの皆さんは、アルゴリズムに熟知してらっしゃると
思うのですが。
0022デフォルトの名無しさん
NGNG00231
NGNG仕切りが２つ、グループは３つですよね。
この整数の数を増やしていくと、
それを例えば４つの仕切りで分割しろといわれても、
最適なものを調べるには、
全部総あたりで、計算すると大変なことになりますよね。
これを動的計画法で解決したいのです。
動的計画法の詳しい説明はかんべんしてください。
0024デフォルトの名無しさん
NGNG0025やばい20
NGNG0027やばい20
NGNG00281
NGNG感想だけなのでさげ
0029デフォルトの名無しさん
NGNG0030
NGNG１）グループの和が総和/ｋなら部分的に最適とは言える。
２）全てのグループの和が総和/ｋなら最適。
３）全てのグループの和と総和/ｋの差が（総和/ｋの余り）/k＋１
以内であるなら最適。
つうことで後よろしく。
0031デフォルトの名無しさん
NGNG0032デフォルトの名無しさん
NGNG動的計画法にうってつけの問題ですね
簡単に出来ますよ。ただ説明を書くのは辛いです。
ソースなら提示できそうですが……
>>30さんの方法は、これだけの文面ではよくわからないのですが、
もうちょっと詳しく教えてもらえませんか？
0033デフォルトの名無しさん
NGNG0034トリッキーの１
NGNG例えば、15,3,7,6,10,4,13,2,3,6 という１０個の数に、
区切りを３つ入れる場合について考えてみます。
この場合、下の図のようなテーブルをプログラムで作成すればいいわけです。
（等幅で見てね）
15 3 7 6 10 4 13 2 3 6
区切り残り０：10,69 9,54 8,51 7,44 6,38 5,28 4,24 3,11 2, 9 1, 6
区切り残り１： 4,38 4,28 4,27 3,24 2,24 2,17 1,13 2, 6 1, 6 1, 6
区切り残り２： 3,25 2,24 3,23 2,17 2,14 1,13 1,13 1, 6 1, 6 1, 6
区切り残り３： 2,23 3,16 2,14 1,14 1,13 1,13 1,13 1, 6 1, 6 1, 6
例えば左下の(2,23)が何を表しているかというと、
「区切りがまだ３つ使える場合、
次の最適な区切りはここから２つ目の場所、
その場合の最大値は23になりますよ」
という事です。すなわち、１つ目のグループは[15,3]が正解だと解るわけです
これがわかれば、問題は、
「7,6,10,4,13,2,3,6 という８個の数に区切りを２つ入れる」
という風に変わります。
その場合は(3,23)、すなわち２つ目のグループは[7,6,10]とわかります。
このように追っていくと、答えは[15,3]、[7,6,10]、[4,13]、[2,3,6]となります。
（続く）
0035トリッキーの１
NGNGそれは自分で考えてください。
ヒントは、
・区切り残り０の場合は単純計算です。
・区切り残りＮの場合が解っていれば、Ｎ＋１の場合もわかります。
例：（等幅）
区切り残り４： 1,16 1,14 2,13 1,13 1,13 1,13 1,13 1, 6 1, 6 1, 6
数学的帰納法により、全ての場合の表が求まります。
わかりにくいかもしれませんが、もし動的計画法の知識があれば、
割合すんなりと読めるのではないでしょうか？甘い？>>1さん
0036デフォルトの名無しさん
NGNGつうか、問題文に厳密さがかける、っていうのが真実だろ。
「n個の任意の自然数からなる数列 i_1, i_2, ..., i_nがある。この
整数列をk個の「仕切り」によってk+1のグループに分割し、グ
ループに含まれる整数の和を最小にしたい。kは0以上n-1以下の
定数で、任意に指定することができるとする。動的計画法により
最適な分割を求めるアルゴリズムを開発せよ。」
こんなかんじか？
0037デフォルトの名無しさん
NGNGなるほどね。動的計画法というものが理解できた。計算量はO(KN)程度かな。
0039デフォルトの名無しさん
NGNG同じく３列目以降がないと、２列目が出ないし。
だから、N列目から１列目に向かって解いて行くんだと思う。
0040デフォルトの名無しさん
NGNG確実にいえることは
０列目の情報は、計算しなくてもわかるので
入力とみることができて、
K列目までがわかれば、答えが出る
そういうわけで、39の言ってる事は正反対です
基本的には
一番右から順番に
数列の数が１個の場合、２個の場合・・・
を考えていくみたいだけど
004140
NGNG右から13,2,3,6だけの場合考える余地が無い
この４つの数の列に
4を付け加えることを考えると
略
この５つの数の列に
１０を付け加えることを考える
この時の最適な区切り線を計算するには
区切り線を10の右につけた場合を考えると
第４列なので残り３本線を引くのだが、
10を取り除いた数列4,13,2,3,6
に３本線を引くときの最適な場所はすでに3列目で計算している
そして､その最大値と10を比較すれば・・・
このように、以前の計算を利用していくのだと思う
0042学生でもＯＢでもなんでもないけどさ
NGNG技術科学大学スレで７系の人にたずねるとよいぞ（ワ
004440
NGNG違うと思う
004540
NGNG行と列逆に使ってる
00461
NGNGみなさん、いろいろな御説明ありがとうございます。
今から学校に行かなければいけませんので、学校
のいきかえりと学校で、このスレを参考にひたすら考えます。
>>32=34 さん？
>ソースなら提示できそうですが……
どうかお願いします。動的計画法にはまってきたので、
いろいろ調べたいです。
0047デフォルトの名無しさん
NGNG４６の書いたコードを公開せよ
00491
NGNG0050デフォルトの名無しさん
NGNG自然数などという条件は付いてないと思うが。
0051トリッキーの１
NGNGあと１日考える価値のある課題だと思いますよ。
動的計画法の、しょうもないナップザック問題などに比べて、この課題はとても良くできています。
動的計画法にはまっているのであれば、この問題に是非挑戦してみてください。
（それに、安易に課題の解を求める人たちが増えても困りますから）
もし私の説明がわかりにくければ、とりあえずネットで「ナップザック問題」等で検索をかけ、
その説明と併せて読んで貰えるとわかるんじゃないかと思います。
頑張ってください。
>>38
39さんが言っているように、自分より右かつ上であるセルが全てわからないと
自分自身のセルが解けないためです。
右側から解いていっても、上側から解いていっても、本質的には同じです。
for文の順序が入れ替わるだけですね、きっと。
00521
NGNG00531
NGNGいままで、やったことがないんです。
005411
NGNG１）期待される最小のグループ和（総和/グループ数）を求める。
２）数列の頭からみていって「期待されるグループ和」を超えた所に壁を作っていく。
これが初期の遺伝子。
【メイン】
３）100本の配列を用意してこの遺伝子をコピーする。
４）乱数によって壁をひとつ選びこれを左または右に（乱数で決定）移動する。
５）最良の結果が出ればこれを別の配列に保存しておく。
６）この操作を100本の配列について100回行う。
７）100本の配列の中味を今までの最良の結果に置き換え、（３）〜（６）を繰り返す。
３）〜７）を数回繰り返せば最良の結果が出て来るだろう。
0055デフォルトの名無しさん
NGNG0056デフォルトの名無しさん
NGNG005711
NGNG−−−−−−−−
にした方が面白いかな。
0058デフォルトの名無しさん
NGNG>４）乱数によって壁をひとつ選びこれを左または右に（乱数で決定）移動する。
このへんがGAじゃないね
最適化問題といえばGAだけど！？
でも、動的計画法の方が計算量が明らかに少ないね
この場合は・・・
005911
NGNG0060デフォルトの名無しさん
NGNGそんなことするよか、全部のパターンを確かめた方が速いでしょ？
数が多すぎて全部のパターンを確かめられない上に、
適切なアルゴリズムが存在しない時に
初めて意味がある
最近は制御系にも応用され始めてる
0061やっぱり向いてない11
NGNG0062デフォルトの名無しさん
NGNG0063デフォルトの名無しさん
NGNGどんくらいに圧縮されるんだ？
ちなみに総当たりだと、指数的数字になるなあ。
006456
NGNG0065デフォルトの名無しさん
NGNGだって､使う機会ほとんどないもん
一流大学でてるインテリ学生の一部でしょ
そういうのに詳しいのは
でもって、そういうのが一流プログラマなんだけどね
00661
NGNG噂では、 O(kn^2)だそうですが。なぜ？
締め切りまで１２時間きりました。
しかし、このアルゴリズム、はまったけど、まとめあげる
の大変やった。A４*3枚も説明に費した。
けど、他人が読んで分かるかなあ？
明日、また読み直して、書き直すかも？
お休みなさい。プログラマの皆さん。
0067デフォルトの名無しさん
NGNG=((n+1)n/2)k>=計算量
0068トリッキーの１
NGNG多分わかっていると思われるのですが、１さんへの説明チックに書きます。
計算量において、/2とか+1とかいう概念は存在しません。
あくまでもオーダーなので、定数プラスや定数倍などは評価されません。
だから、nlognの場合も、「logの底って何だろう？」という事はナンセンスになります（何でもいいんです）
最終的に67さんの式は、結局O(kn^2)となります（なぜその式が出るのかの考察はまだしていませんが）。
>>1
実際にコードを書いてみて、そのfor文に注目すると、計算量は（概算で）出ます。
理論で証明しようとするととたんに面倒になりますが、もしそれを授業でやっていないなら
実際にソースコードを示して、そこから計算量を示す方法が現実的でしょう。
ちなみに、私は（証明はしてませんが）O(kn^2)だと思っています。
>>65
例えば動的計画法なんて、まず普通しらないし、実際の場面で応用する機会もまずありません。
しかし、使用できる道具がいくつかあるというのは選択肢を広げる上で非常に重要だし、
実際に、まず実世界で使わないと思っていた「巡回セールスマン問題」なども、流通業界の仕事で
使用したという経験もあります（時間軸に従ったグラフを利用）
過去の人たちが様々な証明を行ってくれている方法なので、応用できる場面にて
数学的考証をしなくてすむので、知っていればいるほど応用範囲が広がるかと。
決して「一流大学を出ているインテリだけが知ってろ」などと思わずに、
機会があれば学んで貰えればと思います。
とはいえアルゴリズムオタクってのは、応用になれば途端に使えなくなるのが
常ですよね。まさに頭でっかち。
そういう意味では、一般社会で経験を積んだプログラマこそが一流なのかもしれません。
酔っているから支離滅裂で失礼。
0069デフォルトの名無しさん
NGNGソースをみせてくれないですか？>>68
00701
NGNG教えて頂きありがとうございました。
ソースは作成できませんでしたが(今日締め切り４本抱えていたため
余裕無しでした)動的アルゴリズムについては、かなり
いい感じに理解できたと思います。
なかなか面白い発想ですし、これから、リアルタイムに
使って行けたらいいなあ、と思います。
0071デフォルトの名無しさん
NGNG言い訳書いてるだけで、アンタからは技術的な発言無かったし
0072デフォルトの名無しさん
NGNG一年生なんだから仕方ないと思われ
0073デフォルトの名無しさん
NGNG最初はすべての整数が区切られているものとする。
整数がn個あるので区切りはn-1個あるとする。
もちろんこのときは分割は最適です。
さて、ここから区切りを一個取り除いても分割が最小になるには？
と考えて、ある区間内ににおける総和を求めて、その右にある区間における総和と足し合わせます。
その値が過去に調べたいずれの値よりも最小になるのが最適な「区切り」の取り除き場所です。
最小になるかどうかの調べかたは簡単ですよね。
で、一個取り除いたところでこれは区切りn個の時点で最適な分割になっています。
同じ手続きでさらに一個ずつ取り除いていき、k個の区切りになったところで終了。
間違ってるかも？
0074デフォルトの名無しさん
NGNGアルゴリズムは上の方にでてるから・・・・
それ読んでみれば、間違ってんのすぐ気づくよ
007573
NGNGお、間違ってると指摘されたよ。
かなり自信あったんだが。
他の人はどう思う？
0076デフォルトの名無しさん
NGNGだいたい､その日本語じゃわからないって（笑）
人としゃべったことある君？
0077デフォルトの名無しさん
NGNG区切りのパターンが k→k+1 で複数変化する場合があるので、
(e.g.)
4 5 | 2 7 (k=1)
4 | 5 2 | 7 (k=2)
Greedyなアルゴリズムが常に最適解を与えるとは限らない。
0078デフォルトの名無しさん
NGNG６ ３ １ ３ ６ ９ を３つに分けるとすると
６ ３ １ ３ ６ ９ （スタート）
＾ ＾ ＾ ＾ ＾
６ ３ １ ３ ６ ９ （１個抜く）
＾ ＾ ＾ ＾
６ ３ １ ３ ６ ９ （２個抜く）
＾ ＾ ＾
６ ３ １ ３ ６ ９ … 結果、最大13となるが
＾ ＾
正解は
６ ３ １ ３ ６ ９ … 最大10である。
＾ ＾
007978
NGNG６ ３ １ ３ ６ ９ … 最大19
＾
一方、正解は
６ ３ １ ３ ６ ９ … 最大15
＾
0080デフォルトの名無しさん
NGNGもし､これがグリーディーなアルゴリズムなら
>お、間違ってると指摘されたよ。
>かなり自信あったんだが。
>他の人はどう思う？
の発言は痛すぎる（ｗ
とりあえず､書き込む前に考えないとね
0081デフォルトの名無しさん
NGNG将棋ってこういう考えかたしないと、
とてつもない量の計算になるよなぁ
0082デフォルトの名無しさん
NGNGかなりずれてると思われ。
0083トリッキーの１
NGNG申し訳程度のコメントしかついていません。
改行少なくするため、つめて書いていますが許してください。
せっかく公開するんだから、もしバグがあったら、是非教えてくださいね
#include <stdio.h>
// 個数
#define N 10
// セパレートの数
#define SEPARATOR 3
// 与えられる配列
const int array[N]={15,3,7,6,10, 4,13,2,3,6};
#define MAX(a,b) (((a)>(b))?(a):(b))
// 表のセルにあたる構造体
typedef struct
{
// この地点の最適の解
int sol;
// その地点から何個か
int num;
} cell;
int main(void)
{cell solutions[N][SEPARATOR+1];int i,j,s,sum;
// 表の後ろの方から順に埋めていく
for(i=N-1;i>=0;--i)for(j=0;j<SEPARATOR+1;++j)
{solutions[i][j].num=0;for(sum=0,s=i;s<N;++s)
{sum+=array[s];
if(j==0 || i==N-1 || solutions[i][j].num==0
|| (s!=N-1 && solutions[i][j].sol>MAX(sum,solutions[s+1][j-1].sol)) )
{if(j==0 || i==N-1)
// １行目か、もしくは最終列ならば、処理無し
solutions[i][j].sol=sum;else
// より良い解決方法を記録する
solutions[i][j].sol=MAX(sum,solutions[s+1][j-1].sol);
solutions[i][j].num=s-i+1;}}}
// デバッグ用にテーブルを表示
for(j=0;j<SEPARATOR+1;++j){for(i=0;i<N;++i)
printf("%2d,%2d ",solutions[i][j].num,solutions[i][j].sol);
printf("\n");}
printf("\n最大の和:%d\n分割方法:",solutions[0][SEPARATOR].sol);
for(i=0,j=SEPARATOR;j>=0 && i!=N;--j){
printf("[%d個] ",solutions[i][j].num);i+=solutions[i][j].num;}
return 0;}
008473
NGNG＞78
ありがとう。
0085デフォルトの名無しさん
NGNG気付いたことがあった。時間なかったからほっぽったけど。
0086デフォルトの名無しさん
NGNG巡回セールス問題の最適解を求めるアルゴリズムはないです
0087デフォルトの名無しさん
NGNG0088デフォルトの名無しさん
NGNG多項式のオーダで求めるアルゴリズムがない、ね。
>>85はそれは分かってて時間がないから放置したんだと思われ。
0089デフォルトの名無しさん
NGNG将棋もオセロもどう考えても総当りじゃ無理だぞ。
0090デフォルトの名無しさん
NGNGゲームによっては探索する深さが指定できるでしょ？
深読みすれば強いＡＩってことで。
ちゃんとした強いＡＩにしたければニューラルネットとかＧＡとかを使うのかなぁ？
0091デフォルトの名無しさん
NGNG0092デフォルトの名無しさん
NGNGまあ、将棋とかオセロは基本的には幅優先探索。
あとは、いかに枝刈りするかという話しになります。
GAって遺伝的アルゴリズムのこと？
ニューラルネットとかじゃ、現状ではまっとうなゲームプレイヤー
は作れてないと思います。
0093デフォルトの名無しさん
NGNGあれって、動的計画法？それとも、総当り？
009493
NGNGこんなの見つけたけど、どうなんだろう？
棋譜を参照にするってことは枝切りしてるのかな？序盤と終盤だけは、
それ以外は総当りで
0095デフォルトの名無しさん
NGNG２択かい？（笑）
0096デフォルトの名無しさん
NGNGスレ違いなので、下げます。
えっと・・・。総当りという言葉をどういう意味で使ってる
かわからないけどミニマックス法、αβ法、静的評価関数とい
ったあたりの話しは大丈夫？知らなかったら検索かけてみて。
序盤では人間が定石を使うような感じで棋譜を利用する。
こういう探索問題で一手深く読むためには、下手すると何
十倍という時間がかかってしまうのね。で、終盤検索かけて
るときに、「この局面になったらもう勝ちだ」とか、「この
局面になったら負けだ」とかいう情報があると、その局面に
ついては最後まで読んだことになるから、すごく効いてくる
らしいのね。
コンピュータの強みは物量作戦だっていう事ですね。
0097デフォルトの名無しさん
NGNG>>34の
[15,3]、[7,6,10]、[4,13]、[2,3,6]
って答えはあってるの？
>>8のアルゴリズムで解くと
[15,3]、[13,4]、[10,6,2]、[7,6,3]
ってなるけど。各箱の数値の合計の最大値が
最小になるように仕分けるんだよね？
0099デフォルトの名無しさん
NGNG勘違いしてました…。
0100デフォルトの名無しさん
NGNGなんで100にも届こうか問いスレなのに、
いまだに問題を理解してないやつが居るわけ？
0101デフォルトの名無しさん
NGNG動的計画法でゲームのAIは大抵無理でしょう。つーか理解してないでしょ。
総当たりのうち、どれだけ効率的に枝切りをするかという問題じゃないの？
それとももっとエレガントな方法があるのかな？
どうでもいいけど、課題教えてスレが、なぜか優良スレになってしまったのはどうして？
■ このスレッドは過去ログ倉庫に格納されています