Исследование по математике · 10–11 класс
Насколько правило ближайшей точки уступает лучшему маршруту доставки
- Предмет
- Математика
- Тема
- Математика вокруг нас
- Класс
- 10–11 класс
- Вид работы
- Исследование
Идея
Сформулируйте задачу курьера как задачу о кратчайшем обходе точек. Для наборов из 8–10 адресов найдите лучший маршрут полным перебором и сравните его с правилом ехать в ближайшую точку. Выясните, на сколько процентов простое правило длиннее и когда проигрывает сильнее всего.
На сколько процентов маршрут, построенный по правилу ближайшей точки, длиннее самого короткого и от чего зависит этот проигрыш?
План работы
- Изучите постановку задачи о кратчайшем обходе точек и подсчитайте, как число маршрутов растёт с числом адресов.
- Напишите программу или составьте таблицу, которая для набора точек считает длину маршрута по расстояниям между ними.
- Найдите лучший маршрут полным перебором для 8–10 точек и маршрут по правилу ближайшей точки.
- Сгенерируйте не меньше 50 случайных наборов и для каждого запишите, на сколько процентов правило хуже лучшего маршрута.
- Сравните случайное расположение точек с точками, собранными в 2–3 скопления, и постройте гистограмму отклонений.
- Опишите, когда простого правила хватает, а когда нужен более точный алгоритм, и ограничения вашей модели.
Что понадобится
Компьютер с Python или электронными таблицами, справочные материалы о задаче коммивояжёра и теории графов, при желании реальная карта района для примера.
Что получится
Программа или таблица с расчётами, гистограмма отклонений для разных расположений точек и вывод о средней и наибольшей потере правила ближайшей точки по сравнению с лучшим маршрутом.
Частые ошибки
- Сделать вывод по одному набору точек вместо серии случайных наборов
- Использовать прямые расстояния и не сказать, что по дорогам они другие
- Забыть, что маршрут должен вернуться в начальную точку, или считать это по-разному
- Брать слишком много точек для перебора и не дождаться ответа программы
Теги
Тему и план подготовили эксперты фестиваля. Это отправная точка: вопрос, объём опытов и вывод можно менять под себя и вместе с руководителем.