Here's my implementation, which should be relatively straight forward.
We have a value function that is the same size as my world,
and I initialize with 99 everywhere.
This has to be evaluated as large enough it doesn't conflict with any actual value.
I now update the value function a number times--I don't know how often--
but as long as change something, I update it.
Therefore, I introduced the variable "change," which I set to True in the beginning.
While change is the case, I update, but I neatly set change to False.
The only way to come back to True is that I actually changed something.
Now I go through all the grid cells in a fixed order.
It happens to be not very efficient, but certainly gets the job done.
I first check if the grid cell I'm considering is the goal.
Here is a typical case where I check for change.
If the value is presently correctly set to 0, I don't do anything.
If it's larger than 0, such as 99, then I set it down to 0, and I've just changed something.
Therefore, I set the change flag back to True.
If it's not a goal cell, then here is my full update function.
I go through all the actions.
I project a potential next state upon executing an action
by adding the corresponding delta to the x and y.
That gives me x2 and y2.
I test whether x2 and y2 are legitimate states.
For that they have to be inside the grid.
I check whether the numbers are larger than 0 and smaller than the dimension of the grid.
And it has to be an action that action navigable grid cell.
Therefore, I check that the coordinates in the grid has a 0.
If that's the case, I can propagate back the value.
My new value is the value of this future grid cell plus the cost per step,
which happens to be 1.
Now, if this value is better than the value I have already, which means it is smaller,
then I assign this new value to my original grid cell x and y, plus of course the cost step.
Then I know I've changed something.
Therefore I set change to "True," and the procedure repeats.
The only thing missing at the very end when I'm done,
I print out the value function using these commands over here.
I should warn you this is not very efficient.
The reason why it is not efficient is that value slowly propagates
from the end towards the beginning.
But leaving this concern aside, it actually computes the correct value function.
There are ways to make it more efficient.
It's also interesting to see what happens if I cut off any path to the goal.
The the resulting value function will retain 99s for most of the state variables--
exactly those where there is no valid path to the goal.
これが私の実装です これは比較的簡単でしょう
私の世界と同じサイズの価値関数があります
そしてすべて99で初期化します
これは実際の価値と競合しないよう
十分大きな値を求める必要があります
ここで価値関数を何度も更新しています
回数は分かりませんが変更がある限り更新します
そこで変数changeを導入し
冒頭でTrueに設定しています
変更がある限り更新しますが
changeをきちんとFalseに設定します
Trueに戻るのは実際に変更した場合のみです
ここからすべてのグリッドセルを
決まった順序で調べます
あまり効率的ではありませんが
確実に作業を完了できます
まず対象となるグリッドセルが
ゴールかどうかをチェックします
変更があるかを確認する典型的なケースです
現在の価値が
正しく0に設定されていれば何もしません
99など0よりも大きい場合は
0に設定して変更を行います
従ってchangeフラグをTrueに戻します
このセルがゴールではない場合
ここが私の完全な更新機能ですが
すべての動作を調べます
対応するdeltaをxとyに足すことによって
次に起こり得る状態を動作の実行時に予想します
この結果x2とy2が得られるので
x2とy2が妥当な状態かどうかをテストしますが
そのためには
グリッドの内側になければなりません
この2つの数値が0以上かつグリッドの
寸法よりも小さいかをチェックします
またセルを移動できる動作でなければなりません
そこでグリッド内の座標が
0であることをチェックします
それが0なら価値を伝播できます
新しい価値はこの将来のグリッドセル値に
ステップごとのコストを足したもので
コストは1です
これがすでに持っている価値よりもよい場合
つまり価値が小さければ
この新しい価値を元のグリッドセルのxとyに代入し
もちろんコストステップも足します
変更したことが分かっているので
changeをTrueに設定しプロシージャを繰り返します
処理が完了して最後に残っているのは
このステートメントを使って
価値関数を出力することです
この方法はあまり効率的ではありません
その理由は最後から最初に向かって
価値が緩やかに伝播するからです
しかし価値関数を正しく計算してくれます
より効率的に行う方法は他にもあります
またゴールまでの経路をすべて塞いだ場合
面白い結果が出ます
得られた価値関数は
ほとんどの状態変数に対して99を保持し
ゴールまでの有効な経路がない場所です
Вот моя реализация, которая должна быть довольно прямо вперед.
У нас есть значение функции, которая является же размера, как мой мир
и я инициализировать с 99 везде.
Это должно оцениваться как достаточно большой, не конфликтующую с любым фактическим значением.
Я теперь обновить функцию value число раз--не знаю, как часто--
но как долго, как что-то изменить, я обновить его.
Поэтому, я представил переменная «смена», который я установил значение True в начале.
Хотя изменение является случай, я обновить, но я аккуратно набор изменений в значение False.
Единственный способ вернуться к True является, что я на самом деле изменил что-то.
Теперь я иду через все ячейки сетки в фиксированном порядке.
Это случается быть не очень эффективно, но, безусловно, получает работу сделано.
Я сначала проверить, если ячейки сетки, которую я рассматриваю это цель.
Вот типичный случай, когда я проверить изменения.
Если в настоящее время правильно задано значение 0, я ничего не делают.
Если это больше, чем 0, например 99, затем я установить его до 0, и я только что изменил что-то.
Таким образом я установил флаг изменения обратно в значение True.
Если это не цель ячейку, то вот моя функция полное обновление.
Я иду через все действия.
Я проекта потенциальным следующее состояние после выполнения действия
путем добавления соответствующих дельта x и y.
Это дает мне x 2 и y2.
Я проверить, являются ли x 2 и y2 легитимных государств.
Для этого они должны быть внутри grid.
Я проверить, являются ли число больше 0 и меньше, чем размер сетки.
И он должен быть действие что действий судоходных ячейке.
Поэтому я проверить, что координаты в сетке имеет значение 0.
Если это так, я могу распространять обратно значение.
Мое новое значение является значением этого будущего ячейке плюс стоимость шаг,
который случается быть 1.
Теперь если это значение равно лучше, чем значение, у меня уже, который означает, что он меньше,
затем назначить моей первоначальной ячейки сетки это новое значение x и y, плюс конечно стоимость шаг.
Тогда я знаю, что я изменил что-то.
Поэтому я задать изменение «True», и повторяется процедура.
Единственное, что отсутствует в самом конце, когда я сделал,
Я распечатать значение функции, используя эти команды над здесь.
Я должен предупредить вас, что это не очень эффективным.
Почему это не эффективный причина что значение медленно распространяется
от конца к началу.
Но оставляя эту озабоченность в стороне, она на самом деле вычисляет функцию правильное значение.
Есть способы, чтобы сделать его более эффективным.
Это также интересно посмотреть, что произойдет, если я отрезал любой путь к цели.
Результирующее значение функция сохранит 99s для большинства переменных состояния--
именно те там, где нет действительный путь к цели.