java - 构建无限期的 MDP，使用必访状态实现成本最小化

Question

寻求一些帮助来解决无限期问题、成本最小化问题以及一些必须访问的状态。

我们有一个预算 b 和一个成本矩阵 M，它表示状态之间旅行的扣除额(Mij 表示从 i 到 j 的旅行成本)，类似于经典的旅行商问题。在这种情况下，时间可能是负数，表示预算增加，Mij 不一定等于 Mji。同样在这种情况下，M 是 4x4，但情况可能并非如此，通常可以说 3 <= len(M) <= 5，因为我认为这可能需要一些带有大量操作的蛮力方法......

0 1 -3 1
6 0 2 2
4 2 0 3
1 2 3 0

每一行代表给定状态 i，然后每一列代表前往 j 的成本。

因此问题是:给定 b 和 M，不包括 state=0 和 state=len(M) 我们可以到达并最终到达 state=len(M) 且 b >= 的唯一状态的最大数量是多少0.

鉴于上面的 M，并且 b=0，那么我认为输出将是 [2]，路径是 [0] -> [2] -> [3]，完整的展示如下所示:

state nextstate deduction time
 --       0        ---     0
 0        2         -3     3
 2        3         3      0

我试图将这个问题作为一个强化学习问题来解决，使用 e-greedy 解决方案和启发式策略来选择下一个状态，我也将其视为 TSP 并查看了使用 Floyd-Warshall 的解决方案，但是我不太确定如何在问题设置中适应约束。

我认为有一种方法可以找到直接的解决方案，我的直觉似乎能够查看一般的 M 和给定的 b 并提出解决方案，但我无法清楚地表述算法...

对于如何清晰地构建这个框架并提出直接解决方案，我们表示赞赏。

Answer 1

如果您的成本矩阵包含负循环，那么最终可以访问所有状态。您可以使用 Bellman-Ford检测循环，因此答案的其余部分假定不存在这样的循环。

该算法由三部分组成。首先，它找到从开始状态到结束状态成本低于预算的所有路径。对于每条这样的路径，都会跟踪所访问的状态和总成本。然后它会找到所有源自(并终止于)结束状态的循环，并跟踪已访问状态和总成本。

在已知所有路径和循环之后，算法开始向路径添加循环。如果该循环添加新状态并且总成本在预算范围内，则添加成功。添加一直持续到无法向现有路径添加循环为止。最后，包含最多访问状态的路径被选为结果。

以下是上述内容的非精化实现:

M = [
    [0, 2, 2, 2, -1],
    [6, 0, 2, 2, -1],
    [6, 3, 0, 2, -1],
    [6, 3, 2, 0, -1],
    [6, 3, 2, 2, 0]
]

BUDGET = 1
SOURCE = 0
DEST = len(M) - 1

def all_paths_step(source, dest, visited, cost):
    for i in range(len(M)):
        if i in visited:
            continue
        new_cost = cost + M[source][i]
        new_set = visited | {i}
        if i == dest:
            yield new_set, new_cost
        elif i not in visited:
            yield from all_paths_step(i, dest, new_set, new_cost)

def all_paths(source, dest, cost=0):
    result = {}
    for states, cost in all_paths_step(source, dest, frozenset([source]), cost):
        result[states] = min(result.get(states, float('inf')), cost)

    return result

to_dest = all_paths(SOURCE, DEST)
loops = {}

for i in range(len(M)):
    if i == DEST:
        continue
    for states, cost in all_paths(i, len(M) - 1, M[len(M) - 1][i]).items():
        loops[states] = min(loops.get(states, float('inf')), cost)

possible = {visited: cost for visited, cost in to_dest.items() if cost <= BUDGET}

process = set(possible.keys())
while process:
    process_next = set()
    while process:
        states = process.pop()
        for path, cost in loops.items():
            cost += possible[states]
            new_states = states | path
            if path <= states or cost >= possible.get(new_states, BUDGET + 1):
                continue
            possible[new_states] = cost
            process_next.add(new_states)
    process = process_next

print('result: {}'.format(max(possible, key=len)) if possible else 'none')

输出，无特定顺序的访问状态:

result: frozenset({0, 2, 3, 4})