简体中文 | 繁體中文 | English

二分回溯算法

一种节省步数的，效率高的回溯算法。

但是本算法依靠逻辑元，如果运行逻辑元的步数算上的话，并不节省步数。所以，如果有特殊的逻辑与-逻辑或元函数，在运算整体和的时候只需要一步，那本算法带来的优化效率是非常高的。

回溯逻辑

回溯步骤比较复杂，直接看代码可能会好一点

• 定义逻辑与-逻辑或函数单元：

  • logic_unit(self, effective_list: list) -> bool： 接收一个列表（有效数据集合）作为参数，遍历每一个元素，存在一个元素不符合定义的逻辑时就返回False,否则返回True

• 进入dichotomy_backtracking_algorithm(effective_list)方法:

  1. 调用逻辑与-逻辑或函数单元（传参：effective_list）：返回True或者False

  2. 第一次调用：如果返回值为True，则直接退出（因为所有元素均符合定义逻辑），返回值为False，则将有效列表二分为两个子列表（子列表1,子列表2），将子列表1作为参数返回步骤1

  3. 非第一次调用：如果返回值为True,那么该列表内的所有元素均符合定义逻辑，将该列表元素全部加入yes_list，这个时候回溯到它的父列表中的其他子列表中（由于二分法，一个父列表一般就两个子列表，也就是说每一个列表最多只有一个同父同级列表），如果其他子列表返回False,那么继续分割子列表，直到子列表长度小于等于lm（这一个值事实上会影响算法优化程度，因为这个值限制了子列表的最小长度，防止深度优先搜索过度深入造成浪费，也就是说当lm=有效列表长度//3-1的时候，理论上列表最多被分割4次），会把子列表元素逐个穷举，返回True，则加入yes_list，然后回溯，将它的同父同级列表作为参数返回步骤1

暂时还没有配图，所以可能不太好理解

下载和调用

pip install dichback

示例程序

from dichback import AlgorithmSet

class Al(AlgorithmSet):
    LIST = [i for i in range(1, 100) if i%10 == 0]
    def __init__(self):
        super().__init__()

    def logic_unit(self, effective_list: list) -> bool:
        # LIST = [i for i in range(1, 100) if i%2 == 0]
        # 也就是2,4,6,8,10,12...98
        # 在1,2,3,4..99这个数据样本中LIST的离散程度非常大
        # 因为在这个逻辑单元中相当于True,False,True.False...
        for i in effective_list:
            if not i in self.LIST:
                return False
        return True

if __name__ == '__main__':
    a = Al()
    rep = a.dichotomy_backtracking_algorithm([i for i in range(1, 100)])
    print(a.counts)
    print(rep)

dichback中AlgorithmSet类继承的时候强制要求定义逻辑元:

def logic_unit(self, effective_list: list) -> bool

同时提供self.counts属性，查看逻辑元调用次数

Dichback库的其他算法

这些算法都支持逻辑元，具体请查看代码注释

• 简单穷举法
• 普通二分法