数値を組み合わせてある値に近づけるアルゴリズムについて

Question

「Pythonではじめるアルゴリズム入門」という本の幅優先探索や深さ優先探索について書かれている章の
理解度チェック問題として以下のような問題と解答が掲載されていました。
しかし、解答コードに誤りがあるように思えるので自分でコードを書いたのですが正しいでしょうか？

問題:
都道府県の人口を組み合わせて1千万人に近い組み合わせとその人口を求めよ。

本に載っている解答:

# 近づける値
goal = 10000000

# 各都道府県の人口
pref = [
    5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039,
    2916976, 1974255, 1973115, 7266534, 6222666, 13515271, 9126214,
    2304264, 1066328, 1154008, 786740, 834930, 2098804, 2031903,
    3700305, 7483128, 1815865, 1412916, 2610353, 8839469, 5534800,
    1364316, 963579, 573441, 694352, 1921525, 2843990, 1404729,
    755733, 976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566
]

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):
        return
    if total < goal:
        if abs(goal - (total + pref[pos])) < abs(goal - min_total):
            min_total = total + pref[pos]
            search(total + pref[pos], pos + 1)
        search(total, pos + 1)

search(0, 0)
print(min_total) #10001495

このコードだと答えは10001495となるのですが、

if abs(goal - (total + pref[pos])) < abs(goal - min_total):

で探索されるべきところが間違って枝刈りされているように見えます。

例えば

goal = 10
pref = [3,4,5,1,1,5]

だと、答えは10のはずが、12と明らかに間違った答が出るのですが
[3,4,5]でmin_totalが一度12になったらその後は[1]単体などは
if abs(goal - (total + pref[pos])) < abs(goal - min_total)
ではじかれて探索されなくなっているように見えます。

そこで次の様に書きました。

# 近づける値
goal = 10000000

# 各都道府県の人口
pref = [
    5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039,
    2916976, 1974255, 1973115, 7266534, 6222666, 13515271, 9126214,
    2304264, 1066328, 1154008, 786740, 834930, 2098804, 2031903,
    3700305, 7483128, 1815865, 1412916, 2610353, 8839469, 5534800,
    1364316, 963579, 573441, 694352, 1921525, 2843990, 1404729,
    755733, 976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566
]

total_temp = float('inf')

#total:合計 pos:探索ポジション l:探索ルートを入れるリスト pre:1つ前のtotal
def search(total, pos, l, pre):
    global total_temp

    if total >= goal or pos >= len(pref):
      a = abs(total - goal)
      b = abs(pre - goal)
      
      #preの方がgoalに近い場合
      if a > b:
        if b < abs(goal - total_temp):
          total_temp = pre
          print(total_temp,l[:-1] )
      #totalの方がgoalに近い場合
      else:
        if a < abs(goal - total_temp):
          total_temp = total
          print(total_temp, l)
      return

    #total < goal
    else:   
        l1 = l.copy()
        l1.append(pref[pos])
        search(total + pref[pos], pos + 1, l1, total)
        search(total, pos + 1, l, total)

search(0, 0, [], 0)
print(total_temp)

これだと答えがぴったり
10000000
で組み合わせが
[1308265, 2333899, 786740, 2031903, 573441, 755733, 832832, 1377187]
と出たのですが、このコードで合っているでしょうか？
またもっと効率の良いアルゴリズムなどはあるでしょうか？

Comments

[quickquip]

どういったアルゴリズムの説明として出てきていますか?
双方のプログラムの時間（試行回数）の比較はしていますか?
(コードの詳細を読む前に知っておきたいだろう情報として追記するとよいかと思います)

[pyxis]

幅優先探索や深さ優先探索について書かれた章末の理解度チェックとして出題されていました。

[quickquip]

この欄に書くのではなくて質問を編集しましょう。

[pyxis]

質問の方を編集しました。

[hayataka2049]

ぶっちゃけ出たばかりの新刊なので間違っていても不思議はありません。初版でどこも間違っていない本の方が珍しいくらい。
問い合わせてみると良いのでは？
https://www.shoeisha.co.jp/book/detail/9784798163239

Answer 1

直接の回答ではありませんが

このコードで合っているでしょうか？

厳密解と比較してみるとよいかと思います。
以下は厳密解を求めるコード例です。枝刈などはしていないのでとても遅いですが。

import itertools
import random

# 厳密解を求める
def search(goal, pref):
    min_total,min_combi = 0, []

    # 全組合せを列挙
    for bit in itertools.product([0,1], repeat=len(pref)):
        combi = [p for b,p in zip(bit, pref) if b == 1]
        total = sum(combi)

        # 完全一致
        if total == goal:
            return combi

        # 最近値を記録
        if abs(goal-total) < abs(goal-min_total):
            min_total, min_combi = total, combi

    return min_combi


# ランダムテスト
random.seed(110)
for i in range(5):

    # ランダムにデータ生成
    N = random.randint(2, 20) # 最大20個程度が限度
    pref = [random.randint(10, 100) for _ in range(N)]
    goal = int(sum(pref) * random.random())

    min_combi = search(goal, pref)

    print('-----')
    print( 'goal={}, pref={}'.format(goal, pref))
    print( 'min_total={}, min_combi={}'.format( sum(min_combi), min_combi))

"""
-----
goal=101, pref=[86, 41, 62, 71, 45, 91, 79, 98, 19, 79, 63, 74, 50, 15]
min_total=101, min_combi=[41, 45, 15]
-----
goal=791, pref=[20, 29, 66, 90, 11, 77, 64, 85, 94, 39, 45, 46, 56, 56, 74, 23, 62, 81]
min_total=791, min_combi=[90, 77, 64, 85, 94, 45, 46, 56, 56, 74, 23, 81]
-----
goal=130, pref=[45, 97, 26, 34, 43, 62, 70, 39, 32, 67, 38, 20, 73, 52, 52, 41]
min_total=130, min_combi=[43, 67, 20]
-----
goal=186, pref=[35, 44, 32, 10, 86, 44]
min_total=184, min_combi=[44, 10, 86, 44]
-----
goal=26, pref=[69, 61]
min_total=0, min_combi=[]
"""

Comments

[pyxis]

確かに答えが正しいかどうかは全探索した答えと比較するのが確実ですね。

Answer 2

この問題に関しては半分全列挙が効率よさそうです。
ただしこの類の問題は、パラメーターの値やサイズによって効率のいいアルゴリズムが変わってくるので、今の段階でここを掘り下げてもあまり得るものはないと思います。

# 近づける値
goal = 10000000

# 各都道府県の人口
pref = [
    5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039,
    2916976, 1974255, 1973115, 7266534, 6222666, 13515271, 9126214,
    2304264, 1066328, 1154008, 786740, 834930, 2098804, 2031903,
    3700305, 7483128, 1815865, 1412916, 2610353, 8839469, 5534800,
    1364316, 963579, 573441, 694352, 1921525, 2843990, 1404729,
    755733, 976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566
]

#二分探索でvalue以上の要素のインデックスを求める。
def lowerBound(vec, value):
    left = 0
    right = len(vec)
    while left < right:
        mid = (left + right) // 2
        if vec[mid][0] < value:
            left = mid + 1
        else:
            right = mid
    return right
    
def restoreSet(vec, bit):
    result = []
    for i in range(len(vec)):
        if (1 << i) & bit != 0:
            result.append(vec[i])
    return result

#prefの前半の組み合わせのうち明らかに最適な組み合わせに含まれないものを除いたもの
#[(合計、組み合わせのビット表現)]
first = [(0, 0)]
for i in range(len(pref)//2):
    for j in range(len(first)):
        if first[j][0] < goal:
            first.append((first[j][0] + pref[i], first[j][1] | (1 << i)))

#prefの後半の組み合わせのうち明らかに最適な組み合わせに含まれないものを除いたもの
#[(合計、組み合わせのビット表現)]
second = [(0, 0)]
for i in range(len(pref)//2, len(pref)):
    for j in range(len(second)):
        if second[j][0] < goal:
            second.append((second[j][0] + pref[i], second[j][1] | (1 << i)))

second.sort()
min_total = 0
min_set = 0
for f in range(len(first)):
    i = first[f][0]
    #first[f][0] + second[s][0] >= goalとなる最小のs。
    s = lowerBound(second, goal - i)
    #first[f][0]と組み合わせてgoalに最も近くなる可能性があるのはsecond[s][0]かsecond[s - 1][0]のみ
    if len(second) > s and abs(goal - min_total) > abs(goal - i - second[s][0]):
        min_total = i + second[s][0]
        min_set = first[f][1] | second[s][1]
    if s > 0 and abs(goal - min_total) > abs(goal - i - second[s - 1][0]):
        min_total = i + second[s - 1][0]
        min_set = first[f][1] | second[s - 1][1]

set = restoreSet(pref, min_set)
print(sum(set))
print(set)

Comments

[pyxis]

このコードだとかなり速く答えが出て驚きました。
半分全列挙というのは初めて知りました。
ソートなどもそうですが、単純そうに見える問題も奥が深く色々なアルゴリズムがあり難しいですね。

Answer 3

まず本の解答の間違いですが、最初の再帰呼び出しのインデントが間違っています。

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):
        return
    if total < goal:
        if abs(goal - (total + pref[pos])) < abs(goal - min_total):
            min_total = total + pref[pos]
        search(total + pref[pos], pos + 1) # <- ここ
        search(total, pos + 1)

この解答と、あなたの解答とは、ざっと見たところ本質的に同じようです。なので正しいはずです。

もっと効率の良いアルゴリズムがあるかどうかは、知りません。

Comments

[pyxis]

確かにインデントをずらすと正しい答えを出しますね。
ずらして修正した模範解答のコードの方が自分が書いたコードよりスマートです。

Answer 4

模範解答の
search(total + pref[pos], pos + 1)
のインデントを1減らせばよいかと。

新しく書かれた方は挙動はさておきcopyとappendに無駄があるのであまりよろしくないかと思います。

Comments

[退会済みユーザー]

組み合わせ情報も欲しければ現在の組み合わせと暫定最適の組み合わせを0,1で表現した値をglobalでもたせ、再帰呼び出しの前後で値を修正すればよいかと思います。

[pyxis]

たしかにグローバル変数を利用すれば余計なcopyを繰り返さなくて済みますね。

Answer 5

質問内に書いた自分のコードは
a = abs(total - goal)
b = abs(pre - goal)
を比較しているのですが、その比較は必要なく以下のように書けば十分であると気付きました。
また、同値であった場合の組み合わせも出力するようにしました。

# 近づける値
goal = 10000000

# 各都道府県の人口
pref = [
    5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039,
    2916976, 1974255, 1973115, 7266534, 6222666, 13515271, 9126214,
    2304264, 1066328, 1154008, 786740, 834930, 2098804, 2031903,
    3700305, 7483128, 1815865, 1412916, 2610353, 8839469, 5534800,
    1364316, 963579, 573441, 694352, 1921525, 2843990, 1404729,
    755733, 976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566
]

temp = float('inf')
ary = []

def search(total, pos):
    global ary, temp

    # total >= goal にならなかった組み合わせも必ず最後はpos == len(pref)となりここの分岐に入る
    if pos == len(pref) or total >= goal:
        # <=にすることで同値であっても表示
        if abs(goal - total) <= abs(goal - temp):
          print(total, ary)
          temp = total

        return

    else:
        ary.append(pref[pos])
        search(total + pref[pos], pos + 1)
        del ary[-1]
        search(total, pos + 1)

search(0, 0)