Изменения
Нет описания правки
Рассмотрим путь $q \rightarrow r \rightarrow t$, который является самым длинным простым путем $q \rightsquigarrow t$. Является ли путь $q \rightarrow r$ самым длинным путем $q \rightsquigarrow r$? Нет, поскольку простой путь $q \rightarrow s \rightarrow t \rightarrow r$ длиннее. Является ли путь $r \rightarrow t$ самым длинным путем $r \rightsquigarrow t$? Снова нет, поскольку простой путь $r \rightarrow q \rightarrow s \rightarrow t$ длиннее.
Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это [[Классы NP, coNP, Σ₁, Π₁|NP-полная задача]], т.е. вряд ли ее можно решить в течение полиномиального времени.
'''if''' n <= 1
'''return''' 1
a = Fibonacci(n-1) b = Fibonacci(n-2)
'''return''' a + b
'''if''' fib[n] != -1 <font color=green>// проверка на то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib</font>
'''return''' fib[n]
fib[n-1] = Fibonacci(n-1) fib[n-2] = Fibonacci(n-2) '''return''' fib[n-1] + fib[n-2]
==См.также==
* [[<math>\mathrm{NP}</math>-полнотаДинамическое программирование по профилю]]* [[Динамика по поддеревьям]]
==Ссылки и источники информации==
