計算量を少なくするアイデア

Question

###前提・実現したいこと

処理速度を早くする方法を知りたいです。

36個の形が違う石を箱に詰めていきます。それぞれ１〜３６の番号をつけます。
箱の大きさは一辺２mの立方体です。
まず、石２〜５個の組み合わせを考え、ある条件を満たしている組み合わせのみ配列に格納します。これがおおよそ800通り程あります。
その後、この800の組み合わせからさらに、５〜１９個の組み合わせを考えます。この時１〜３６の数字が必ず一つずつ入るような組み合わせを求めたいです。

###発生している問題・エラーメッセージ

計算量が膨大すぎて結果を出すのにあまりにも時間がかかる。

if k[1][0] == k[2][0]:この記述だと不完全なのはわかっていますが、どうかけばいいのかアイデアをいただきたいです。

###該当のソースコード

import xlrd
import os.path
import numpy as np
import itertools
import sys
import openpyxl

xlfile = "結果.xlsx"
if os.path.exists(xlfile):
    xls = xlrd.open_workbook(xlfile)
    sheet1 = xls.sheet_by_index(0)
    nrows = sheet1.nrows
    ncols = sheet1.ncols 
    data = np.zeros(ncols*nrows).reshape((nrows, ncols))
    surablist = []
    atusalist = []
    seibunlist = []
    taisekilist = []
    kekkalist = []
    kekkalist4 = []

    for r in range(0, nrows):
        for c in range(0, ncols):
            data[r,c] = sheet1.cell(r,c).value

    for r in range(0, nrows):
        surablist.append(data[r,0])
        atusalist.append(data[r,2])
        seibunlist.append(data[r,3])
        taisekilist.append(data[r,5])

    for i, _ in enumerate(surablist, 2):
        if i == 6:
         break
        for j in itertools.combinations(surablist, r=i):
              if i == 2:
               n = int(j[0]-1)
               m = int(j[1]-1)
               if data[n,3] == data[m,3] and data[n,2] + data[m,2] <= 2.0 and data[n,5] + data[m,5] <=2.56:

 #               kekkalist.append(j)
                pass

              elif i == 3:
               o = int(j[0]-1)
               p = int(j[1]-1)
               v = int(j[2]-1)
               if data[o,3] == data[p,3] and data[o,3] == data[v,3] and data[p,3] == data[v,3] and data[o,2] + data[p,2] + data[v,2] <= 2.0 and data[o,5] + data[p,5] + data[v,5] <= 2.56:
 #               kekkalist.append(j)
                 pass


              elif i == 4:
               g = int(j[0]-1)
               u = int(j[1]-1)
               z = int(j[2]-1)
               a = int(j[3]-1)
               if data[g,3] == data[u,3] and data[g,3] == data[a,3] and data[g,3] == data[z,3] and data[u,3] == data[z,3] and data[a,3] == data[u,3] and data[z,3] == data[a,3] and data[g,2] + data[u,2] + data[z,2] + data[a,2] <= 2.0 and data[g,5] + data[u,5] + data[z,5] + data[a,5] <= 2.56:
                kekkalist4.append(j)
                
              else:
               q = int(j[0]-1)
               w = int(j[1]-1)
               e = int(j[2]-1)
               f = int(j[3]-1)
               h = int(j[4]-1)
               if data[q,3] == data[w,3] and data[q,3] == data[f,3] and data[q,3] == data[e,3] and data[q,3] == data[h,3] and data[w,3] == data[e,3] and data[f,3] == data[w,3] and data[h,3] == data[w,3] and data[e,3] == data[f,3] and data[e,3] == data[h,3] and data[f,3] == data[h,3] and data[q,2] + data[w,2] + data[e,2] + data[f,2] + data[h,2] <= 2.0 and data[q,5] + data[w,5] + data[e,5] + data[f,5] + data[h,5] <= 2.56:
                 kekkalist.append(j)




       


z = 0
a = 0
b = 0
c = 0
d = 0
e = 0
f = 0
g = 0
h = 0
j = 0
l = 0
m = 0
n = 0
o = 0
p = 0
q = 0
r = 0
s = 0
t = 0
u = 0
v = 0
w = 0
x = 0
ab=0
ac=0
ad=0
ae=0
af=0
ag=0
ah=0
ai=0
aj=0
ak=0
al=0
am=0
an=0
ao=0

for i, _ in enumerate(kekkalist4,9):
          if i == 10:
           break
          
          for k in itertools.combinations(kekkalist4, r=i):
             for y in range(0,9):
                 z += len(k[y])
 #               if z == 43:
 #                print(k)
                     
                 if y == 0:
                   z = 0
                   a = 0
                   b = 0
                   c = 0
                   d = 0
                   e = 0
                   f = 0
                   g = 0
                   h = 0
                   j = 0
                   l = 0
                   m = 0
                   n = 0
                   o = 0
                   p = 0
                   q = 0
                   r = 0
                   s = 0
                   t = 0
                   u = 0
                   v = 0
                   w = 0
                   x = 0
                   ab=0
                   ac=0
                   ad=0
                   ae=0
                   af=0
                   ag=0
                   ah=0
                   ai=0
                   aj=0
                   ak=0
                   al=0
                   am=0
                   an=0
                   ao=0 
                    
                 if k[y].count(1.0) == 1:
                        a += 1
                 if k[y].count(2.0) == 1:
                        b += 1
                 if k[y].count(3.0) == 1:
                        c += 1
                 if k[y].count(4.0) == 1:
                        d += 1
                 if k[y].count(5.0) == 1:
                        e += 1
                 if k[y].count(6.0) == 1:
                        f += 1
                 if k[y].count(7.0) == 1:
                        g += 1
                 if k[y].count(8.0) == 1:
                        h += 1
                 if k[y].count(9.0) == 1:
                        j += 1
                 if k[y].count(10.0) == 1:
                        l += 1
                 if k[y].count(11.0) == 1:
                        m += 1
                 if k[y].count(12.0) == 1:
                        n += 1
                 if k[y].count(13.0) == 1:
                        o += 1
                 if k[y].count(14.0) == 1:
                        p += 1
                 if k[y].count(15.0) == 1:
                        q += 1
                 if k[y].count(16.0) == 1:
                        r += 1
                 if k[y].count(17.0) == 1:
                        s += 1
                 if k[y].count(18.0) == 1:
                        t += 1
                 if k[y].count(19.0) == 1:
                        u += 1
                 if k[y].count(20.0) == 1:
                        v += 1
                 if k[y].count(21.0) == 1:
                        w += 1
                 if k[y].count(22.0) == 1:
                        x += 1
                 if k[y].count(23.0) == 1:
                        ab += 1
                 if k[y].count(24.0) == 1:
                        ac += 1
                 if k[y].count(25.0) == 1:
                        ad+= 1
                 if k[y].count(26.0) == 1:
                        ae += 1
                 if k[y].count(27.0) == 1:
                        af += 1
                 if k[y].count(28.0) == 1:
                        ag += 1
                 if k[y].count(29.0) == 1:
                        ah += 1
                 if k[y].count(30.0) == 1:
                        ai += 1
                 if k[y].count(31.0) == 1:
                        aj += 1
                 if k[y].count(32.0) == 1:
                        ak += 1
                 if k[y].count(33.0) == 1:
                        al += 1
                 if k[y].count(34.0) == 1:
                        am += 1
                 if k[y].count(35.0) == 1:
                        an += 1
                 if k[y].count(36.0) == 1:
                        ao += 1
                        if all([a,b,c,d,e,f,g,h,j,l,m,n,o,p,q,r,s,t,u,v,w,x,ab,ac,ad,ae,af,ag,ah,ai,aj,ak,al,am,an,ao]) == True:
                            print (k)

Comments

[ozwk]

「重量がW[i]である石N個を容量Mの箱に収めるとき箱数が最小となる収め方を全て求めよ」って感じですかね

[Looove]

そうです！まさにそのような感じです。

[ozwk]

で、もっと条件が厳しくて、石は直方体で、箱は容積が決まっていて、さらに化学成分的に安定するように入れる必要があると

[Looove]

はいその通りです。

[ozwk]

でもコード見ると石のパラメータは厚さとsurab(?)と成分の3つしかないようですが。直方体+化学成分なら4つあるはずですよね?

[Looove]

石の設定としては厚さ、長さ、化学成分、幅がありますが、幅と長さは全て条件を満たしているので省いています。またsurabは1~36の番号を示しています。

Answer 1

36個の形が違う石を箱に詰めていきます
処理速度を早くする方法を知りたいです

1. 要件を整理する
2. 速い言語で書く
3. 速いアルゴリズムで書く

まず、要件定義を詰めるだけで、結果的に速くなる場合があります。
「化学成分」という、重要そうなキーワードが質問文にないあたり、
質問者の方の中でも、整理しきれていないように感じます。

要件しだいで速くなるというのは、たとえば、要件が許容する範囲で、
整数化したり、グリッド化（マス目に当てはめ）したり、近似化することです。

次に、実行速度が速い言語で書くだけで、何十倍も速くなる場合があります。
C/C++、C#、Javaとかです。PythonやRubyなどの動的言語は遅い。

そして、速いアルゴリズムで書くことも大事です。
今回は**「ナップサック問題」っぽいので、「動的計画法（DP）」**などが向いています。

---

また、分かりやすさにも言及したいと思います。
質問文のサンプルコードが、非常に読みにくいです。
たとえば、横に長いIF文、縦に長いIF文（の列）とか……。

もしかしたら、多少速い書き方で、わざとそう書いたのかもしれません。
しかし、遅い言語で分かりにくく書くよりも、
速い言語で分かりやすく書いた方が、はるかに早くて楽です。

多少のオーバーヘッドは無視して、
まず分かりやすく書いて、次に速く書き直す方が、
開発速度も含めて総合的には、良い結果が出ることが多いです。

---

この問題、要件によっては、私なら**「遺伝的アルゴリズム（GA）」**で書くかも。
パフォーマンスだけ見れば、動的計画法に負けることもよくあるんですが、
とにかく分かりやすいから、複雑な問題になるほど、GAの方を選びます。

具体的にどう書くか、概要を言いますと、GA部分と評価部分を分けます。
評価部分はたとえば、GUIがない自動操作の「三次元テトリス」のイメージです。
上からガッチョンガッチョン石を落として、埋まったら密度とかでスコアを評価。

GAの方は、たとえば石の選び方を遺伝子に持ちます。
（配列）変数が36個あり、箱の番号が書いてあるとか。
そうして、評価AIの効率化と、GAの効率化を別々に進めます。

GAはDPより冗長になるかもしれませんが、実装しやすいし、
変更時に何を変更するか分かりやすいので、変更しやすいです。

たとえば、化学成分の相性を判定する場合でも、
GAモジュールの方は独立してるので、変更がないわけです。

それに、判定部分にDPを使うとか、併用することも可能です。
あるいは、評価部分にもGAを使うとか、多重で使うことも可能です。

実際の実用で使うプログラムなら、たとえば変な積み方をすると、
石の重さで割れるから、構造力学的に形状と重量も考慮するとか、
サンプルよりはるかに複雑になるし、仕様変更も生じます。

「化学成分」みたいな、隠れた仕様がまだ出てきそうなので、
複雑になるようなら、GAも選択肢としてアリだと思います。

Answer 2

石２〜５個の組み合わせを考え、ある条件を満たしている組み合わせのみ配列に格納します。

ある条件とは「全てが同一成分で厚さの合計が2[m]以下」でよいでしょうか？
であれば、同一成分でグループ化し、各グループ毎に２～５個の組み合わせを列挙したほうがよいです。
さらに各成分毎のグループ内の要素を厚さ順にソートしておけば、厚さ順に組合せ列挙走査する過程で2[m]を超えたら足切りできるので、全組合せを列挙する必要もなくなります。

その後、この800の組み合わせからさらに、５〜１９個の組み合わせを考えます。

この部分に該当するソースがよく理解できなかったのですが、まずは石を足した合計が36個かの判定を加えることで走査数は減ると思われます。

Answer 3

アルゴリズム的にはナップサック問題でよく用いられる動的計画法を使うのがよいかと思います。

計算時間を短縮したいのであれば、C言語で書き直すとそれだけで10分の1程度の実行時間になります。
この問題、あまりpythonは得意ではありません。

---

他にも

g = int(j[0]-1)
u = int(j[1]-1)

のようなものを予めキャストしておくなどが考えられます。

Answer 4

問題を小さくして考えて、それを一般化した方がよいかと思います。
一辺２mの立方体の中に石は全部収まるのでしょうか。
何をされたいのかがいまいちイメージできませんでした。

もし石が立方体からあふれるのであれば、ナップザック問題のような考え方をされるとよいのではないかと思います。

Comments

[Looove]

言葉が足らず申し訳ありません。一辺２mの立方体はたくさんあります。ですができるだけ少ない箱数で３６個の石を全て収めたいということです。

[退会済みユーザー]

実際の石の形まで考慮した計算をされようとしていますか？
それとも立方体のパターンで近似されますか？パターンの数は限定されますか？
このあたりの考慮によって計算のやりやすさは変わってきます。
最初の答えが yes の場合は計算は大変かと思います。
次の答えがどちらも yes であれば、解くのはそれほど難しくはないかもしれません。

[Looove]

石の長さ、厚さ、幅、化学成分を考慮した計算をしようとしています。立方体のパターンで近似されません。

[退会済みユーザー]

聞いた感じですと、3Dモデルを作って物理演算をシミュレーションしてみるというのが案外手軽そうに思います。