Thuật toán để tìm kích thước phù hợp nhất

Question

Tôi đang tìm một thuật toán để tìm kết hợp thứ nguyên tốt nhất để đạt được kết quả mong muốn.

Lấy sau đây là ví dụ:

| A | B | C | y | 
|--------|--------|-------|-----| 
| dog | house1 | green | 30 | 
| dog | house1 | blue | 15 | 
| cat | house1 | green | 20 | 
| cat | house2 | red | 5 | 
| turtle | house3 | green | 50 | 

A, B, C là các kích thước đo. y là kết quả đo được.

Nếu tôi muốn nhận được tất cả sự kết hợp của kích thước đó thực hiện y> = 50 nên kết quả sẽ là:

turtle, house3, green 
turtle, any, green 
turtle, house3, any 
turtle, any, any 
any, house3, green 
any, house3, any 
any, any, green 
any, house1, green 
any, house1, any 

Có lẽ đó là một vấn đề dễ dàng nhưng tôi đã cố gắng tìm một giải pháp tối ưu về mặt O (n) và tôi không tìm thấy nó.

Answer 1

Bắt đầu với hàng đợi công việc có chứa (any, any, ..., any), 0. Các phần tử của hàng đợi này sẽ là các cặp bao gồm một sự kết hợp và một số phần tử bên trái không thể thay đổi từ any (điều này sẽ có ý nghĩa hơn trong thời gian ngắn). Cho đến khi hàng đợi công việc trống, hãy xóa một phần tử khỏi nó và tính toán tổng tương ứng. Nếu nó không đáp ứng được ngưỡng, hãy loại bỏ nó. Nếu không, hãy báo cáo đó là một trong những kết hợp được tìm kiếm. Đối với mỗi any có thể thay đổi, cho mỗi giá trị trong cột đó, hãy enqueue kết hợp bao gồm giá trị hiện tại với any được thay thế bằng giá trị đó, với chỉ mục khóa tất cả các giá trị any trước đó.

Xem xét giới hạn nhạy cảm đầu ra, điều này nằm trong một hệ số đa thức tối ưu (nói chung, có thể có nhiều kết hợp theo cấp số nhân).

Trong Python 3:

def overthreshold(data, threshold): 
    queue = [(('any',) * len(data[0][0]), 0)] 
    for combination, begin in queue: 
     if sum(row[1] for row in data 
       if all(x in {'any', y} 
         for x, y in zip(combination, row[0]))) < threshold: 
      continue 
     yield combination 
     for i in range(begin, len(combination)): 
      if combination[i] == 'any': 
       queue.extend((combination[:i] + (x,) + combination[i+1:], i + 1) 
          for x in {row[0][i] for row in data}) 


def demo(): 
    data = [ 
     (('dog', 'house1', 'green'), 30), 
     (('dog', 'house1', 'blue'), 15), 
     (('cat', 'house1', 'green'), 20), 
     (('cat', 'house2', 'red'), 5), 
     (('turtle', 'house3', 'green'), 50), 
    ] 
    for combination in overthreshold(data, 50): 
     print(combination)