Редактирование: Динамическое программирование

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 29: Строка 29:
  
 
Рассмотрим путь $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$ длиннее.  
 
Рассмотрим путь $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-полная задача]], т.е. вряд ли ее можно решить в течение полиномиального времени.  
+
Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это NP-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.  
  
  
Строка 92: Строка 92:
 
   '''if''' n <= 1
 
   '''if''' n <= 1
 
     '''return''' 1
 
     '''return''' 1
   a = Fibonacci(n - 1)
+
   a = Fibonacci(n-1)
   b = Fibonacci(n - 2)
+
   b = Fibonacci(n-2)
 
   '''return''' a + b
 
   '''return''' a + b
  
Строка 102: Строка 102:
 
   '''if''' fib[n] != -1 <font color=green>// проверка на то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib</font>
 
   '''if''' fib[n] != -1 <font color=green>// проверка на то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib</font>
 
     '''return''' fib[n]
 
     '''return''' fib[n]
   fib[n - 1] = Fibonacci(n - 1)
+
   fib[n-1] = Fibonacci(n-1)
   fib[n - 2] = Fibonacci(n - 2)
+
   fib[n-2] = Fibonacci(n-2)
   '''return''' fib[n - 1] + fib[n - 2]
+
   '''return''' fib[n-1] + fib[n-2]
  
 
==См.также==
 
==См.также==
* [[Динамическое программирование по профилю]]
+
* [[<math>\mathrm{NP}</math>-полнота]]
* [[Динамика по поддеревьям]]
 
  
 
==Источники информации==
 
==Источники информации==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: