8
<<
<
>
>>
1/1
1 yama
2010/08/02(月) 00:43:58 ID: STKZ8TK7Fj
パスカルの三角形は、
nCr=n-1Cr-1+nCr
→ nCr=n-1Cr-1+n-1Cr
^^^
ではないでしょうか.
2 yama
2010/08/02(月) 01:20:28 ID: STKZ8TK7Fj
^^^がずれました.
n-1Cr の n-1の下に書いたつもりです.
3 nodchip
2010/08/02(月) 10:09:53 ID: tvVCz76rNQ
>>2
御指摘ありがとうございます。修正いたしました。
4 ななしのよっしん
2010/08/19(木) 17:42:26 ID: /76r25pouO
08年初頭だったかな「巡回セールスマン問題」というタグを
無差別につけて回っているヤツがいたようだけど
暇だったから全部辿って消してやった
5 ななしのよっしん
2015/06/15(月) 12:24:30 ID: mHY6ycBXXG
自分に意味がわからなかったから勝手に意味を変える編集者スゲー
最適解はどこへ行った
6 ななしのよっしん
2016/12/18(日) 23:35:04 ID: VHW4OHtJrF
ここの定義だと単に漸化式とか再帰的アルゴリズムのことを言ってるだけだよな。
必須定義:
* 問題全体は部分部分の結果を足せば出る
* 一度解いた問題は二度解かない <- これ重要
** 単に割ってくだけの作りだと同じサブ問題があちこちに出てダブることがあるので、その時は前の結果を使いまわす
必須ではないけどデフォ:
* そうやってベストケースな組み合わせを効率良く探す
7 ななしのよっしん
2016/12/19(月) 00:26:48 ID: VHW4OHtJrF
そもそも動的「計画法」という名前は、最終結果はとりあえず置いといて、先にどんな材料があれば答えが出るか決めちゃおうというところから来てる。
一般的にでかい問題は分割統治して、それぞれ別に作った結果を最後にがっちゃんこするってのがよくあるセオリーなわけだが、それぞれが完全に独立でやっちゃうと部品の共通化ができなくてすげー効率が悪いわけよ。だから元締め側でそこは管理して「これは余所で用意したのと一緒だからそれを使いまわす」という風に車輪の再発明をしないというのがミソなわけだ。
ただ普通の計画と違って部品を作りながら足りないところを増やしていくから動的だという言い方をする。
8 ななしのよっしん
2019/05/29(水) 17:23:23 ID: f880YqjIl6
<<
<
>
>>
1/1
ほめた!
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。