[ツリー表示へ] [ワード検索] [Home]
タイトル ： Re^12: 組み合わせ合計検索 つづき 投稿日 ： 2023/08/30(Wed) 18:12 投稿者 ： 魔界の仮面弁士
| > たとえば 1, 2, 3, 4 の4 つの数値のすべての組み合わせから合計値 5 を探索する場合、 > 探索(5, New Integer() {1, 2, 3, 4}) > の呼び出しにより、Dim root As Node に対して下記の構造が格納されます。 もしも、{ 1, 2, 3, 4 } という 4 つの値すべての組み合わせを得る実装にしていたのであれば、 こういう階層結果が得られていたわけです。 root ┣Value=1 … 1 = 1 不足 ┃┣Value=2 … 3 = 1 + 2 不足 ┃┃┣Value=3 … 6 = 1 + 2 + 3 ◇超過 ┃┃┃┗Value=4 … 10 = 1 + 2 + 3 + 4 ◇超過 ┃┃┗Value=4 … 7 = 1 + 2 + 4 ◇超過 ┃┣Value=3 … 4 = 1 + 3 不足 ┃┃┗Value=4 … 8 = 1 + 3 + 4 ◇超過 ┃┗Value=4 … 5 = 1 + 4 ★合致 ┣Value=2 … 2 = 2 不足 ┃┣Value=3 … 5 = 2 + 3 ★合致 ┃┃┗Value=4 … 9 = 2 + 3 + 4 ◇超過 ┃┗Value=4 … 6 = 2 + 4 ◇超過 ┣Value=3 … 3 = 3 不足 ┃┗Value=4 … 7 = 3 + 4 ◇超過 ┗Value=4 … 4 = 4 不足 実際には、合計値が超過した枝はそれ以上生やす必要が無いので、 『If nextNode.Total <= targetValue Then』の枝刈りロジックにより、 ◇部は生成されず、下記の構造だけが残ります。 root ┣Value=1 … 1 = 1 不足 ┃┣Value=2 … 3 = 1 + 2 不足 ┃┣Value=3 … 4 = 1 + 3 不足 ┃┗Value=4 … 5 = 1 + 4 ★合致 ┣Value=2 … 2 = 2 不足 ┃┗Value=3 … 5 = 2 + 3 ★合致 ┣Value=3 … 3 = 3 不足 ┗Value=4 … 4 = 4 不足 この場合、合計 5 になる組み合わせとして本来は 1+4 と 2+3 の 2 種類が存在するわけですが、 探索の高速化のため、最初の組み合わせが発見された時点で edge を確定させ、 それ以降は「If Not edge Is Nothing Then Return」によって捜索を打ち切る実装になっています。 そのため、root 変数および edge 変数の階層構造は、下記のようになります。 root ┣Value=1 … 1 = 1 不足 ┃┣Value=2 … 3 = 1 + 2 不足 ┃┣Value=3 … 4 = 1 + 3 不足 ┃┗Value=4 … 5 = 1 + 4 ★合致(edge 変数) ┣Value=2 … 2 = 2 不足 ┣Value=3 … 3 = 3 不足 ┗Value=4 … 4 = 4 不足 上図の通り、終端となる edge.Value は 4 を返します。 その親階層を辿ると、edge.Parent.Value は 1 になっています。 さらにその親階層である edge.Parent.Parent は root に当たります。 このことから、この edge は 2 階層であり、それが 1 + 4 の組み合わせを意味しているのだと分かります。 なお、root.Value や edge.Parent.Parent.Value は 0 なので無視できます。 また、root のさらに親は存在していないため、root.Parent や edge.Parent.Parent.Parent は Nothing です。 > なお、たけしさんが書かれた「Dim a As Integer = 0」のカウントアップは、 > 詳細値の数を意味していないので、実装として間違っています。これについては後述。 残念なことに、たけしさんが書かれた「a = a + 1」のカウント方式は、 組み合わせた詳細値の数（Node の階層数 N）を表す処理にはなっていません。 実際には、兄弟の番号をカウントアップしているだけの処理になっています。 (すなわち、N 階層目における A 番目の要素、の意味) たとえば『探索(5, New Integer() {1, 2, 3, 4})』の場合、 現状の Dim a As Integer は下記のようにカウントされています。 Root ┣Value=1 … a = 1 (階層数=1) Total = 1 ┃┣Value=2 … a = 1 (階層数=2) Total = 3 ┃┣Value=3 … a = 2 (階層数=2) Total = 4 ┃┗Value=4 … a = 3 (階層数=2) Total = 5 ┣Value=2 … a = 2 (階層数=1) Total = 2 ┣Value=3 … a = 3 (階層数=1) Total = 3 ┗Value=4 … a = 4 (階層数=1) Total = 4 そして、『探索(1230, 値一覧3)』の場合は下記の結果になるでしょう。 それゆえ探索終了時に詳細値が 15 個あっても、MsgBox(a) には「8」と表示されてしまうのです。 Root ┣Value=36 … a= 1 (階層数= 1) Total= 36 ┃┣Value=40 … a= 1 (階層数= 2) Total= 76 ┃┃┣Value=45 … a= 1 (階層数= 3) Total= 121 ┃┃┃┣Value=51 … a= 1 (階層数= 4) Total= 172 ┃┃┃┃┣Value=55 … a= 1 (階層数= 5) Total= 227 ┃┃┃┃┃┣Value=65 … a= 1 (階層数= 6) Total= 292 ┃┃┃┃┃┃┣Value=69 … a= 1 (階層数= 7) Total= 361 ┃┃┃┃┃┃┃┣Value=76 … a= 1 (階層数= 8) Total= 437 ┃┃┃┃┃┃┃┃┣Value=82 … a= 1 (階層数= 9) Total= 519 ┃┃┃┃┃┃┃┃┃┣Value=98 … a= 1 (階層数=10) Total= 617 ┃┃┃┃┃┃┃┃┃┃┣Value=106 … a= 1 (階層数=11) Total= 723 ┃┃┃┃┃┃┃┃┃┃┃┣Value=108 … a= 1 (階層数=12) Total= 831 ┃┃┃┃┃┃┃┃┃┃┃┃┣Value=115 … a= 1 (階層数=13) Total= 946 ┃┃┃┃┃┃┃┃┃┃┃┃┃┣Value=116 … a= 1 (階層数=14) Total=1062 ┃┃┃┃┃┃┃┃┃┃┃┃┃： ┃┃┃┃┃┃┃┃┃┃┃┃┃┣Value=119 … a= 3 (階層数=14) Total=1065 ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┣Value=123 … a= 1 (階層数=15) Total=1188 ┃┃┃┃┃┃┃┃┃┃┃┃┃┃： ┃┃┃┃┃┃┃┃┃┃┃┃┃：┗Value=165 … a= 8 (階層数=15) Total=1230 ★これが edge ┃┃┃┃┃┃┃┃┃┃┃┃：┗Value=186 … a=13 (階層数=14) Total=1132 ┃┃┃┃┃┃┃┃┃┃┃：┗Value=186 … a=14 (階層数=13) Total=1017 ┃┃┃┃┃┃┃┃┃┃┃┗Value=186 … a=15 (階層数=12) Total= 909 ┃┃┃┃┃┃┃┃┃：┗Value=186 … a=16 (階層数=11) Total= 803 ┃┃┃┃┃┃┃┃：┗Value=186 … a=17 (階層数=10) Total= 705 ┃┃┃┃┃┃┃：┗Value=186 … a=18 (階層数= 9) Total= 623 ┃┃┃┃┃┃：┗Value=186 … a=19 (階層数= 8) Total= 547 ┃┃┃┃┃：┗Value=186 … a=20 (階層数= 7) Total= 478 ┃┃┃┃：┗Value=186 … a=21 (階層数= 6) Total= 413 ┃┃┃：┗Value=186 … a=22 (階層数= 5) Total= 358 ┃┃：┗Value=186 … a=23 (階層数= 4) Total= 307 ┃：┗Value=186 … a=24 (階層数= 3) Total= 262 ：┗Value=186 … a=25 (階層数= 2) Total= 222 ┗Value=186 … a=26 (階層数= 1) Total= 186 |
をクリックするとツリー全体を一括表示します） - 組み合わせ合計検索 つづき - たけし 23/08/11-06:34No.12125