Преобразование псевдокода в переполнение стека

Question

Преобразование псевдокода в переполнение стека

Я пытаюсь узнать о проблемах решения Маркова, и мне дали алгоритм для Итерации Значения, но я запутался, как превратить их в реальный код C ++. Главным образом части, где суммирование и тому подобное. Вот алгоритм:

function VALUE-ITERATION(P;R) returns a utility matrix
inputs: P, a transition-probability matrix
R, a reward matrix
local variables: U, utility matrix, initially identical to R
U', utility matrix, initially identical toR
repeat
U <- U'
for each state i do
U'(s_i) <-  R(s_i) + max_a Summation_j P^a_ij*U(s_j)
end
until max_(s_i) |U(s_i) - U'(s_i)| < e
return U

Для меня это выглядит иероглифами, есть ли более простой алгоритм, который может мне помочь? Или кто-нибудь может меня обескуражить?

1

c++markov pseudocode

Решение

Другие решения

Я могу перевести кусочки, но в вашем коде много информации, которая имеет смысл только в контексте, и у нас нет возможности узнать этот контекст.
Кроме того, кажется, что некоторое форматирование было потеряно по пути, так как P ^ a_ij выглядит так, как будто это было в одной точке P в степени a_i, умноженной на j. Дэвид, кажется, знает, как интерпретировать сумасшедший бит
Также цикл условий использует | в псевдокоде, который странный, но я понял это буквально.

utility_matrix VALUE_ITERATION(const probability_matrix& P,
const reward_matrix& R)
{
utility_matrix U(R);
utility_matrix UP(R);
do {
U = UP;
for(int s_i : ????) //for each state in what?
UP[s_i] = R[s_i] + ???? //max_a Summation_j P^a_ij*U(s_j)
while(max(s_i) ???? std::abs(U[s_i] - UP[s_i])<e);
return U;
}

Как сказал Акира, понятные биты просты: если вы не можете сделать это, вам, возможно, придется узнать больше о C ++, прежде чем заняться этим.

Согласно вашему комментарию, я нашел C-код, который выглядит примерно как ваш алгоритм Вот. (Строки 62-76)

2

Источник

Accepted Answer

Я нашел эту статью довольно легко: Алгоритмы итерации значений и политики итерации для решения задачи Маркова [PDF файл]. Это объясняет немного больше, что происходит.

Концептуально, у вас есть система, которая может находиться в нескольких состояниях, вознаграждения за переходы из одного состояния в другое и действия, которые иногда могут привести к переходам состояний. Основная идея состоит в том, чтобы продолжать итерацию, пока вы не получите полезную матрицу, которая не меняется. max_(s_i) | U(s_i) - U'(s_i)| < e ищет. (Вот, e это сокращение от epsilon, небольшое число и, вероятно, должно быть дополнительным входом.)

Для каждой итерации вы хотите выполнить наилучшее действие для каждого состояния. Лучшее действие — это то, которое приносит наибольшую награду, взвешенную по вероятности. Это то что max_a Summation_j P^a_ij*U(s_j) делает: Найти действие, которое дает лучшую награду, взвешенную по вероятности.

3