寻求一些帮助来解决无限期问题、成本最小化问题以及一些必须访问的状态。
我们有一个预算 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 并提出解决方案,但我无法清楚地表述算法...
对于如何清晰地构建这个框架并提出直接解决方案,我们表示赞赏。
最佳答案
如果您的成本矩阵包含负循环,那么最终可以访问所有状态。您可以使用 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})
关于java - 构建无限期的 MDP,使用必访状态实现成本最小化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40077864/