Сортировка, упаковка и сетевые алгоритмы
Введено| English | Значение |
|---|---|
| algorithm/ˈælɡərɪθəm/ | алгоритм |
Является ли быстрый метод упаковки всегда оптимальным?
- Метод упаковки быстро заполняет коробки, но быстрое допустимое расположение не обязательно использует наименьшее количество коробок.
- Этот урок посвящён алгоритму: конечному набору упорядоченных инструкций, решающих определённый класс задач.
Выберите математическую структуру
- Точно проследите названный алгоритм, включая правила при равенстве (tie rules). При упаковке методом первого подходящего места (first-fit) каждый предмет помещается в первую доступную корзину, способную его вместить. Метод first-fit decreasing сортирует предметы перед применением first-fit. Эвристический метод может быть допустимым, но не оптимальным.
- Укажите допустимые входные данные и единицы измерения перед вычислением. Уравнение должно отражать зависимость, а не просто фиксировать ввод в калькулятор.
Алгоритм первого подходящего (First-fit) использовал 2 ящиков для 6,5,4,3,2 при ёмкости 10, совпадая с нижней границей. Что можно заключить?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Совпадение с нижней границей доказывает оптимальность только для данного случая. Успех эвристического метода на одном примере ничего не говорит о худших случаях — другие списки предметов могут привести к тому, что First-fit превысит нижнюю границу.
Разберите проверенный случай
- Проверьте результат по исходным величинам. Подставьте значения в исходное соотношение или сравните график и числовой ответ, где это уместно.
При ёмкости корзины 10 и предметах 6,5,4,3,2 в указанном порядке метод first-fit размещает 6 и 4 в корзину 1, затем 5,3,2 в корзину 2. Используется 2 корзин. Общая сумма составляет 20, поэтому нижняя граница равна ceil(20/10)=2; данное решение является оптимальным для данного примера.
Сортировка, упаковка и сетевые алгоритмы
Тщательно проследите указанный алгоритм, включая правила разрешения ничьих
Сравните модель с разобраным примером и объясните одно изменение.
Сколько контейнеров использует решенный пример метода первого подходящего (first-fit)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Распределение методом первого подходящего заполняет два контейнера, каждый суммарным размером 10.
Проверьте соблазнительное сокращение
- Пример успешного решения не доказывает, что эвристический метод всегда является оптимальным. Сохраняйте промежуточные списки в трассировке сортировки; не переходите сразу от входных данных к отсортированному финальному списку. Обновление кратчайшего пути должно сохранять информацию о предшественнике, если требуется восстановить маршрут.
- Если сокращение приводит к ошибке, определите нарушенное предположение. Сохраняйте точное значение до момента, когда требуется финальное округление.
Эвристический метод упаковки, хорошо работающий на одном примере, всегда является оптимальным. Это утверждение неверно. Объясните, какое определение или допущение оно нарушает.
Найдите нижнюю границу количества контейнеров для общего размера 20 и вместимости 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
В каждом контейнере помещается не более 10, поэтому требуется минимум ⌈20 / 10⌉ = 2 контейнеров.
Эвристический метод упаковки, хорошо работающий на одном примере, обязательно является оптимальным.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Пример успеха не доказывает, что эвристика всегда оптимальна. Сохраняйте промежуточные списки при отслеживании работы алгоритма сортировки; не переходите напрямую от входных данных к отсортированному финальному списку. Обновление кратчайшего пути должно сохранять информацию о предшественнике, если требуется восстановить маршрут.
Интерпретируйте новую ситуацию
- Для алгоритма Дейкстры выбирайте наименьший неутвержденный предварительный метку и обновляйте её соседей. В задачах об инспектировании маршрутов различайте замкнутый и разомкнутый маршруты и определяйте вершины нечетной степени перед их попарным соединением.
- Полное решение должно содержать математический результат и объяснение его смысла. Убедитесь, что полученный результат возможен в заданном контексте.
Найдите оставшееся свободное место в контейнере, содержащем элементы 5,3,2, при вместимости 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Нерасходный объем = 10 - (5 + 3 + 2) = 0.
Соотнесите каждое правило упаковки с его действием.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Выполняйте алгоритм точно так, как он определён; нижняя граница оценивает, насколько хорошо вообще может быть выполнена упаковка.
Примените это в своем курсе
- Edexcel IAL Further Mathematics; официальный модуль D1. Обогащение другими модулями определяется в обзоре содержания; это не является дополнительным требованием по начислению баллов.
- Приводите ход решения до финального ответа и соблюдайте правила использования калькулятора и формул, указанные в экзаменационном билете. Проанализируйте неверный ответ, найдя первый недопустимый шаг.
Конечное упорядоченное множество инструкций, решающих определенный класс задач. Установите связь, покажите метод, проверьте его допущения и интерпретируйте результат.