YouTube

Got a YouTube account?

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

Polish 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. Odpowiedź brzmi nie--
  2. nie ma rozwiązania, do którego agent mógłby dojść
  3. ponieważ Bukareszt nie pojawia się na mapie.
  4. Zatem agent nie zna żadnych działań, dzięki którym mógłby tam dotrzeć.
  5. Dajmy zatem agentowi większą szansę.
  6. Teraz daliśmy agentowi pełną mapę Rumunii.
  7. Na starcie jest w Arad, a meta--albo cel--jest w Bukareszcie.
  8. Agent otrzymuje zadanie dojścia do sekwencji działań
  9. dzięki którym dotrze do celu.
  10. Czy jest możliwe, że agent rozwiąże ten problem?
  11. Odpowiedź brzmi: tak--istnieje wiele tras albo kroków albo sekwencji działań
  12. które doprowadzą do celu.
  13. Oto jedna z nich:
  14. Zaczynając w Arad i podejmując najpierw ten krok, a następnie ten, a potem ten,
  15. a później ten--i w końcu ten, żeby dotrzeć do celu.
  16. Liczyłoby się to zatem jako rozwiązanie problemu.
  17. Zatem sekwencja czynności, uszeregowanych razem, które gwarantują, że dotrzemy do celu.
  18. [OKREŚLENIE PROBLEMU]
  19. Zdefiniujemy teraz formalnie, na czym polega problem.
  20. Problem może zostać rozbity na pewną ilość komponentów.
  21. Po pierwsze, stan początkowy, od którego agent zaczyna. [STAN POCZĄTKOWY]
  22. W przypadku problemu wyznaczania trasy, stan początkowy był taki, że agent był w mieście Arad.
  23. Następnie, funkcja, Działania, która pobiera stan na wejściu i zwraca [Działania (s)]
  24. zbiór możliwych działań, które agent może wykonać, gdy jest w danym stanie.
  25. [DZIAŁANIA (s) {a,a2,a3...}]
  26. W przypadku pewnych problemów, agent będzie mógł podejmować te same działania w każdym ze stanów
  27. a w przypadku innych problemów, zbiór możliwych do podjęcia działań będzie zależał od stanu.
  28. W przypadku zagadnienia wyznaczania trasy, dzialania są zależne od stanu.
  29. Gdy jesteśmy w jednym mieście, możemy wybrać trasy do sąsiadujących miast--
  30. ale nie możemy się udać do żadnego innego miasta.
  31. Dalej, mamy funkcje nazywaną Wynikiem, która pobiera, jako wejście, stan oraz działanie
  32. i dostarcza jako, jako wyjście, nowy stan. [WYNIK(s,a) S1]
  33. Zatem, na przykład, jeżeli agent jest w mieście Arad, i uznaje, że to jest jego stan,
  34. i podejmuje działanie polegające na jechaniu trasą E-671 w stronę Timisoary,
  35. wynikiem zastosowania tego działania w tym stanie byłby nowy stan--
  36. w którym agent znajduje się w mieście Timisoara.
  37. Dalej, potrzebujemy funkcji nazywanej Sprawdzeniem Celu
  38. która pobiera stan i zwraca wartość logiczną-- [SPRAWDZENIE CELU (s) P/F]
  39. prawdę bądź fałsz--która mówi nam, czy agent osiągnął już cel, czy nie.
  40. W przypadku zagadnienia wyznaczania trasy, jedynym celem byłoby bycie w docelowym mieście--
  41. w Bukareszcie--a wszystkie pozostałem stany zwracałyby wartość fałszu przy Sprawdzeniu Wyniku.
  42. Wreszcie potrzebujemy jeszcze jednej rzeczy, którą jest funkcja Kosztu Ścieżki--
  43. która pobiera ścieżkę, czyli sekwencję przejść stan/działanie,
  44. a zwraca liczbę, ktora jest kosztem ścieżki. [KOSZT ŚCIEŻKI]
  45. Dla większości problemów, z którymi będziemy mieli do czynienia, byędziemy chcieli, żeby funkcja Kosztu Ścieżki była addytywna
  46. to znaczy, żeby koszt ścieżki był po prostu sumą kosztów poszczególnych kroków.
  47. Zatem będziemy realizować tę funkcję Kosztu Ścieżki za pomocą funkcji Kosztu Kroku.
  48. Funkcja Kosztu Kroku pobiera stan, działanie oraz stan będący wynikiem podjęcia działania,
  49. i zwraca liczbę, n, która stanowi koszt tego działania. [KOSZT KROKU (s, a, s1)=n]
  50. W przykładzie znajdowania trasy, koszt może być liczbą przebytych kilometrów
  51. albo liczbą minut wymaganych na dotarcie do celu.