5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

動的計画法を用いるアルゴリズムの開発

1 :デフォルトの名無しさん:01/09/26 17:09
以下の問題を考えています。私には手におえないので、
教えて頂けないでしょうか?
日頃からアルゴリズムについて御詳しい、プログラマの方々
なら、お分かりになるかなあ?と思います。

問題
n個の整数の列i_1,i_2,.....,i_nがある。この整数列をk個の「仕切り」
によって、k+1のグループに分割し、グループに含まれる整数の和を最小
にしたい。
動的計画法により最適な分割を求めるアルゴリズムゐ開発せよ。


15,3,7,6,10,4
という整数が与えられた場合は、
15|3,7,6|10,4
が最適な分割で、和が最大のグループは2番目で
16である。

2 :1:01/09/26 17:13
解決しました

----------------- 糸冬 -----------------

3 :デフォルトの名無しさん:01/09/26 18:06
俺も初心者なんで、答えが知りたいです。
動的計画法ってなんですか?

4 :デフォルトの名無しさん:01/09/26 19:15
そうだそうだ、1は結果をちゃんと書いてくれ

5 :デフォルトの名無しさん:01/09/26 19:19
俺も結果が気になってきた・・・

6 :デフォルトの名無しさん:01/09/26 19:21
その分割は何の為にするの?
圧縮関連の話?

7 :デフォルトの名無しさん:01/09/26 19:23
>>3
臨機応変な家族計画

8 :デフォルトの名無しさん:01/09/26 21:00
俺なら、

K個の箱に、箱の中の総和が一番小さい箱に、一番大きい数を入れるな

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

て事になるんだが、このアルゴリズムが動的計画法かどうかは知らんし
つか、問題が単純すぎるんじゃないの?こんなの最適解は小学生でも
判るだろ。もーっと難しい問題に適用すべき計画法じゃないのか?

とりあえず動的計画法について教えろや

9 :トリッキーの1:01/09/26 21:16
動的計画法は、場合によってはかなり有用なアルゴリズムです。

問題を解くとき、全体を小さい単位の問題に分割して、それぞれを
解決することによって全体としての解を得る、という方法が一般的です。

8クィーンを例に挙げると、「チェス盤に8つクィーンを置く」という
目的を達成するために、1つのクィーンが置けるかどうかを8回判断して、
最終的な解を得る、という方法を(無意識に)考えますよね。
#例が悪いかもしれない

それに対し、動的計画法とは、あらかじめその小さい問題を全て解いておいて、
必要に応じて解いた答えを索引し、最終的な答えを得る考え方です。

具体的な例、必要ですかね?そこまで行くと、なんかスレ違いの気分もします。

10 :デフォルトの名無しさん:01/09/26 21:28
そういうアプローチなら、

15,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

この考えも動的計画法かはわからんが、思考自体は、
「想定される最適解に近付くように、解を組み立てていく」
というもの。

やっぱり問題が簡単すぎるな。1は動的計画法のアルゴリズム自体を
知りたいのか、設問を解きたいのか、どっちなのだ?

11 :デフォルトの名無しさん:01/09/26 21:35
数字の順番変えちゃいけないんじゃないの?

12 :デフォルトの名無しさん:01/09/26 21:41
>>11
なんで?つか、数字の順番変える事に意味は無いだろ。
単に整頓されてるかされてないかの違いなだけで。

こういうのは、問題の本質を抽出する(ソートが本質かそうでないかを
判断する)事が肝要だから、11はこういう話には向いてないんじゃない?

13 :デフォルトの名無しさん:01/09/26 22:02
>1
Nをそれぞれの数に対して積分してから変数変換してフーリエ変換してから偏微分。

14 :デフォルトの名無しさん:01/09/26 22:06
>>13
もはやあわれ。

15 :デフォルトの名無しさん:01/09/26 22:09
数列と集合を勘違いしてない?>>12
数列の要素には順番があるんだよ?

16 :1:01/09/26 22:10
1です。ちょっと返信送れました。
すみません。
まず、数字の順番を入れ換えてはいけません。
説明ぶそくで済みませんでした。

この問題のヒントみたいなのが載っていたのですが、
(これってヒントになるのか?ってレベルですが)
ヒント
例によって、木状に探索していく。整数列に仕切りをいれて2つに
分割することで木を一段深くする。その時、元の列がi個の分割
なら一段下がったところは、i_1個とi_2個の分割(ただしi_1+i_2=i)
になっている)
というヒントがついていました。

僕が考えるに動的計画法は、
1、同じことの繰り返しによる、無だを省く
2、ボトムアップ
ということが指針だということなので、

17 :1:01/09/26 22:19
まず、
1,2,3,4,5(数字はアイテム番号とする)
というアイテムを分割することを考える。
ここで、
(1,2)(3,4,5)と(1),(2,3,4,5)
という分割を考え、
さらにこれから先の分割を考えるとき、
一つ目の分割で、
1+2 < 3+4+5
とすると、
明かに(3,4,5)を次は分割しようとするはずである。

ここで、2つ目の分割
(1)(2,3,4,5)
をさらに分割しようとすると、
すでに最初の分割(1,2)(3,4,5)

1+2 < 3+4+5
ということが分かっているから、
(1)(2)(3,4,5)
という分割パターンは最初から、考えなくていいということになり、
計算時間が短縮できる。
ということだと思います。

これをアルゴリズムとして、気持のいい形にかきたいんだけど、
どうやったらいいのかな?って思って悩んでいます。

(もっといい考え方+拡張があれば教えてください!)

18 :11:01/09/26 22:19
ざまみろ 12>>
お前の方が向いてないんだよ。

19 :1:01/09/26 22:21
勿論2は僕じゃないです。
あと、有益なヒントとして、以下の情報を持っています。

動的計画法を適用できる多くの問題にもれず,
この問題も部分問題によって(定式化にしたがった)木を構成できます.
そこでこの木の根に相当する問題の解を求めるというのが
我々の目的なんですが,
動的計画法ではこの木の一番下の子の部分から
ボトムアップ式に解を覚えつつやっていこうというのが
方針だと思われます.

ちなみに O(kn^2) でできました.
(たぶんこれが正解でしょう)

20 :デフォルトの名無しさん:01/09/26 22:23
問題がよくわからん。
「グループに含まれる数の和を最小」ってどういうこと?
文面通り受け止めると、
1,2,3,4,5,6,7,8→1|2|3|4|5|6|7|8
グループに含まれる最小の数:1、最大の数:8

21 :1:01/09/26 22:26
問題はかなり抽象的というか、数学ぽい考えというか
難解な感じで、説明しにくいです。
でも、これが、与えられた問題で、一字たりとも変えていません。

まず、
k個の「仕切り」のkは定数です。
また、nも定数です。

プログラマの皆さんは、アルゴリズムに熟知してらっしゃると
思うのですが。

22 :デフォルトの名無しさん:01/09/26 22:29
この問題の意味がわからないというのは、かなりヤバいと思うが。。

23 :1:01/09/26 22:30
最初にあった例では、
仕切りが2つ、グループは3つですよね。

この整数の数を増やしていくと、
それを例えば4つの仕切りで分割しろといわれても、
最適なものを調べるには、
全部総あたりで、計算すると大変なことになりますよね。

これを動的計画法で解決したいのです。

動的計画法の詳しい説明はかんべんしてください。

24 :デフォルトの名無しさん:01/09/26 22:36
つーか課題?

25 :やばい20:01/09/26 22:39
しきりの数は任意?

26 :1:01/09/26 22:43
>>24
そうです。〆切明後日です。
結構考えてるんですが、できない。

>>25
仕切りの数は定数kです。

これを機会に動的計画法について勉強してみたらおもしろいと思います。

27 :やばい20:01/09/26 22:48
kが変数だと思ってた……鬱氏

28 :1:01/09/26 22:49
結構動的計画法ってはまるとおもろいですね。
感想だけなのでさげ

29 :デフォルトの名無しさん:01/09/26 23:08
あげ

30 :  :01/09/26 23:27

1)グループの和が総和/kなら部分的に最適とは言える。
2)全てのグループの和が総和/kなら最適。
3)全てのグループの和と総和/kの差が(総和/kの余り)/k+1
以内であるなら最適。

つうことで後よろしく。

31 :デフォルトの名無しさん:01/09/26 23:49
動的計画法のからみは?

32 :デフォルトの名無しさん:01/09/27 00:45
>>1
動的計画法にうってつけの問題ですね
簡単に出来ますよ。ただ説明を書くのは辛いです。
ソースなら提示できそうですが……

>>30さんの方法は、これだけの文面ではよくわからないのですが、
もうちょっと詳しく教えてもらえませんか?

33 :デフォルトの名無しさん:01/09/27 00:47
PTASとかFPTASとか超懐かしいねえ。10と30はヴァカだけど。

34 :トリッキーの1:01/09/27 01:23
寝る前に頑張って説明してみよう。

例えば、15,3,7,6,10,4,13,2,3,6 という10個の数に、
区切りを3つ入れる場合について考えてみます。
この場合、下の図のようなテーブルをプログラムで作成すればいいわけです。
(等幅で見てね)

15 3 7 6 10 4 13 2 3 6
区切り残り0:10,69 9,54 8,51 7,44 6,38 5,28 4,24 3,11 2, 9 1, 6
区切り残り1: 4,38 4,28 4,27 3,24 2,24 2,17 1,13 2, 6 1, 6 1, 6
区切り残り2: 3,25 2,24 3,23 2,17 2,14 1,13 1,13 1, 6 1, 6 1, 6
区切り残り3: 2,23 3,16 2,14 1,14 1,13 1,13 1,13 1, 6 1, 6 1, 6

例えば左下の(2,23)が何を表しているかというと、
「区切りがまだ3つ使える場合、
  次の最適な区切りはここから2つ目の場所、
  その場合の最大値は23になりますよ」
という事です。すなわち、1つ目のグループは[15,3]が正解だと解るわけです

これがわかれば、問題は、
「7,6,10,4,13,2,3,6 という8個の数に区切りを2つ入れる」
という風に変わります。
その場合は(3,23)、すなわち2つ目のグループは[7,6,10]とわかります。

このように追っていくと、答えは[15,3]、[7,6,10]、[4,13]、[2,3,6]となります。
(続く)

35 :トリッキーの1:01/09/27 01:24
さて、このような表をどうつくるかという問題ですが、
それは自分で考えてください。

ヒントは、
・区切り残り0の場合は単純計算です。
・区切り残りNの場合が解っていれば、N+1の場合もわかります。

例:(等幅)
区切り残り4: 1,16 1,14 2,13 1,13 1,13 1,13 1,13 1, 6 1, 6 1, 6

数学的帰納法により、全ての場合の表が求まります。

わかりにくいかもしれませんが、もし動的計画法の知識があれば、
割合すんなりと読めるのではないでしょうか?甘い?>>1さん

36 :デフォルトの名無しさん:01/09/27 01:28
>>22
つうか、問題文に厳密さがかける、っていうのが真実だろ。

「n個の任意の自然数からなる数列 i_1, i_2, ..., i_nがある。この
整数列をk個の「仕切り」によってk+1のグループに分割し、グ
ループに含まれる整数の和を最小にしたい。kは0以上n-1以下の
定数で、任意に指定することができるとする。動的計画法により
最適な分割を求めるアルゴリズムを開発せよ。」

こんなかんじか?

37 :デフォルトの名無しさん:01/09/27 01:48
>>34-35
なるほどね。動的計画法というものが理解できた。計算量はO(KN)程度かな。

38 :デフォルトの名無しさん:01/09/27 02:04
>>34, >>35
なるほどなるほど。解き方はわかったつもりなのだが、テーブルの1列目以外
を求めているのはなぜ?

39 :デフォルトの名無しさん:01/09/27 02:26
2列目以降がないと、1列目は出ないからじゃない?
同じく3列目以降がないと、2列目が出ないし。
だから、N列目から1列目に向かって解いて行くんだと思う。

40 :デフォルトの名無しさん:01/09/27 03:09
俺も良くわからないけど、
確実にいえることは
0列目の情報は、計算しなくてもわかるので
入力とみることができて、
K列目までがわかれば、答えが出る
そういうわけで、39の言ってる事は正反対です

基本的には
一番右から順番に
数列の数が1個の場合、2個の場合・・・
を考えていくみたいだけど

41 :40:01/09/27 03:20
補足しておけば、第4列を求める場合
右から13,2,3,6だけの場合考える余地が無い
この4つの数の列に
4を付け加えることを考えると

この5つの数の列に
10を付け加えることを考える
この時の最適な区切り線を計算するには
区切り線を10の右につけた場合を考えると
第4列なので残り3本線を引くのだが、
10を取り除いた数列4,13,2,3,6
に3本線を引くときの最適な場所はすでに3列目で計算している
そして、その最大値と10を比較すれば・・・
このように、以前の計算を利用していくのだと思う

42 :学生でもOBでもなんでもないけどさ:01/09/27 03:21
>>1
技術科学大学スレで7系の人にたずねるとよいぞ(ワ

43 :デフォルトの名無しさん:01/09/27 03:21
>>40
列と行を勘違いしているっぽいけれど?
列は縦、行は横だよ

つーか厨房なので、ソース見せて下さい(涙)>>34

44 :40:01/09/27 03:23
>計算量はO(KN)程度かな
違うと思う

45 :40:01/09/27 03:26
確かに(w
行と列逆に使ってる

46 :1:01/09/27 10:36
今、起きて、犬の散歩から帰って来たところです。
みなさん、いろいろな御説明ありがとうございます。
今から学校に行かなければいけませんので、学校
のいきかえりと学校で、このスレを参考にひたすら考えます。

>>32=34 さん?
>ソースなら提示できそうですが……
どうかお願いします。動的計画法にはまってきたので、
いろいろ調べたいです。

47 :デフォルトの名無しさん:01/09/27 10:46
教えて君じゃないことを証明するために、
46の書いたコードを公開せよ

48 :1:01/09/27 13:30
>>47
アルゴリズムを考えているので、コードは考えていないですよ。

49 :1:01/09/27 14:52
age

50 :デフォルトの名無しさん:01/09/27 15:22
>>36
自然数などという条件は付いてないと思うが。

51 :トリッキーの1:01/09/27 17:01
>>1
あと1日考える価値のある課題だと思いますよ。
動的計画法の、しょうもないナップザック問題などに比べて、この課題はとても良くできています。
動的計画法にはまっているのであれば、この問題に是非挑戦してみてください。
(それに、安易に課題の解を求める人たちが増えても困りますから)

もし私の説明がわかりにくければ、とりあえずネットで「ナップザック問題」等で検索をかけ、
その説明と併せて読んで貰えるとわかるんじゃないかと思います。

頑張ってください。

>>38
39さんが言っているように、自分より右かつ上であるセルが全てわからないと
自分自身のセルが解けないためです。
右側から解いていっても、上側から解いていっても、本質的には同じです。
for文の順序が入れ替わるだけですね、きっと。

52 :1:01/09/27 17:12
ナップサックもついこないだやったばっかなので、頑張ります。

53 :1:01/09/27 17:57
やっと理解できました。次は、計算量の評価ですが、これが
いままで、やったことがないんです。

54 :11:01/09/27 18:26
【前処理】
1)期待される最小のグループ和(総和/グループ数)を求める。
2)数列の頭からみていって「期待されるグループ和」を超えた所に壁を作っていく。
  これが初期の遺伝子。

【メイン】
3)100本の配列を用意してこの遺伝子をコピーする。
4)乱数によって壁をひとつ選びこれを左または右に(乱数で決定)移動する。
5)最良の結果が出ればこれを別の配列に保存しておく。
6)この操作を100本の配列について100回行う。

7)100本の配列の中味を今までの最良の結果に置き換え、(3)〜(6)を繰り返す。

3)〜7)を数回繰り返せば最良の結果が出て来るだろう。

55 :デフォルトの名無しさん:01/09/27 18:31
が?

56 :デフォルトの名無しさん:01/09/27 18:33
これって遺伝的アルゴリズムと関係ありそうですね

57 :11:01/09/27 18:37
7)見込みのない50本の配列の中味を今までの最良の結果に置き換え、(3)〜(6)を繰り返す。
  −−−−−−−−

にした方が面白いかな。

58 :デフォルトの名無しさん:01/09/27 18:39
Genetic Argorithm風アルゴリズム?
>4)乱数によって壁をひとつ選びこれを左または右に(乱数で決定)移動する。
このへんがGAじゃないね
最適化問題といえばGAだけど!?
でも、動的計画法の方が計算量が明らかに少ないね
この場合は・・・

59 :11:01/09/27 18:44
よく知らないんですが「ナップザック問題」で検索して出てきた頁を読んで思いついたものです。

60 :デフォルトの名無しさん:01/09/27 18:50
58
そんなことするよか、全部のパターンを確かめた方が速いでしょ?
数が多すぎて全部のパターンを確かめられない上に、
適切なアルゴリズムが存在しない時に
初めて意味がある
最近は制御系にも応用され始めてる

61 :やっぱり向いてない11:01/09/27 19:03
「動的計画法」とやらを全く理解していないもんで。失礼しました。

62 :デフォルトの名無しさん:01/09/27 20:50
結局、7が一番面白い

63 :デフォルトの名無しさん:01/09/27 21:40
う〜ん、途中参加だが、俺も計算量が気になって来たぞ。
どんくらいに圧縮されるんだ?
ちなみに総当たりだと、指数的数字になるなあ。

64 :56:01/09/27 23:24
関係ありそうだけどなさそうだった 死農

65 :デフォルトの名無しさん:01/09/27 23:27
たいていのプログラマーってアルゴリズムに精通してないと思われ
だって、使う機会ほとんどないもん
一流大学でてるインテリ学生の一部でしょ
そういうのに詳しいのは
でもって、そういうのが一流プログラマなんだけどね

66 :1 :01/09/28 00:21
1です。計算量が求まりません。
噂では、 O(kn^2)だそうですが。なぜ?
締め切りまで12時間きりました。

しかし、このアルゴリズム、はまったけど、まとめあげる
の大変やった。A4*3枚も説明に費した。
けど、他人が読んで分かるかなあ?
明日、また読み直して、書き直すかも?
お休みなさい。プログラマの皆さん。

67 :デフォルトの名無しさん:01/09/28 00:32
Σ(1+2+・・・n)
=((n+1)n/2)k>=計算量

68 :トリッキーの1:01/09/28 01:59
>>67
多分わかっていると思われるのですが、1さんへの説明チックに書きます。
計算量において、/2とか+1とかいう概念は存在しません。
あくまでもオーダーなので、定数プラスや定数倍などは評価されません。
だから、nlognの場合も、「logの底って何だろう?」という事はナンセンスになります(何でもいいんです)
最終的に67さんの式は、結局O(kn^2)となります(なぜその式が出るのかの考察はまだしていませんが)。

>>1
実際にコードを書いてみて、そのfor文に注目すると、計算量は(概算で)出ます。
理論で証明しようとするととたんに面倒になりますが、もしそれを授業でやっていないなら
実際にソースコードを示して、そこから計算量を示す方法が現実的でしょう。
ちなみに、私は(証明はしてませんが)O(kn^2)だと思っています。

>>65
例えば動的計画法なんて、まず普通しらないし、実際の場面で応用する機会もまずありません。
しかし、使用できる道具がいくつかあるというのは選択肢を広げる上で非常に重要だし、
実際に、まず実世界で使わないと思っていた「巡回セールスマン問題」なども、流通業界の仕事で
使用したという経験もあります(時間軸に従ったグラフを利用)

過去の人たちが様々な証明を行ってくれている方法なので、応用できる場面にて
数学的考証をしなくてすむので、知っていればいるほど応用範囲が広がるかと。
決して「一流大学を出ているインテリだけが知ってろ」などと思わずに、
機会があれば学んで貰えればと思います。

とはいえアルゴリズムオタクってのは、応用になれば途端に使えなくなるのが
常ですよね。まさに頭でっかち。
そういう意味では、一般社会で経験を積んだプログラマこそが一流なのかもしれません。

酔っているから支離滅裂で失礼。

69 :デフォルトの名無しさん:01/09/28 23:12
課題の締切もすぎたことだし、
ソースをみせてくれないですか?>>68

70 :1 :01/09/28 23:18
レポート出しました。今回は本当にいろいろ
教えて頂きありがとうございました。
ソースは作成できませんでしたが(今日締め切り4本抱えていたため
余裕無しでした)動的アルゴリズムについては、かなり
いい感じに理解できたと思います。
なかなか面白い発想ですし、これから、リアルタイムに
使って行けたらいいなあ、と思います。

71 :デフォルトの名無しさん:01/09/29 00:11
結局理解できてないわけ?
言い訳書いてるだけで、アンタからは技術的な発言無かったし

72 :デフォルトの名無しさん:01/09/29 00:50
>>71
一年生なんだから仕方ないと思われ

73 :デフォルトの名無しさん:01/09/29 01:07
もう終わっちゃったのかもしれないけど、私の予想。

最初はすべての整数が区切られているものとする。
整数がn個あるので区切りはn-1個あるとする。
もちろんこのときは分割は最適です。
さて、ここから区切りを一個取り除いても分割が最小になるには?
と考えて、ある区間内ににおける総和を求めて、その右にある区間における総和と足し合わせます。
その値が過去に調べたいずれの値よりも最小になるのが最適な「区切り」の取り除き場所です。
最小になるかどうかの調べかたは簡単ですよね。
で、一個取り除いたところでこれは区切りn個の時点で最適な分割になっています。
同じ手続きでさらに一個ずつ取り除いていき、k個の区切りになったところで終了。

間違ってるかも?

74 :デフォルトの名無しさん:01/09/29 01:19
はー、よく考えてから書けっつーの
アルゴリズムは上の方にでてるから・・・・
それ読んでみれば、間違ってんのすぐ気づくよ

75 :73:01/09/29 01:40
>74
お、間違ってると指摘されたよ。
かなり自信あったんだが。
他の人はどう思う?

76 :デフォルトの名無しさん:01/09/29 02:15
>73
だいたい、その日本語じゃわからないって(笑)
人としゃべったことある君?

77 :デフォルトの名無しさん:01/09/29 04:02
>>73
区切りのパターンが k→k+1 で複数変化する場合があるので、
(e.g.)
4 5 | 2 7 (k=1)
4 | 5 2 | 7 (k=2)

Greedyなアルゴリズムが常に最適解を与えるとは限らない。

78 :デフォルトの名無しさん:01/09/29 04:08
>>73

6 3 1 3 6 9  を3つに分けるとすると


6 3 1 3 6 9  (スタート)
 ^ ^ ^ ^ ^

6 3 1 3 6 9  (1個抜く)
 ^ ^   ^ ^

6 3 1 3 6 9  (2個抜く)
 ^     ^ ^

6 3 1 3 6 9  … 結果、最大13となるが
 ^       ^

正解は

6 3 1 3 6 9  … 最大10である。
   ^     ^

79 :78:01/09/29 04:27
さらに2つに分ける場合だと、78を受けて

6 3 1 3 6 9  … 最大19
         ^
一方、正解は

6 3 1 3 6 9  … 最大15
       ^

80 :デフォルトの名無しさん:01/09/29 04:40
73の日本語がわけわかんないのは言うまでもないけど
もし、これがグリーディーなアルゴリズムなら
>お、間違ってると指摘されたよ。
>かなり自信あったんだが。
>他の人はどう思う?
の発言は痛すぎる(w
とりあえず、書き込む前に考えないとね

81 :デフォルトの名無しさん:01/09/29 07:34
オセロやチェスは総当りでもOKだろうけど、
将棋ってこういう考えかたしないと、
とてつもない量の計算になるよなぁ

82 :デフォルトの名無しさん:01/09/29 07:46
>>81
かなりずれてると思われ。

83 :トリッキーの1:01/09/29 08:25
それじゃソースあげておきます。
申し訳程度のコメントしかついていません。
改行少なくするため、つめて書いていますが許してください。
せっかく公開するんだから、もしバグがあったら、是非教えてくださいね

#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)
// 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;}

84 :73:01/09/29 09:27
あらら間違ってたか。
>78
ありがとう。

85 :デフォルトの名無しさん:01/09/29 10:48
ゲームの思考ルーチン作ってるとき「あこりゃ巡回セールスマン問題だ」って
気付いたことがあった。時間なかったからほっぽったけど。

86 :デフォルトの名無しさん:01/09/29 14:30
>「あこりゃ巡回セールスマン問題だ」って気付いたことがあった
巡回セールス問題の最適解を求めるアルゴリズムはないです

87 :デフォルトの名無しさん:01/09/29 14:58
最適解以外は意味無いとでも思ってる?

88 :デフォルトの名無しさん:01/09/29 15:05
>>86
多項式のオーダで求めるアルゴリズムがない、ね。
>>85はそれは分かってて時間がないから放置したんだと思われ。

89 :デフォルトの名無しさん:01/09/29 17:51
>>81
将棋もオセロもどう考えても総当りじゃ無理だぞ。

90 :デフォルトの名無しさん:01/09/29 20:15
将棋とかオセロとかだと幅優先探索でやるのかな?
ゲームによっては探索する深さが指定できるでしょ?
深読みすれば強いAIってことで。

ちゃんとした強いAIにしたければニューラルネットとかGAとかを使うのかなぁ?

91 :デフォルトの名無しさん:01/09/29 20:51
GAだって(笑)

92 :デフォルトの名無しさん:01/09/29 21:46
>>90
 まあ、将棋とかオセロは基本的には幅優先探索。
 あとは、いかに枝刈りするかという話しになります。

 GAって遺伝的アルゴリズムのこと?
 ニューラルネットとかじゃ、現状ではまっとうなゲームプレイヤー
は作れてないと思います。

93 :デフォルトの名無しさん:01/09/29 23:40
関係無いけど、チェスの世界チャンプに勝ったスパコン(ディープブルーだっけ?)
あれって、動的計画法?それとも、総当り?

94 :93:01/09/29 23:51
http://www-6.ibm.com/jp/rs6000/resource/deepblue/
こんなの見つけたけど、どうなんだろう?
棋譜を参照にするってことは枝切りしてるのかな?序盤と終盤だけは、
それ以外は総当りで

95 :デフォルトの名無しさん:01/09/30 00:18
>動的計画法?それとも、総当り?
2択かい?(笑)

96 :デフォルトの名無しさん:01/09/30 00:20
>>93
スレ違いなので、下げます。

えっと・・・。総当りという言葉をどういう意味で使ってる
かわからないけどミニマックス法、αβ法、静的評価関数とい
ったあたりの話しは大丈夫?知らなかったら検索かけてみて。

 序盤では人間が定石を使うような感じで棋譜を利用する。
 こういう探索問題で一手深く読むためには、下手すると何
十倍という時間がかかってしまうのね。で、終盤検索かけて
るときに、「この局面になったらもう勝ちだ」とか、「この
局面になったら負けだ」とかいう情報があると、その局面に
ついては最後まで読んだことになるから、すごく効いてくる
らしいのね。
 コンピュータの強みは物量作戦だっていう事ですね。

97 :デフォルトの名無しさん:01/09/30 02:02
ぶり返すようで悪いんだけど..
>>34
[15,3]、[7,6,10]、[4,13]、[2,3,6]
って答えはあってるの?
>>8のアルゴリズムで解くと
[15,3]、[13,4]、[10,6,2]、[7,6,3]
ってなるけど。各箱の数値の合計の最大値が
最小になるように仕分けるんだよね?

98 :デフォルトの名無しさん:01/09/30 02:22
>>97

>>16 で 1 が数字の順番は入れ換えちゃだめ、って言ってるから
>>34 の答えでたぶん合ってるんじゃなかろうかと。

99 :デフォルトの名無しさん:01/09/30 02:50
すいません…
勘違いしてました…。

100 :デフォルトの名無しさん:01/09/30 03:40
>>99
なんで100にも届こうか問いスレなのに、
いまだに問題を理解してないやつが居るわけ?

101 :デフォルトの名無しさん:01/09/30 16:54
>>93
動的計画法でゲームのAIは大抵無理でしょう。つーか理解してないでしょ。
総当たりのうち、どれだけ効率的に枝切りをするかという問題じゃないの?
それとももっとエレガントな方法があるのかな?

どうでもいいけど、課題教えてスレが、なぜか優良スレになってしまったのはどうして?

102 :デフォルトの名無しさん:01/09/30 17:11
>課題教えてスレが、なぜか優良スレになってしまったのはどうして?
1がコテハンじゃなかったから

103 :デフォルトの名無しさん:01/09/30 17:14
動的計画法は奥が深いから

誰か他の問題もあげてくれ
マージソート、クイックソートも動的計画法でいいんだよね?
分割統治法っていうんだっけ?

104 :デフォルトの名無しさん:01/09/30 17:19
トリッキーの1が出てきたから。

>>103
分割統治法というのは、動的計画法とは正反対の手法じゃないの?
一般的なバックトラックみたいな。マージ/クィックソートも。

105 :デフォルトの名無しさん:01/09/30 17:19
アルゴリズム板が無いっていうのがそもそも間違ってるんだよな。

106 :デフォルトの名無しさん:01/09/30 17:23
でもそんなに頻繁にアルゴリズムの話題出てないし

107 :デフォルトの名無しさん:01/09/30 17:24
グリーディーアルゴリズムって?

108 :デフォルトの名無しさん:01/09/30 17:30
試行錯誤によって解を得ようとするアルゴリズム。別名力技。
かかる計算量などを一切無視して作られるアルゴリズム。

グリーディー:貪欲な

109 :デフォルトの名無しさん:01/09/30 17:35
>かかる計算量などを一切無視して作られるアルゴリズム
嘘の情報流すのやめようよ

110 :108:01/09/30 17:42
>>109
ゴメ、俺はそう信じてた。>>107さん、嘘らしいですごめんなさい

111 :デフォルトの名無しさん:01/09/30 17:56
簡単なので良かったら(高校数学レベル)

1からnまでの数字を1回だけ使って並べて、n桁の数字を作る。
出来る数字を、辞書的に並べた場合、m番目に来る数字は何か

mとnは定数

112 :111:01/09/30 17:57
スマヌ、日本語オカシイ

n桁の数字>n桁の数
出来る数字>出来る数

113 :デフォルトの名無しさん:01/09/30 18:01
3だったら、
123
132
213<-
231
312
321
って事?

114 :113:01/09/30 18:02
あ、ゴメ、n=3、m=3の場合

115 :デフォルトの名無しさん:01/09/30 18:03
基数ソートでいいのかな?
高校数学ってどこらへんが?

116 :デフォルトの名無しさん:01/09/30 23:09
nは最大でも9。そのときでもmは最大で362800。
ってことは、一回テーブル作っとけば充分じゃん。

117 :デフォルトの名無しさん:01/10/01 01:23
>nは最大でも9
かわいそう・・・
大学卒業してないみたい

118 :111:01/10/01 07:43
>>113
そういうことです。

>>116
君の頭の中では十六進数は無いんだね

119 :デフォルトの名無しさん:01/10/01 12:15
高校数学って16進習ったっけか?

120 :111:01/10/01 16:42
高校じゃ習わないな、良く考えたら
っていうか、ム板来てて16進解らないんならホントかわいそう

121 :デフォルトの名無しさん:01/10/01 17:07
二進数は中学で習う

122 :デフォルトの名無しさん:01/10/01 17:32
>>117
高卒プログラマですが何か?

123 :デフォルトの名無しさん:01/10/01 19:07
階乗使って上のケタから決定していくのかな。

16進がありならnは数学の立場からすれば何でもいいんでしょうね。
たまたまコンピュータの都合で16進がポピュラーになっただけだから。

124 :デフォルトの名無しさん:01/10/02 00:42
なんで16にこだわってるんだろ
馬鹿ばっかり

125 :デフォルトの名無しさん:01/10/02 02:08
>>124=116
16はnの例だろ。

126 :デフォルトの名無しさん:01/10/06 13:21
あげ

127 :名無しさん:01/10/07 02:29
n進法は中学で習ったんじゃないですか?今はしらんです。

128 :デフォルトの名無しさん:01/10/08 18:26
習った覚えがあるけど10をこえた記憶は無い
そろばんが5進数+2進数とかやってた記憶がある

129 :デフォルトの名無しさん:01/10/08 18:28
10超えようが超えまいが関係ない。
A-Fを使うのは表現(符号化)の問題なので、
n進法とは別の問題

130 :デフォルトの名無しさん:01/10/25 00:33
>>1
動的計画法の練習問題としていい問題ですね.
ただし,k が大きくて,i_1, i_2, ... , i_n がさほど大きくなければ,
目的関数の値の上界と下界を求めて,目的関数の値に関して2分探索かけた方が
早い?(自信なし)

ちなみに与えられた数の入れ替えを許すと Knapsack や Bin Packing 系の
NP困難問題になる.まあ,その場合でも擬似多項式時間の,動的計画法の
アルゴリズムはある.そっちが宿題だったら院生レベルかな.

36 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)