15 Questions
Co znajduje się w podstrukturze optymalnego rozwiązania problemu dotyczącego znalezienia najszybszej drogi do stacji S1, j?
Optymalne rozwiązanie podproblemów: znajdowania najszybszej drogi do S1, j - 1 lub S2, j – 1.
Jakie są definicje w kontekście rozwiązania rekurencyjnego?
Przypadek bazowy i ogólny przypadek.
Jakie wartości zależą od f1 [j – 1] oraz f2 [j - 1] w obliczaniu optymalnego rozwiązania?
fi [j] = min(f1 [j - 1] + a1,j ,f2 [j -1] + t2,j-1 + a1,j)
Jakie informacje zawarte są w strukturze rozwiązania optymalnego?
Rozważenie wszystkich możliwych sposobów przejścia z punktu startowego do stacji S1,j.
Jakie są możliwe sposoby przejścia z punktu startowego do stacji S1, j w strukturze rozwiązania optymalnego?
Najszybsza droga do S1, j jest albo droga do S1, j - 1 wtedy prosto do S1, j, albo droga do S2, j - 1 , transfer z linii 2 do linii 1 do S1, j.
Które zdanie najlepiej opisuje strukturę rozwiązania optymalnego?
Struktura rozwiązania optymalnego opiera się na generalizacji problemu i rekurencyjnym rozwiązaniu.
Jakie wartości są zawarte w definicji f* w kontekście rozwiązania rekurencyjnego?
Najszybszy czas przejścia z punktu startowego do wszystkich stacji.
Co zawiera rozwiązanie rekurencyjne w przypadku bazowym (j = 1)?
Zawiera minimalny czas przejścia od punktu startowego do pierwszej stacji dla obu linii metra.
W jaki sposób można obliczyć wartości fi[j] zależne od wartości f1[j – 1] oraz f2[j - 1]?
Można obliczyć wartości fi[j] metodą bottom-up, korzystając z już znanych wartości f1[j – 1] oraz f2[j - 1].
Co określa własność optymalnej podstruktury w kontekście problemu znajdowania najszybszej drogi do stacji S1, j?
Określa, że optymalne rozwiązanie problemu zawiera optymalne rozwiązania podproblemów.
Co to jest f* w kontekście rozwiązania rekurencyjnego?
Najszybszy czas od punktu startowego do stacji Si,j
Co zawiera definicja f2 [j] w kontekście rozwiązania rekurencyjnego?
Minimalny czas od punktu startowego do stacji S2,j
Co określa własność optymalnej podstruktury w kontekście problemu znajdowania najszybszej drogi do stacji S1, j?
Właściwości optymalnych rozwiązań podproblemów
Jakie są definicje f1 [j] oraz f2 [j] w kontekście rozwiązania rekurencyjnego?
Czasy przejścia od startu do stacji Si,j
Jakie są możliwe sposoby przejścia z punktu startowego do stacji S1, j w strukturze rozwiązania optymalnego?
Przez S1, j - 1 lub S2, j - 1
This quiz covers the key concepts of dynamic programming algorithm, including defining the optimal solution structure, recursive definition of optimal solution value, bottom-up computation of optimal solution value, and constructing the optimal solution based on computed information. It also includes assembly line planning for a car factory with two assembly lines and n stations each.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
