YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Russian subtitles

← 04-24 Dynamic Programming

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 1 created 12/24/2012 by Eldar.

  1. Теперь я хочу научить вас альтернативному методу для планирования.
  2. Этот альтернативный метод имеет ряд преимуществ и ряд недостатков.
  3. Это называется динамическим программированием,
  4. и так же, как A-star, он будет искать кратчайший путь.
  5. Вы даете ему карту окружающей среды как в A-star, один или несколько позиций цели--
  6. Допустим только одна целевая позиции.
  7. Он выводит это лучший путь от любого возможного начала местоположения.
  8. Эта методика планирования не ограничивается только единственным
  9. началом местоположения, но к любому начальному местоположению. Зачем нам беспокоиться по этому поводу?
  10. Позвольте мне привести вам один пример.
  11. Предположим, что Google самодвижущийся автомобиль в среде, как эта.
  12. Вы находитесь на этой маленькой улице здесь, и вас попросят повернуть направо,
  13. но ваша цель право здесь.
  14. Как и прежде, есть две различные полосы здесь--левый поворот переулка и прямая переулок.
  15. Если вы достигнете прямой переулок, единственный способ, чтобы добраться до цели
  16. — идти вокруг блока здесь и действовать в этом направлении.
  17. Вы видели этот пример раньше.
  18. Теперь я хочу сделать суть другой.
  19. То есть ваша попытка сделать сдвиг переулка здесь может завершиться неудачей. Почему это будет неудачно?
  20. Может быть есть большой, большой грузовик в этой полосе здесь,
  21. и когда вы идете в правую полосу, тогда вы ждете когда грузовик исчезнет,
  22. есть эти люди позади вас, которые кричат.
  23. Вы действительно не хотите ждать когда грузовик исчезнет.
  24. Это означает, что окружающей среде стохастическая.
  25. Результаты действий являются недетерминированными.
  26. В нашем планировании пока что мы игнорировали это, но в действительности это так.
  27. В действительности вы могли бы найти себя--ух ты, я здесь. Как это произошло?
  28. Ну, это произошло потому, что мир стохастический и этот грузовик здесь--
  29. Этот глупый грузовик---не позволяют вам.
  30. Это означает, что вам нужен план не только для наиболее вероятной позиции
  31. но вам может потребоваться план для других позиций.
  32. Что динамическое программирование дает вам, это план для каждой позиции.
  33. Если мы перерисуем эту среду в сетку с расположением цели и определенными препятствиями,
  34. динамическое программирование дает вам оптимальные действия сделать в каждой ячейки сетки.
  35. Как вы можете видеть, каждая ячейка сетки теперь имеет метку.
  36. Этот ярлык часто называют тактикой,
  37. и тактика — это функция, которая сопоставляет ячейки сетки в действия
  38. с действием в этом случае как шаг влево, вниз, вправо или переместить вверх.
  39. Теперь мы будет вычислить тактику, с помощью динамического программирования.
  40. То есть учитывая сетки мира как эта и цель положения как это
  41. Мы будем писать программу, которая выведет для каждой ячейки сетки
  42. что самое лучшее следует сделать роботу чтоб найти себя там.
  43. Это требует другого алгоритма чем A-star.
  44. Это случается быть более участвующих алгоритмов вычисления.
  45. Как я сказал ранее, это называется динамическим программирование робота пути планирования.