teratail
回答率
85.30%
teratail header banner
teratail header banner
質問するログイン新規登録
トップに関する質問計算量を少なくするアイデア

編集履歴

質問編集履歴

2

皆さまありがとうございます。遺伝的アルゴリズムを学ぶには時間が足りないので問題を小さくして４個の組み合わせのみで考えることにしました。もともと自分で最適解を設定していたのでその答えが出たら成功ですが…

2017/12/06 08:57

投稿

Looove
Looove

スコア11

title CHANGED
File without changes
body CHANGED
@@ -35,6 +35,7 @@
35
35
  seibunlist = []
36
36
  taisekilist = []
37
37
  kekkalist = []
38
+ kekkalist4 = []
38
39
 
39
40
  for r in range(0, nrows):
40
41
  for c in range(0, ncols):
@@ -55,7 +56,7 @@
55
56
  m = int(j[1]-1)
56
57
  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:
57
58
 
58
- kekkalist.append(j)
59
+ # kekkalist.append(j)
59
60
  pass
60
61
 
61
62
  elif i == 3:
@@ -63,7 +64,7 @@
63
64
  p = int(j[1]-1)
64
65
  v = int(j[2]-1)
65
66
  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:
66
- kekkalist.append(j)
67
+ # kekkalist.append(j)
67
68
  pass
68
69
 
69
70
 
@@ -73,7 +74,7 @@
73
74
  z = int(j[2]-1)
74
75
  a = int(j[3]-1)
75
76
  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:
76
- kekkalist.append(j)
77
+ kekkalist4.append(j)
77
78
 
78
79
  else:
79
80
  q = int(j[0]-1)
@@ -84,25 +85,61 @@
84
85
  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:
85
86
  kekkalist.append(j)
86
87
 
87
- kekkalist.reverse()
88
88
 
89
+
90
+
89
91
 
90
92
 
91
93
 
92
94
  z = 0
93
95
  a = 0
96
+ b = 0
97
+ c = 0
98
+ d = 0
99
+ e = 0
100
+ f = 0
101
+ g = 0
102
+ h = 0
103
+ j = 0
104
+ l = 0
105
+ m = 0
106
+ n = 0
107
+ o = 0
108
+ p = 0
109
+ q = 0
110
+ r = 0
111
+ s = 0
112
+ t = 0
113
+ u = 0
114
+ v = 0
115
+ w = 0
116
+ x = 0
117
+ ab=0
118
+ ac=0
119
+ ad=0
120
+ ae=0
121
+ af=0
122
+ ag=0
123
+ ah=0
124
+ ai=0
125
+ aj=0
126
+ ak=0
127
+ al=0
128
+ am=0
129
+ an=0
130
+ ao=0
94
131
 
95
- for i, _ in enumerate(kekkalist,9):
132
+ for i, _ in enumerate(kekkalist4,9):
96
133
  if i == 10:
97
134
  break
98
135
 
99
- for k in itertools.combinations(kekkalist, r=i):
136
+ for k in itertools.combinations(kekkalist4, r=i):
100
- for y in range(0,i):
137
+ for y in range(0,9):
101
138
  z += len(k[y])
102
- if z == 36:
139
+ # if z == 43:
103
- print(k)
140
+ # print(k)
104
141
 
105
- if y == 0:
142
+ if y == 0:
106
143
  z = 0
107
144
  a = 0
108
145
  b = 0
@@ -139,81 +176,80 @@
139
176
  al=0
140
177
  am=0
141
178
  an=0
142
- ao=0
179
+ ao=0
143
-
144
-
180
+
145
- if k[y].count(1.0) == 1:
181
+ if k[y].count(1.0) == 1:
146
182
  a += 1
147
- if k[y].count(2.0) == 1:
183
+ if k[y].count(2.0) == 1:
148
184
  b += 1
149
- if k[y].count(3.0) == 1:
185
+ if k[y].count(3.0) == 1:
150
186
  c += 1
151
- if k[y].count(4.0) == 1:
187
+ if k[y].count(4.0) == 1:
152
188
  d += 1
153
- if k[y].count(5.0) == 1:
189
+ if k[y].count(5.0) == 1:
154
190
  e += 1
155
- if k[y].count(6.0) == 1:
191
+ if k[y].count(6.0) == 1:
156
192
  f += 1
157
- if k[y].count(7.0) == 1:
193
+ if k[y].count(7.0) == 1:
158
194
  g += 1
159
- if k[y].count(8.0) == 1:
195
+ if k[y].count(8.0) == 1:
160
196
  h += 1
161
- if k[y].count(9.0) == 1:
197
+ if k[y].count(9.0) == 1:
162
198
  j += 1
163
- if k[y].count(10.0) == 1:
199
+ if k[y].count(10.0) == 1:
164
200
  l += 1
165
- if k[y].count(11.0) == 1:
201
+ if k[y].count(11.0) == 1:
166
202
  m += 1
167
- if k[y].count(12.0) == 1:
203
+ if k[y].count(12.0) == 1:
168
204
  n += 1
169
- if k[y].count(13.0) == 1:
205
+ if k[y].count(13.0) == 1:
170
206
  o += 1
171
- if k[y].count(14.0) == 1:
207
+ if k[y].count(14.0) == 1:
172
208
  p += 1
173
- if k[y].count(15.0) == 1:
209
+ if k[y].count(15.0) == 1:
174
210
  q += 1
175
- if k[y].count(16.0) == 1:
211
+ if k[y].count(16.0) == 1:
176
212
  r += 1
177
- if k[y].count(17.0) == 1:
213
+ if k[y].count(17.0) == 1:
178
214
  s += 1
179
- if k[y].count(18.0) == 1:
215
+ if k[y].count(18.0) == 1:
180
216
  t += 1
181
- if k[y].count(19.0) == 1:
217
+ if k[y].count(19.0) == 1:
182
218
  u += 1
183
- if k[y].count(20.0) == 1:
219
+ if k[y].count(20.0) == 1:
184
220
  v += 1
185
- if k[y].count(21.0) == 1:
221
+ if k[y].count(21.0) == 1:
186
222
  w += 1
187
- if k[y].count(22.0) == 1:
223
+ if k[y].count(22.0) == 1:
188
224
  x += 1
189
- if k[y].count(23.0) == 1:
225
+ if k[y].count(23.0) == 1:
190
226
  ab += 1
191
- if k[y].count(24.0) == 1:
227
+ if k[y].count(24.0) == 1:
192
228
  ac += 1
193
- if k[y].count(25.0) == 1:
229
+ if k[y].count(25.0) == 1:
194
230
  ad+= 1
195
- if k[y].count(26.0) == 1:
231
+ if k[y].count(26.0) == 1:
196
232
  ae += 1
197
- if k[y].count(27.0) == 1:
233
+ if k[y].count(27.0) == 1:
198
234
  af += 1
199
- if k[y].count(28.0) == 1:
235
+ if k[y].count(28.0) == 1:
200
236
  ag += 1
201
- if k[y].count(29.0) == 1:
237
+ if k[y].count(29.0) == 1:
202
238
  ah += 1
203
- if k[y].count(30.0) == 1:
239
+ if k[y].count(30.0) == 1:
204
240
  ai += 1
205
- if k[y].count(31.0) == 1:
241
+ if k[y].count(31.0) == 1:
206
242
  aj += 1
207
- if k[y].count(32.0) == 1:
243
+ if k[y].count(32.0) == 1:
208
244
  ak += 1
209
- if k[y].count(33.0) == 1:
245
+ if k[y].count(33.0) == 1:
210
246
  al += 1
211
- if k[y].count(34.0) == 1:
247
+ if k[y].count(34.0) == 1:
212
248
  am += 1
213
- if k[y].count(35.0) == 1:
249
+ if k[y].count(35.0) == 1:
214
250
  an += 1
215
- if k[y].count(36.0) == 1:
251
+ if k[y].count(36.0) == 1:
216
252
  ao += 1
217
-
218
- print(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)
253
+ 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:
254
+ print (k)
219
255
  ```

1

皆さんのアドバイスを踏まえコードを書き直しました。処理に時間がかかり計算結果は出ていません。

2017/12/06 08:57

投稿

Looove
Looove

スコア11

title CHANGED
File without changes
body CHANGED
@@ -33,8 +33,9 @@
33
33
  surablist = []
34
34
  atusalist = []
35
35
  seibunlist = []
36
+ taisekilist = []
36
37
  kekkalist = []
37
- b = range(1,37)
38
+
38
39
  for r in range(0, nrows):
39
40
  for c in range(0, ncols):
40
41
  data[r,c] = sheet1.cell(r,c).value
@@ -43,6 +44,7 @@
43
44
  surablist.append(data[r,0])
44
45
  atusalist.append(data[r,2])
45
46
  seibunlist.append(data[r,3])
47
+ taisekilist.append(data[r,5])
46
48
 
47
49
  for i, _ in enumerate(surablist, 2):
48
50
  if i == 6:
@@ -51,22 +53,26 @@
51
53
  if i == 2:
52
54
  n = int(j[0]-1)
53
55
  m = int(j[1]-1)
54
- if data[n,3] == data[m,3] and data[n,2] + data[m,2] <= 2.0:
56
+ 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:
57
+
55
58
  kekkalist.append(j)
59
+ pass
56
60
 
57
61
  elif i == 3:
58
62
  o = int(j[0]-1)
59
63
  p = int(j[1]-1)
60
64
  v = int(j[2]-1)
61
- 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:
65
+ 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:
62
66
  kekkalist.append(j)
67
+ pass
63
68
 
69
+
64
70
  elif i == 4:
65
71
  g = int(j[0]-1)
66
72
  u = int(j[1]-1)
67
73
  z = int(j[2]-1)
68
74
  a = int(j[3]-1)
69
- 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:
75
+ 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:
70
76
  kekkalist.append(j)
71
77
 
72
78
  else:
@@ -75,16 +81,139 @@
75
81
  e = int(j[2]-1)
76
82
  f = int(j[3]-1)
77
83
  h = int(j[4]-1)
78
- 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:
84
+ 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:
79
85
  kekkalist.append(j)
80
86
 
81
- for i, _ in enumerate(kekkalist,8):
82
- if i == 19:
83
- break
84
- for k in itertools.combinations(kekkalist, r=i):
85
- if k[1][0] == k[2][0]:
87
+ kekkalist.reverse()
86
- pass
87
- else:
88
- print(k)
89
88
 
89
+
90
+
91
+
92
+ z = 0
93
+ a = 0
94
+
95
+ for i, _ in enumerate(kekkalist,9):
96
+ if i == 10:
97
+ break
98
+
99
+ for k in itertools.combinations(kekkalist, r=i):
100
+ for y in range(0,i):
101
+ z += len(k[y])
102
+ if z == 36:
103
+ print(k)
104
+
105
+ if y == 0:
106
+ z = 0
107
+ a = 0
108
+ b = 0
109
+ c = 0
110
+ d = 0
111
+ e = 0
112
+ f = 0
113
+ g = 0
114
+ h = 0
115
+ j = 0
116
+ l = 0
117
+ m = 0
118
+ n = 0
119
+ o = 0
120
+ p = 0
121
+ q = 0
122
+ r = 0
123
+ s = 0
124
+ t = 0
125
+ u = 0
126
+ v = 0
127
+ w = 0
128
+ x = 0
129
+ ab=0
130
+ ac=0
131
+ ad=0
132
+ ae=0
133
+ af=0
134
+ ag=0
135
+ ah=0
136
+ ai=0
137
+ aj=0
138
+ ak=0
139
+ al=0
140
+ am=0
141
+ an=0
142
+ ao=0
143
+
144
+
145
+ if k[y].count(1.0) == 1:
146
+ a += 1
147
+ if k[y].count(2.0) == 1:
148
+ b += 1
149
+ if k[y].count(3.0) == 1:
150
+ c += 1
151
+ if k[y].count(4.0) == 1:
152
+ d += 1
153
+ if k[y].count(5.0) == 1:
154
+ e += 1
155
+ if k[y].count(6.0) == 1:
156
+ f += 1
157
+ if k[y].count(7.0) == 1:
158
+ g += 1
159
+ if k[y].count(8.0) == 1:
160
+ h += 1
161
+ if k[y].count(9.0) == 1:
162
+ j += 1
163
+ if k[y].count(10.0) == 1:
164
+ l += 1
165
+ if k[y].count(11.0) == 1:
166
+ m += 1
167
+ if k[y].count(12.0) == 1:
168
+ n += 1
169
+ if k[y].count(13.0) == 1:
170
+ o += 1
171
+ if k[y].count(14.0) == 1:
172
+ p += 1
173
+ if k[y].count(15.0) == 1:
174
+ q += 1
175
+ if k[y].count(16.0) == 1:
176
+ r += 1
177
+ if k[y].count(17.0) == 1:
178
+ s += 1
179
+ if k[y].count(18.0) == 1:
180
+ t += 1
181
+ if k[y].count(19.0) == 1:
182
+ u += 1
183
+ if k[y].count(20.0) == 1:
184
+ v += 1
185
+ if k[y].count(21.0) == 1:
186
+ w += 1
187
+ if k[y].count(22.0) == 1:
188
+ x += 1
189
+ if k[y].count(23.0) == 1:
190
+ ab += 1
191
+ if k[y].count(24.0) == 1:
192
+ ac += 1
193
+ if k[y].count(25.0) == 1:
194
+ ad+= 1
195
+ if k[y].count(26.0) == 1:
196
+ ae += 1
197
+ if k[y].count(27.0) == 1:
198
+ af += 1
199
+ if k[y].count(28.0) == 1:
200
+ ag += 1
201
+ if k[y].count(29.0) == 1:
202
+ ah += 1
203
+ if k[y].count(30.0) == 1:
204
+ ai += 1
205
+ if k[y].count(31.0) == 1:
206
+ aj += 1
207
+ if k[y].count(32.0) == 1:
208
+ ak += 1
209
+ if k[y].count(33.0) == 1:
210
+ al += 1
211
+ if k[y].count(34.0) == 1:
212
+ am += 1
213
+ if k[y].count(35.0) == 1:
214
+ an += 1
215
+ if k[y].count(36.0) == 1:
216
+ ao += 1
217
+
218
+ print(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)
90
219
  ```