布尔型DataFrame最优逻辑组合（&/|）求解高效算法问询

问题背景 #

现有布尔型DataFrame，含数千列、数万行（后续将扩容）。每列对应不同时间戳的信号，通过get_reward函数计算单列/组合列的奖励值（0-1000）。需用&（与）、|（或）结合括号指定运算顺序，找到奖励最高的列组合。核心难点：

• 搜索空间极大，贪心仅探索高奖励列易漏过最优解
• 需高效遍历+自定义早停
• 需处理逻辑运算的优先级问题

可行算法方案 #

1. 后缀表达式（逆波兰表达式）处理优先级 #

逻辑表达式的优先级可通过后缀表达式消除括号影响，结合排列/组合生成所有合法运算序列：

• 步骤：
  • 先限定组合列数（比如2-5列，列数过多时&会大幅降低True占比，|奖励提升有限）
  • 生成指定列数的所有列组合
  • 对每个列组合，生成所有可能的运算符序列（长度为列数-1，元素为&/|）
  • 用递归生成所有合法后缀表达式（对应卡特兰数的合法括号结构）
  • 计算每个表达式的奖励，跟踪最大值，支持早停

2. 分治+剪枝策略 #

拆分列集合为小子集，先找子集最优组合，再二次组合子集结果：

• 剪枝规则：
  • 若子集最优奖励远低于当前全局最大值，跳过该子集后续组合
  • 预过滤低奖励列（比如奖励为0的列），缩小搜索空间

3. 启发式搜索（贪心+随机局部搜索） #

先通过贪心筛选高奖励列，再在该子集内随机组合+局部调整（替换列/修改运算符），平衡效率与最优解概率。

代码实现示例 #

后缀表达式核心实现 #

import numpy as np
import pandas as pd
from itertools import product, combinations

# 生成示例数据
column_amount = 6
row_amount = 10
df = pd.DataFrame([np.random.choice([True, False], column_amount) for _ in range(row_amount)])

def get_reward(column):
    # 替换为实际奖励计算逻辑
    return column.sum() * 100

def evaluate_postfix(expr, df):
    # 计算后缀表达式对应的组合列
    stack = []
    for elem in expr:
        if isinstance(elem, int):
            stack.append(df[elem])
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(a & b if elem == '&' else a | b)
    return stack[0]

def generate_valid_expressions(columns, ops):
    # 递归生成所有合法后缀表达式
    if len(columns) == 1:
        yield [columns[0]]
    else:
        for i in range(1, len(columns)):
            left_cols, right_cols = columns[:i], columns[i:]
            left_ops, right_ops = ops[:i-1], ops[i-1:]
            for left_expr in generate_valid_expressions(left_cols, left_ops):
                for right_expr in generate_valid_expressions(right_cols, right_ops):
                    yield left_expr + right_expr + [ops[i-1]]

max_reward = -1
best_expr = None

# 限制组合列数为2-3，可按需调整
for k in range(2, 4):
    for cols in combinations(df.columns, k):
        for ops in product(['&', '|'], repeat=k-1):
            for expr in generate_valid_expressions(list(cols), list(ops)):
                combined_col = evaluate_postfix(expr, df)
                current_reward = get_reward(combined_col)
                
                # 早停：达到奖励上限直接终止
                if current_reward == 1000:
                    max_reward = current_reward
                    best_expr = expr
                    print(f"找到最优组合，奖励：{max_reward}，后缀表达式：{expr}")
                    exit()
                if current_reward > max_reward:
                    max_reward = current_reward
                    best_expr = expr

print(f"最优奖励：{max_reward}，最优组合后缀表达式：{best_expr}")

优化建议 #

• 缓存奖励结果：用字典缓存已计算过的组合列奖励，避免重复计算
• 列预筛选：提前移除奖励为0或极低的列，减少搜索基数
• 动态调整列数：先从2列开始搜索，若找到的奖励接近上限，可停止更高列数的搜索

内容的提问来源于stack exchange，提问作者Jakko