Обрамление неопределенного горизонта MDP, минимизация затрат с помощью обязательных к посещению состояний

Если ваша матрица затрат содержит отрицательные циклы, то в конечном итоге можно посетить все состояния. Вы можете использовать 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})