YouTube

Got a YouTube account?

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

French 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. Une réponse est non.
  2. Il n'y a pas de solution qu'un agent puisse trouver
  3. parce que Bucharest n'apparait pas sur la carte,
  4. Et donc l'agent ne sait pas quelles actions permettent d'arriver la bas.
  5. Donc donnons à l'agent une meilleur chance.
  6. Maintenant nous avons donné à l'agent une carte complète de la Roumanie
  7. Pour commencer, il est a Arad et la destination--ou objectif--est Bucharest .
  8. Et l'agent est donné le problème de trouver une suite d'actions
  9. qui amènent à destination.
  10. Maintenant, est il possible pour l'agent de résoudre ce problème ?
  11. Et la réponse est oui.
  12. il y a plusieurs routes ou pas ou suites d'actions qui amènent a destination.
  13. Ici l'un d'entres eux :
  14. Commençons à Arad, prenant ce premier pas , puis celui la , puis celui ci,
  15. et celui la,et ensuite celui la, pour arriver à destination.
  16. Donc ça compterais comme solution au problème.
  17. Alors suite d'actions, chainés ensemble, qui sont garantis de nous amener jusqu'a l'objectif .
  18. [DEFINITION D'UN PROBLEME]
  19. Maintenant définissions formellement ce qu'est un problème.
  20. Un problème peut etre découper en un certain nombre de composants.
  21. Premièrement, l'état initial est ce que l'agent commence avec.
  22. Dans notre problème de recherche d'itinéraire, l'état initial était que l'agent soit dans la ville d'Arad.
  23. Ensuite, une fonction--Actions--qui prend un état comme donnée et retourne
  24. un ensemble possible d'actions que l'agent peut éxécuter quand l'agent est dans cet état .
  25. [ACTION (s) {a,a2,a3...}]
  26. Dans quelques problèmes, l'agent pourra avoir les memes actions disponibles dans tous les états
  27. et dans d'autres problèmes, il aura d'autres actions dépendantes de l'état .
  28. Dans le problème de recherche d'itinéraire, les actions sont dépendantes de l'état .
  29. Quand nous sommes dans une ville, on peut prendre des routes jusqu'aux villes voisines--
  30. mais nous ne pouvons aller dans d'autres villes.
  31. Ensuite nous avons une fonction appelée Resultat, qui prend, comme donnée, un état et une action
  32. et délivre, en résultat, un nouvel état.
  33. Donc, par exemple, si l'agent est dans la ville d'Arad, et la prend comme état,
  34. et prend comme action que de conduire sur la route E-671 vers Timisoara,
  35. alors le résultat que d'appliquer cette action à cet état serait un nouvel état--
  36. où l'agent est dans la ville de Timisoara.
  37. Ensuite, nous avons une fonction appelée Test De But.
  38. qui prend un état et retourne une valeur booléene--
  39. vrai ou faux--nous disant si l'état est un objectif ou non.
  40. Dans un problème de recherche d'itinéraire, le seul objectif serait d'etre dans la ville de destination--
  41. la ville de Bucharest--et les autres états retourneraient faux pour le Test De But.
  42. Et finalement , nous avons une chose en plus qui est une fonction de coût de chemin .
  43. qui prend un chemin, une suite de état/action de transitions,
  44. et retourne un nombre, qui est le cout du chemin.
  45. Maintenant, pour la plupart des problèmes qu'on verra , nous allons faire additive la fonction de coût de chemin
  46. donc le cout du chemin est juste une comme de coûts des pas individuels.
  47. Et nous implémenterons cette fonction de coût de chemin, en termes de fonction de cout de pas.
  48. La fonction de coût de pas prend un état, une action, et le résultat sera l'état par cette action,
  49. et retourne un nombre--n-- qui est le coût de cette action.
  50. Dans l'exemple de recherche d'itinéraire, le coût pourrait etre un nombre de miles parcourus
  51. ou peut etre le nombre de minutes qu'il faut pour aller à destination.