YouTube

Got a YouTube account?

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

Russian subtitles

← Unit 2, Topic 2, Route Finding Question

Unit 2, Topic 2, Route Finding Question

Get Embed Code
20 Languages

Showing Revision 1 created 10/13/2011 by Amara Bot.

  1. И ответ в этом случае - нет.
  2. Агент не сможет предложить никакого решения
  3. потому что Бухарест на карте отсутствует,
  4. так что агент не знает каким способом туда можно добраться.
  5. Теперь давайте улучшим шансы агента.
  6. Теперь мы дали агенту полную карту Румынии.
  7. Выезжать ему надо из Арада, а пункт назначения - цель путешествия - Бухарест.
  8. Агенту надо решить задачу и предложить серию действий
  9. которые приведут его в пункт назначения.
  10. Способен ли агент решить эту задачу?
  11. И ответ в данном случае - да.
  12. Существует множество маршрутов (шагов, последовательностей действий), которые приведут в пункт назначения.
  13. Вот один из них:
  14. Выехать из Арада, потом направиться сюда, затем сюда, и потом вот сюда,
  15. а дальше вот сюда и сюда - и вы достигли цели путешествия.
  16. Этот маршрут можно считать решением задачи.
  17. Это последовательность действий, связанных друг с другом, которые гарантированно приведут нас к цели.
  18. [ФОРМУЛИРОВКА ПРОБЛЕМЫ]
  19. Теперь давайте формально определим как выглядит наша проблема.
  20. Проблему можно разбить на несколько частей.
  21. Первая часть - исходное состояние, из которого агент начинает строить маршрут.
  22. В нашей задаче по поиску маршрута исходное состояние - агент находится в городе Арад.
  23. Затем функция Действия получает информацию об исходном состоянии и возвращает в качестве результата
  24. набор возможных действий, которые агент может осуществить находясь в этом состоянии.
  25. [ДЕЙСТВИЯ (s) {a,a2,a3...}]
  26. В некоторых задачах одни и те же действия будут доступны агенту во всех состояниях,
  27. тогда как в других задачах, разные действия будут доступны в зависимости от состояния.
  28. В нашей задаче по нахождению маршрута все действия зависят от состояния.
  29. Когда мы находимся в одном городе, мы можем поехать в любой из соседних с ним городов,
  30. но мы не можем поехать в любые другие произвольные города.
  31. Затем у нас есть функция Результат, которая получает на входе состояние и действие
  32. и возвращает новое состояние в качестве результата.
  33. Так например, если агент находится в городе Арад - это его состояние -
  34. и принимает решение поехать по автодороге E-671 в сторону Тимисоара,
  35. то результатом применения этого действия в этом состоянии будет новое состояние -
  36. состояние, где агент теперь находится в городе Тимисоара.
  37. Затем нам нужна функция проверки цели,
  38. которая получает информацию о состоянии и возвращает логическое значение -
  39. верно или неверно - которое указывает на то, является данное состояние целью или нет.
  40. В задаче по нахождению маршрута единственной целью будет достижение пункта назначения -
  41. города Бухареста - и любое другое состояние должно вернуть значение "неверно" для функции проверки цели.
  42. И наконец нам нужна еще одна деталь - функция стоимости маршрута -
  43. которая получает информацию о выбранном маршруте, последовательности состояний и действий,
  44. и возвращает число соответствующее стоимости этого маршрута.
  45. В большинстве задач, с которыми мы будем иметь дело, мы будем рассматривать функцию стоимости маршрута как функцию суммы
  46. таким образом, что стоимость маршрута - это просто сумма стоимости всех индивидуальных шагов.
  47. То есть мы будем использовать эту функцию стоимости как функцию стоимости шага.
  48. Функция стоимости шага получает информацию о состоянии, действии, и конечном состоянии в результате данного действия
  49. и возвращает число - n - стоимость этого действия.
  50. В примере с поиском маршрута стоимость может обозначать количество пройденных миль
  51. или это может быть количество минут, потребовавшихся для достижения пункта назначения.