YouTube

Got a YouTube account?

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

Portuguese 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. E a resposta é não.
  2. Não há solução que o agente possa encontrar
  3. porque Bucareste não aparece no mapa.
  4. e, portanto, o agente não conhece nenhuma ação que possa levar até lá.
  5. Vamos dar então ao agente uma chance melhor.
  6. Agora demos ao agente o mapa completo da Romênia.
  7. O início é em Arad e o destino--ou objetivo--é em Bucareste,
  8. e é dado ao agente o problema de determinar uma sequência de ações
  9. que levem até o destino.
  10. É possível o agente resolver este problema agora?
  11. A resposta é sim--há várias rotas ou passos ou sequências de ações
  12. que levarão ao destino.
  13. Aqui está uma delas:
  14. Começando em Arad, realizando este primeiro passo, e depois este, depois este,
  15. e depois este--e mais este para chegar ao destino.
  16. Isto contaria como uma solução para o problema.
  17. É uma sequência de ações interligadas que certamente nos levará ao objetivo.
  18. [DEFINIÇÃO DE UM PROBLEMA]
  19. Vamos agora definir formalmente os aspectos de um problema.
  20. Um problema pode ser dividido em uma série de componentes.
  21. Primeiro, o estado inicial no qual o agente inicia. [ESTADO INICIAL]
  22. Em nosso problema de determinação de rota, o estado inicial era o agente estar na cidade de Arad.
  23. Em seguida, uma função, ações, que pega um estado como entrada e retorna
  24. um conjunto de ações possíveis que o agente pode executar quando o agente está nesse estado.
  25. [AÇÕES (s) {a,a2,a3...}]
  26. Em alguns problemas, o agente terá as mesmas ações disponíveis em todos os estados,
  27. enquanto em outros problemas ele terá ações diferentes dependentes do estado.
  28. No problema de determinação de rota, as ações são dependentes do estado.
  29. Quando estamos em uma cidade, podemos usar as rotas para as cidades vizinhas,
  30. mas não podemos ir a qualquer outra cidade.
  31. Em seguida, temos uma função chamada Resultado, que usa como entrada um estado e uma ação
  32. e retorna como saída, um estado novo [RESULTADO (s,a) S1]
  33. Assim, se por exemplo o agente está na cidade de Arad e assume isso como sendo seu estado,
  34. e toma a ação de dirigir ao longo da Rota E-671 em direção à Timisoara,
  35. então o resultado de aplicar essa ação nesse estado seria o estado novo--
  36. onde o agente está na cidade de Timisoara.
  37. Agora, precisamos de uma função chamada de Verificação de Objetivo,
  38. que pega um estado e retorna um valor booleano-- [TESTE DE OBJETIVO (s) V/F]
  39. verdadeiro ou falso--nos dizendo se este estado é um objetivo ou não.
  40. Em um problema de determinação de rota, o único objetivo seria estar na cidade destino--
  41. a cidade de Bucareste--e todos os outros estados retornariam falso para o Verificação de Objetivo.
  42. Finalmente, precisamos de mais uma coisa, a função Custo do Caminho,
  43. que pega uma rota, uma sequência de transições estado/ação,
  44. e retorna um número que é o custo daquele caminho. [CUSTO DO CAMINHO]
  45. Para a maioria dos problemas com os quais lidaremos, faremos a função Custo do Caminho ser aditiva
  46. para que o custo do caminho seja simplesmente a soma dos custos dos passos individuais.
  47. Assim implementaremos esta função Custo do Caminho, em termos de uma função Custo do Passo.
  48. A função Custo do Passo pega um estado, uma ação e o estado resultante daquela ação
  49. e retorna um número, n, que é o custo daquela ação. [CUSTO DO PASSO (s, a, s1)=n]
  50. No exemplo de determinação de rota, o custo pode ser o número de milhas viajadas
  51. ou talvez o número de minutos que leva até chegar àquele destino.