TOC generated by https://magnetikonline.github.io/markdown-toc-generate/
项目中遇到的算法
在阅读完 艾略特波浪理论 后发现，波浪理论是一个由规则组成的市场解释模型，所以就想用个代码实现对应的规则并且通过回测检验其准确性。在实现的过程中发现它也需要一些有趣的算法支撑，就趁机记录一下。
加权区间调度问题的建模
在实现了一个通过规则数浪的模块后，输入模块的是一个时间序列，输出的是所有满足波浪理论的浪的组合。每个浪都有4个元素：（开始时间，结束时间，浪的类型，置信度）。其中置信度是根据波浪理论的指南生成的复合斐波那契关系的程度。
接下来为了能生成交易信号，需要选取其中 N 个不重叠的浪，输出一个“数浪方案”，从而通过已有的浪判断下一个浪的趋势和方向。我们希望选取置信度最高的浪，同时浪之间不能有重合的部分。这时候就可以将其抽象成加权区间调度问题了。
同理，美团的酒店预定竞标算法也是可以使用的：每一个竞标是一个三元组（开始，入住时间，每天费用）。现在有N个竞标，选择使酒店效益最大的竞标。
算法内容
算法主要参考了CSDN上的一篇文章
算法的思考过程：
我们为了便于判断元素之间是否重合，先将所有元素以结束时间进行排列，那么要找到与元素 A 不重合的元素B，只要用元素 A 的开始时间在数组中用二分法搜索即可。元素B 的结束时间小于元素A的开始时间即不重合。
找到一个权值之和最大的元素组合，即需要对每一个元素判断，当前的元素是否需要被包含在最终的最优解中。我们可以把这个问题拆解成两个子问题：
- 如果当前的元素需要被包含在最优解中，那么，其最优解应当是这个元素 + 在这个元素之前并不重合的解。
- 如果当前的元素不需要被包含在最优解中，那么，其最优解与前一个元素的最优解相同。
我们将前n个元素的集合对应的最优解表示为 Solution(n)，那么我们就有：
if 元素n in Solution(n):
Solution(n) = Solution(non_overlap(n)) + 元素n
else:
Solution(n) = Solution(n-1)
non_overlap(n) 表示与元素n不重合的元素的最大索引。同时我们可以用新组合的权重是否更大来判断元素 n 是否在前 n 个元素的最优解中，于是算法就变为：
if weight_n + Solution(non_overlap(n)).weight > Solution(n-1):
Solution(n) = Solution(non_overlap(n)) + 元素n
else:
Solution(n) = Solution(n-1)
算法实现和复杂度也并不高：
- O(nlogn) 将所有待选的目标的 list 根据结束时间排序。
- 根据结束时间排序的原因是：
- 任选一个目标，我们可以通过目标的开始时间是否大于 list 中的元素快速找到其不重叠的元素。
- 如果根据开始时间排序也可以，但是就要反向遍历。
- O(n) 用动态规划创建一个 list 记录每个元素对应的最大加权调度组合以及对应的最大权重值.
- O(nlogn) 遍历每个元素并生成当前元素对应的最大加权调度组合：
- 如果可以找到在当前元素之前，并且不重叠的元素最大加权调度组合，则把当前元素加到之前的组合里，并记录下权重值。
- 如果找不到在当前元素之前，且不重叠的元素组合，则使用当前元素自己的权重值。
- 将这个权重值与之前已记录的最大权重值进行比较，如果更大，则更新进当前的权重组合中，否则使用之前的权重组合和最大权重值。
算法实现
我用 python 实现了一下：
import bisect
# Format: (object, start, end, weight)
input_wave_list = [
("1", 2, 3, 1),
("2", 3, 5, 2),
("3", 1, 4, 10),
("4", 5, 8, 10),
("5", 5, 7, 10),
("6", 7, 10, 2),
("7", 1, 10, 0),
]
input_wave_list_2 = [
("8", 3, 13, 100),
("9", 3, 11, 1),
("10", 13, 14, 1),
]
target_wave_list = ["3", "5", "6"]
class MaxWeightCombSearcher():
def __init__(self, get_start_time, get_end_time, get_weight):
self.input_wave_list = []
self.search_result_list = []
self.curr_max_result = ([], -1)
self.last_search_index = -1
self.get_start_time = get_start_time
self.get_end_time = get_end_time
self.get_weight = get_weight
def add_new_waves_list(self, new_wave_list, reset_progress=False):
self.input_wave_list += sorted(new_wave_list, key=self.get_end_time)
self.search_result_list += [None] * len(new_wave_list)
if reset_progress:
self.last_search_index = -1
self.input_wave_list = sorted(self.input_wave_list, key=self.get_end_time)
self.search_result_list = [None] * len(self.input_wave_list)
self.curr_max_result = ([], -1)
def find_max_weight_comb(self):
end_time_list = [x[2] for x in self.input_wave_list]
for i in range(self.last_search_index+1, len(self.input_wave_list)):
start_time = self.get_start_time(self.input_wave_list[i])
non_overlap_index = bisect.bisect_right(end_time_list, start_time)
if non_overlap_index == 0:
# 找不到在当前元素之self.input_wave_list前，且不重叠的元素组合，则使用当前元素自己的权重值。
new_result = ([self.input_wave_list[i]], self.get_weight(self.input_wave_list[i]))
else:
# 可以找到在当前元素之前，并且不重叠的元素最大加权调度组合，则把当前元素加到之前的组合里，并记录下权重值。
new_result = (self.search_result_list[non_overlap_index-1][0] + [self.input_wave_list[i]],
self.search_result_list[non_overlap_index-1][1] + self.get_weight(self.input_wave_list[i]))
# 将这个权重值与之前已记录的最大权重值进行比较，如果更大，则更新进当前的权重组合中，否则使用之前的权重组合和最大权重值。
print("Search progress", new_result, self.curr_max_result)
if new_result[1] > self.curr_max_result[1]:
self.curr_max_result = new_result
self.search_result_list[i] = new_result
else:
self.search_result_list[i] = self.curr_max_result
self.last_search_index = i
searcher = MaxWeightCombSearcher(get_start_time=lambda x:x[1],
get_end_time=lambda x:x[2],
get_weight=lambda x:x[3])
searcher.add_new_waves_list(input_wave_list)
searcher.find_max_weight_comb()
print(searcher.curr_max_result)
searcher.add_new_waves_list(input_wave_list_2)
searcher.find_max_weight_comb()
print(searcher.curr_max_result)
输出：
Search progress ([('1', 2, 3, 1)], 1) ([], -1)
Search progress ([('3', 1, 4, 10)], 10) ([('1', 2, 3, 1)], 1)
Search progress ([('1', 2, 3, 1), ('2', 3, 5, 2)], 3) ([('3', 1, 4, 10)], 10)
Search progress ([('3', 1, 4, 10), ('5', 5, 7, 10)], 20) ([('3', 1, 4, 10)], 10)
Search progress ([('3', 1, 4, 10), ('4', 5, 8, 10)], 20) ([('3', 1, 4, 10), ('5', 5, 7, 10)], 20)
Search progress ([('3', 1, 4, 10), ('5', 5, 7, 10), ('6', 7, 10, 2)], 22) ([('3', 1, 4, 10), ('5', 5, 7, 10)], 20)
Search progress ([('7', 1, 10, 0)], 0) ([('3', 1, 4, 10), ('5', 5, 7, 10), ('6', 7, 10, 2)], 22)
([('3', 1, 4, 10), ('5', 5, 7, 10), ('6', 7, 10, 2)], 22)
Search progress ([('1', 2, 3, 1), ('9', 3, 11, 1)], 2) ([('3', 1, 4, 10), ('5', 5, 7, 10), ('6', 7, 10, 2)], 22)
Search progress ([('1', 2, 3, 1), ('8', 3, 13, 100)], 101) ([('3', 1, 4, 10), ('5', 5, 7, 10), ('6', 7, 10, 2)], 22)
Search progress ([('1', 2, 3, 1), ('8', 3, 13, 100), ('10', 13, 14, 1)], 102) ([('1', 2, 3, 1), ('8', 3, 13, 100)], 101)
([('1', 2, 3, 1), ('8', 3, 13, 100), ('10', 13, 14, 1)], 102)
