Алгоритмы, сети и линейное программирование
Введено| English | Значение |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | минимальное остовное дерево |
Самая дешевая сеть или самый короткий маршрут?
- Школе необходимо соединить здания кабелем. Самый короткий маршрут между двумя зданиями и самая дешевая сеть в целом — это разные задачи.
- Этот урок изучает дерево минимального веса: связный нетрицикловый граф, соединяющий каждую вершину с наименьшим возможным суммарным весом ребер.
Выберите математическую структуру
- Алгоритм Краскала выбирает ребра по возрастанию веса, избегая циклов. Алгоритм Дейкстры обновляет кратчайшие предварительные расстояния от начальной точки. Линейное программирование оптимизирует линейную целевую функцию в допустимой области; проверяйте вершины и целочисленные ограничения при необходимости.
- Укажите допустимые входные данные и единицы измерения перед вычислением. Уравнение должно отражать зависимость, а не просто фиксировать ввод в калькулятор.
Алгоритмы Крускала и кратчайшего пути оба дали общую стоимость 6 на примере сети. Почему это не делает их взаимозаменяемыми?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Цели различны: остовное дерево соединяет все вершины (n-1 рёбер, без циклов), тогда как кратчайший путь оптимизирует маршрут только от одной точки к другой. Равенство ответов здесь случайно.
Разберите проверенный случай
- Проверьте результат по исходным величинам. Подставьте значения в исходное соотношение или сравните график и числовой ответ, где это уместно.
Для вершин A,B,C,D и ребер AB=2, BC=3, AC=4, CD=1, BD=5, Краскала выбирает CD, AB, BC для общего веса 6. Кратчайший маршрут от A до D — A-B-C-D, также 6, но это равенство случайно. Максимизируйте 3x+2y при x+y≤4, x≤2, x,y≥0: лучшая вершина (2,2), значение 10.
Алгоритмы, сети и линейное программирование
Крускаль выбирает рёбра в порядке возрастания веса, избегая циклов
Сравните модель с разобраным примером и объясните одно изменение.
Найдите вес минимального остовного дерева для примера сети.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Крускаль выбирает рёбра с весами 1,2,3 без циклов, соединяя каждую вершину: всего 6.
Проверьте соблазнительное сокращение
- Дерево охвата не имеет циклов и соединяет все вершины. Самое длинное отдельное ребро не исключается автоматически из каждого оптимального решения. Алгоритм кратчайшего пути не может заменить алгоритм дерева минимального веса.
- Если сокращение приводит к ошибке, определите нарушенное предположение. Сохраняйте точное значение до момента, когда требуется финальное округление.
Кратчайший путь между двумя вершинами должен также являться деревом минимального веса для всей сети. Это утверждение ложно. Объясните, какое определение или допущение оно нарушает.
Найдите максимум выражения 3x+2y для примера допустимой области.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Проверьте допустимые вершины: (2,2) даёт значение 3×2+2×2=10 — наибольшее значение целевой функции.
Кратчайший путь между двумя вершинами также должен быть минимальным остовным деревом всей сети.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Остовное дерево не содержит циклов и соединяет все вершины. Самое длинное ребро не обязательно исключается из каждого оптимального решения. Алгоритм кратчайшего пути не может заменить алгоритм минимального остовного дерева.
Интерпретируйте новую ситуацию
- Для критических путей вычислите ранние и поздние моменты событий и определите активности с нулевой плашкой. Укажите единицы измерения и интерпретируйте оптимальность. В существующем архиве нет пар D1, поэтому эти исходные задачи не формируют базу прошлых экзаменационных вопросов уровня D1.
- Полное решение должно содержать математический результат и объяснение его смысла. Убедитесь, что полученный результат возможен в заданном контексте.
Сколько рёбер имеет остовное дерево на 4 вершинах?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Дерево на n вершинах имеет n-1 рёбер, поэтому четырем вершинам нужно три.
Соотнесите каждый алгоритм с его правилом.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Каждый алгоритм точен для своего класса задач; воспроизведение заявленного правила, включая обработку ничьих, приносит баллы.
Примените это в своем курсе
- edexcel IAL mathematics; официальный модуль D1. Обогащение из других модулей определяется в обзоре охвата; это не является дополнительным требованием для получения баллов.
- Приводите ход решения до финального ответа и соблюдайте правила использования калькулятора и формул, указанные в экзаменационном билете. Проанализируйте неверный ответ, найдя первый недопустимый шаг.
Связанная сеть без циклов, соединяющая каждую вершину с наименьшей возможной суммарной стоимостью рёбер. Выберите соотношение, покажите метод, проверьте его допущения и проинтерпретируйте результат.