2004-gre-cs-practice-book.pdf/Q50 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Вопрос: Q50-4c9f66 == | == Вопрос: Q50-4c9f66 == | ||
| − | + | {{50-51 вопрос из теста 2004}} | |
| − | + | ||
| − | + | Какой из следующих этапов является общим в рекурентной схеме, где <m> 0 \le k \le n</m> | |
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>A(k, i, j) = \min_{l < k}(A(l, i, k)+A(l, k, j)) </m> |
| − | ( | + | * <m>A(k, i, j) = \min_{l < k}(A(k-1, i, l)+A(k-1, l, j)) </m> |
| + | * Правильный ответ: <m>A(k, i, j) = \min(A(k-1, i, j), A(k-1, i, k)+A(k-1, k, j)) </m> | ||
| + | * <m>A(k, i, j) = \min(C(i, j), A(k, i, k)+A(k, k, j)) </m> | ||
| + | * <m>A(k, i, j) = \min(C(i, j), A(k-1, i, k)+A(k-1, k, j)) </m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|35|50}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Формулы немного пугают, но надо же помнить | |
| − | + | * рекурсивная зависимость — от таблицы на предыдущей итерации | |
| − | + | * и на таблицу расстояний не смотрим — выбираем минимум между известным путем и суммой путей через какой-то транзитный новый узел. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | |||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:30, 15 декабря 2024 (UTC)}} |
| − | [[Категория: | + | [[Категория:Алгоритмы на графах]] |
Текущая версия на 15:30, 15 декабря 2024
Вопрос: Q50-4c9f66
Задача о кратчайшем пути для всех пар может быть определена следующим образом
Input
Направленный граф , где
Стоимость для всех , где тогда и только тогда, когда
Definition
длина кратчайшего пути от до для всех
Если нет пути от до , то
Если для всех
Problem
Определить для всех
Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям
длина кратчайшего пути от до , для которого все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если
Тогда
Алгоритм вычисляет используя рекуррентность по , где начальный шаг задается следующим образом
для и
для всех
Какой из следующих этапов является общим в рекурентной схеме, где
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 50 на 35 странице книги «2004-gre-cs-practice-book.pdf»
Формулы немного пугают, но надо же помнить
- рекурсивная зависимость — от таблицы на предыдущей итерации
- и на таблицу расстояний не смотрим — выбираем минимум между известным путем и суммой путей через какой-то транзитный новый узел.