#java #algorithm #dynamic-programming
#java #алгоритм #динамическое программирование
Вопрос:
Я только начал понимать концепцию динамического программирования. Я понимаю, что он используется для кэширования результатов для будущих вызовов и действительно эффективен при разработке сложных алгоритмов, которые дают экспоненциальное время выполнения. Чего я не понимаю, так это того, как поток будет работать программно. Например, для вычисления n-го числа Фибоначчи с использованием динамического программирования следующим образом. На что похож поток в программе?
int[] fibMap = new int[max]
int fibo(int i){
if(i == 0) return 0;
if(i == 1) return 1;
if( fibMap[i] != 0) return fibMap[i]; // return cached result
fibMap[i] = fibo(i-1) fibo(i-2); //Cache result
return fibMap[i];
}
Я нашел этот код в одном из справочников по Java, которые я использую, но мне трудно понять, как будет работать эта программа. Скажем, если мы захотим вычислить простой фибо (3) или фибо (5), не мог бы кто-нибудь, пожалуйста, объяснить мне, как программа будет кэшировать результат и как общий поток будет работать для этой проблемы по сравнению с обычным рекурсивным подходом без DP, как показано ниже?
int fibo(int i){
if(i == 0) return 0;
if( i == 1) return 1;
return fibo(i-1) fibo(i-2);
}
Комментарии:
1. Вы пробовали вытащить надежный старый карандаш и бумагу и следовать этому вручную?
2. Кстати, то, что вы делаете, называется запоминанием. Это в основном то же самое, что и динамическое программирование, за исключением того, что в последнем алгоритмы обычно пишутся итеративно, а не рекурсивно, что заставляет вас думать о потоке и данных, которые вы отслеживаете явно. Кроме того, я исправил вашу опечатку.
3. Да, я изложил это на бумаге. Чего я не понимаю, так это когда в первом цикле if, где написано fibMap[i] != 0, затем возвращает fibMap[i] . Если, скажем, i = 5, то в первую очередь fibMap[5] не будет иметь правильного значения, потому что в массиве еще ничего не сохранено. Как это все еще продолжается?
4. @JimZilla: поскольку значение неверно, затем он пытается оценить
fibo(i-1)иfibo(i-2), и когда они завершены, он сохраняет значение, а также возвращает его. Это помогает?5. Не по теме, но не удержался: первые две строки можно заменить одной строкой:
if (i < 2) return i;
Ответ №1:
Ваш код
int fibo(int i){
if(i == 0) return 0;
if(i == 1) return 1;
if( fibMap[i] != 0) return fibMap[i]; // return cached result
fibMap[i] = fibo(i-1) fibo(i-2); //Cache result
return fibMap[i];
}
или, что эквивалентно
int fibo(int i){
if(i == 0) return 0;
if(i == 1) return 1;
if( fibMap[i] == 0)
fibMap[i] = fibo(i-1) fibo(i-2); //Cache result
return fibMap[i];
}
таким образом, «поток» — это в основном то же самое, что и некэшированная версия, за исключением того, что вы избегаете пересчета результатов, которые вы уже вычислили.
Комментарии:
1. Спасибо, сэр. Немного поломав голову, я немного понял. Скажем, если бы нам пришлось оценивать fibo (3). Поскольку fibMap[3] == 0, он будет разделен на fibMap [3] = fibo(2) fibo (1) . теперь у fibo(2) будет новый результат в fibMap[2] = fibo(1) fibo(0), который возвращает значение 1 обратно в fibMap[2] . Теперь fibMap[3] = fibMap[2] fibo(1), что равно 1 1 = 2. Правильно ли это? Если да, то как помогает сохранение результата в массиве? Я знаю, что это глупый вопрос, но хранятся ли эти кэшированные результаты вне функции?
2. @JimZilla: Да, вы правы. Если значение найдено в массиве,
fiboоно больше не вызывается. Поскольку в большинстве случаев каждый вызов генерирует дополнительные 2 вызова, вы получите экспоненциальное количество вызововfibo, если вы не сохраните результат где-нибудь, вот почему это помогает.3. ах! ПОЛУЧИТЕ СЕЙЧАС. Большое спасибо!