使用 DFS 查找总和最大的路径花费的时间太长

Question

在每个时间点，客服人员可以：

• 如果他有足够的资金，就开仓。这按当前价格减少了资金。价格已添加到未平仓合约列表中
• 如果他有未平仓合约，则平掉一个仓位（开仓时间最远的仓位）。这会将当前价格添加到资金中，从列表中删除头寸，并通过当前价格减去开仓价来增加利润。
• 按住（不执行任何操作）。

给定一系列价格，目标是找到最佳开盘/平仓时刻以获得最大利润。

我已经实现了这个，但是代码运行时间很长（16 个观察需要 1 分钟）。有哪些改进的可能性？

另外，我想得到最优路径本身。我无法存储所有路径。回溯的算法是什么？

这是使用Python的代码：

import matplotlib.pyplot as plt
from collections import deque
import numpy as np
import time

def optimal_strategy(prices, root):
    s = deque([root])
    m = 0.0
    while s:
        n = s.pop()
        t = n['time'] + 1
        if t == len(prices):
            m = np.max([m, n['profit']])
            continue
        p = prices[t]
        s.append({'name': 'h' + str(t), 'time': t, 'parent': n['name'],
                  'funds': n['funds'], 'positions': n['positions'], 'profit': n['profit']})
        if p < n['funds']:
            s.append({'name': 'ol' + str(t), 'time': t, 'parent': n['name'],
                      'funds': n['funds'] - p, 'positions': n['positions'] + [p], 'profit': n['profit']})
        if len(n['positions']) > 0:
            s.append({'name': 'cl' + str(t), 'time': t, 'parent': n['name'],
                      'funds': n['funds'] + p, 'positions': n['positions'][1:], 'profit': n['profit'] + p - n['positions'][0]})

    return m

nobs = 16
np.random.seed(1)
prices = np.cumsum(np.random.normal(size=nobs))
plt.plot(prices)

t0 = time.time()
m = optimal_strategy(prices, {'name': 'r', 'time': -1, 'parent': None,
                              'funds': 4.0, 'positions': [], 'profit': 0.0})
print('Time {} Max {}'.format(time.time() - t0, m))

Answer 1

这里是一个示例，展示了如何获得获得最大资金的确切交易。资金最大化保证了我们利润最大化。知道顺序后就可以详细计算哪些交易赚了多少利润。

from collections import namedtuple

Trade = namedtuple("Trade", "time funds shares parent")

def optimal_strategy (prices, funds):
    root = Trade(-1, funds, 0, None)
    portfolios = [root]
    for i, price in enumerate(prices):
        # Start with the option of holding.
        next_portfolios = portfolios.copy()
        for portfolio in portfolios:
            # Can we sell?
            next_funds = portfolio.funds + price
            next_shares = portfolio.shares - 1
            if 0 <= next_shares and 0 <= next_funds:
                if next_portfolios[next_shares].funds < next_funds:
                    next_portfolios[next_shares] = Trade(
                        i, next_funds, next_shares, portfolio)
            # Can we buy?
            next_funds = portfolio.funds - price
            next_shares = portfolio.shares + 1
            if 0 <= next_funds:
                if len(next_portfolios) == next_shares:
                    next_portfolios.append(Trade(
                        i, next_funds, next_shares, portfolio))
                elif next_portfolios[next_shares].funds < next_funds:
                    next_portfolios[next_shares] = Trade(
                        i, next_funds, next_shares, portfolio)
        portfolios = next_portfolios

        # Remove portfolios that cannot lead to our answer.
        while len(prices) - i < len(portfolios):
            portfolios.pop()

    path = []
    portfolio = portfolios[0]
    parent_portfolio = portfolio.parent
    while parent_portfolio is not None:
        if parent_portfolio.shares < portfolio.shares:
            path.append((portfolio.time, 'buy'))
        else:
            path.append((portfolio.time, 'sell'))
        portfolio = parent_portfolio
        parent_portfolio = portfolio.parent
    return list(reversed(path))