部分和問題の深さ優先探索

Question

c++を使って、部分和問題を深さ優先探索で書いています。
その際の再帰関数が分かりにくいのでご教授ください。
例は蟻本のp33です
bool dfs(int i ,int sum){
if(i==n) return sum == k;
// n個決め終わったら、sumがkと等しいかを返す
★sumが等しいかを返すならtrue or falseではないのですか？
★returnで何が返ってくるのかわかりません
if(dfs(i+1,sum)) return true;
★dfs(i,sum)はtrue なんですか？falseなんですか？　
★何をもってdfs(i+1,sum)の値が決まるのかがこの式から読めません。
if(dfs(i+1),sum+a[i])) return true;
return false;
}
void solve(){
if(dfs(0,0)) printf("Yes\m");
★なぜ0,0なんですか？
｝
素人質問ですみません。いろいろ調べまわりましたが、部分和のDFSについて詳しい説明がありませんでした。
何かわかりやすい解説があれば教えてください。よろしくお願いします。

Answer 1

★sumが等しいかを返すならtrue or falseではないのですか？
★returnで何が返ってくるのかわかりません

まず sum == k が「式」であることを理解しましょう。

式というのはプログラムにおいては評価され置換されるもののことを指します。以下が例です。(iは宣言済みとします。)

1 + 1
2 * 2
i
i++
++i

iに1が入っていれば、上から順に 2、 4、1 、1、 2 の値に置き換わります。

sum == k も同様に式です。この式は sum と k の値が同じであれば true、 違う場合は false に置き換わります。

if文の引数として渡される式に対しても、この「評価」が行われています。変数がくると変数も評価され値が置き換わります。よって以下のような書き方が可能です。

#include <iostream>

int main() {

  bool hoge = 1 == 2; // hogeにfalseが代入される

  if (hoge) { // hogeの評価値はfalseなのでelse以降を実行
    printf("同じ\n");
  } else {
    printf("違う\n");
  }

  return 0;
}

今回の場合、return文によって k == sum の評価された値が、dfs関数の返り値となります。したがって、 true または false の値が返されます。

★dfs(i,sum)はtrue なんですか？falseなんですか？
★何をもってdfs(i+1,sum)の値が決まるのかがこの式から読めません。

まず動くソースコードを。コメント、つけ直してみました(大して変わってないかも)
○1, ○2, ○3, ○4はソースコード以下の説明と対応しています。

wandbox: https://wandbox.org/permlink/AMrTofmWNM2RKDpA

#include <iostream>

const int MAX_N = 20;
int *a;
int n, k;

bool dfs(int i, int sum) {
  /*
    この再帰関数の深さがn(今回は4)であれば、最終的に合計値(sum)が目的の値(k...今回なら13)
    になっているかを返して終わり。
  */
  if (i == n) return sum == k; // ○1

  /*
    まだ深さが4ではないときに以下は実行される。
    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
  */
  if (dfs(i + 1, sum)) return true; // ○2

  /*
    もしa[i]を合計値に入れて目的の値になったならば、真を返す。
  */
  if (dfs(i + 1, sum + a[i])) return true; // ○3

  /*
    a[i]を入れようが入れまいが、もう合計値にすることは不可能であるからfalseを返す。
  */
  return false; // ○4
}

void solve() {
  if (dfs(0, 0)) printf("Yes\n");
  else printf("No\n");
}

int main(void) {
  n = 4;
  int b[MAX_N] = {1, 2, 4, 7};
  a = b;
  k = 13;

  solve(); // Yes
}

i の役割は配列の何番目の話をしているかで、 sum の役割は再帰関数がうまく働くようにするための蓄積値といったところです。

この関数は次のように動きます。( https://wandbox.org/permlink/VikAMasmuqES69RS で確認できます。以下の説明文めちゃくちゃ長いですが、実際に動きを追ったほうがわかりやすいので書いてみました。)

---

dfs(0, 0)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(1, 0)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(2, 0)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(3, 0)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(4, 0)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 0 == 13 は偽なので、 dfs(4, 0) は false を返す。

↓

○3 dfs(3, 0) の中に戻る。○2 が実行されなかったので、次に sum(=0) に a[3](=7) が足された
dfs(4, 7)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 7 == 13 は偽なので、 dfs(4, 7) は false を返す。

↓

○4 dfs(3, 0) の中に戻る。 dfs(3, 0) は false を返す。

↓

○3 dfs(2, 0) の中に戻る。○2 が実行されなかったので、次に sum(=0) に a[2](=4) が足された
dfs(3, 4)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(4, 4)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 4 == 13 は偽なので、 dfs(4, 4) は false を返す。

↓

○3 dfs(3, 4) の中に戻る。○2 が実行されなかったので、次に sum(=4) に a[3](=7) が足された
dfs(4, 11)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 11 == 13 は偽なので、 dfs(4, 11) は false を返す。

↓

○4 dfs(3, 4) の中に戻る。 dfs(3, 4) は false を返す。

↓

○4 dfs(2, 0) の中に戻る。 dfs(2, 0) は false を返す。

↓

○3 dfs(1, 0) の中に戻る。○2 が実行されなかったので、次に sum(=0) に a[1](=2) が足された
dfs(2, 2)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(3, 2)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(4, 2)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 2 == 13 は偽なので、 dfs(4, 2) は false を返す。

↓

○3 dfs(3, 2) の中に戻る。○2 が実行されなかったので、次に sum(=2) に a[3](=7) が足された
dfs(4, 9)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 9 == 13 は偽なので、 dfs(4, 9) は false を返す。

↓

○4 dfs(3, 2) の中に戻る。 dfs(3, 2) は false を返す。

↓

○3 dfs(2, 2) の中に戻る。○2 が実行されなかったので、次に sum(=2) に a[2](=4) が足された
dfs(3, 6)が呼ばれる。

↓

○1 i ≠ nであるから、まだ値は返さない。
○2 dfs(4, 6)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 6 == 13 は偽なので、 dfs(4, 6) は false を返す。

↓

○3 dfs(3, 6) の中に戻る。○2 が実行されなかったので、次に sum(=6) に a[3](=7) が足された
dfs(4, 13)が呼ばれる。

↓

○1 i = nであるから、sum == k の式の評価値を返す。 13 == 13 は真なので、 dfs(4, 13) は true を返す。

↓

○3のif文以降が実行される。 dfs(3, 6) は true を返す。

↓

○3のif文以降が実行される。 dfs(2, 2) は true を返す。

↓

○3のif文以降が実行される。 dfs(1, 0) は true を返す。

↓

○2のif文以降が実行される。 dfs(0, 0) は true を返す。

---

この説明は蟻本p34の解説絵と同じです。

★なぜ0,0なんですか？

dfs関数の再帰の仕組みを理解すれば自ずとわかるかと思います。

i = 0なのは、配列の0番目から部分和を確認する必要があるためです。これは明白だと思います。(i = 4であればi = 0, 1, 2, 3は無視される...明らかにそれは望んだ操作ではない)

sum = 0なのは、再帰関数がうまく働くようにするには最初の値を0にする必要があるからというのがわかると思います。この変数は、部分和が目的値になっているかを確認するために使われています。

遷移について等、まだよくわからない部分があれば返信ください。m(_ _)m

Comments

[reo517]

理解しました。ありがとうございます。まったく動きが分かってませんでした。。。

Answer 2

蟻本は、アマゾンの試し読みで読めました。

if (i == n) return sum == k;

// n個決め終わったら、sumがkと等しいかを返す
★sumが等しいかを返すならtrue or falseではないのですか？
★returnで何が返ってくるのかわかりません

== は、2項演算子で、
第1項と第2項が等しければ、演算結果はtrue。
第1項と第2項が等しくなければ、演算結果は false です。
sum と k が等しければ、true を返し、
sum と k が等しくなければ、false を返します。

if (dfs(0, 0)) printf("Yes\m");

★なぜ0,0なんですか？

bool dfs(int i, int sum) { と定義された関数 dfs は、
a[0]～a[i-1] の部分和が sum に入っているとき、
a[i] を加えない場合と加える場合の 2通りについて、
残りの a[i+1], ... a[n-1] の部分和を sum に加えたものが
k に等しければ true を返し、等しくなければ false を返します。

dfs(0, 0) で dfs を呼び出すと、i = 0, sum = 0 で呼び出すので、
a[0]～a[n-1] の部分和を sum に加えたものが k に等しければ true、
そうでなければ false が返ってきます。

if (dfs(i+1, sum)) return true;

a[i] を加えない場合、残りの a[i+1]～a[n-1] の部分和を sum に
加えたものが k に等しいかどうかが返ってくるので、
true が返ってきたら、探索終了で true で返ります。

if (dfs(i+1, sum + a[i])) return true;

a[i] を加えた場合、残りの a[i+1]～a[n-1] の部分和を sum に
加えたものが k に等しいかどうかが返ってくるので、
true が返ってきたら、探索終了で true で返ります。

a[i] を部分和に加えても加えなくても false だったら、
a[0]～a[i-1] の部分和が間違っていたことになるので
false で戻って、違う組み合わせの部分和に変更してもらいます。

Comments

[reo517]

2項演算子の質問はすみません。精進します。読み込んで理解します。夜中に返信ありがとうございました。