Исследование по математике · 10–11 класс

Насколько правило ближайшей точки уступает лучшему маршруту доставки

Предмет
Математика
Тема
Математика вокруг нас
Класс
10–11 класс
Вид работы
Исследование

Идея

Сформулируйте задачу курьера как задачу о кратчайшем обходе точек. Для наборов из 8–10 адресов найдите лучший маршрут полным перебором и сравните его с правилом ехать в ближайшую точку. Выясните, на сколько процентов простое правило длиннее и когда проигрывает сильнее всего.

Исследовательский вопрос

На сколько процентов маршрут, построенный по правилу ближайшей точки, длиннее самого короткого и от чего зависит этот проигрыш?

План работы

  1. Изучите постановку задачи о кратчайшем обходе точек и подсчитайте, как число маршрутов растёт с числом адресов.
  2. Напишите программу или составьте таблицу, которая для набора точек считает длину маршрута по расстояниям между ними.
  3. Найдите лучший маршрут полным перебором для 8–10 точек и маршрут по правилу ближайшей точки.
  4. Сгенерируйте не меньше 50 случайных наборов и для каждого запишите, на сколько процентов правило хуже лучшего маршрута.
  5. Сравните случайное расположение точек с точками, собранными в 2–3 скопления, и постройте гистограмму отклонений.
  6. Опишите, когда простого правила хватает, а когда нужен более точный алгоритм, и ограничения вашей модели.

Что понадобится

Компьютер с Python или электронными таблицами, справочные материалы о задаче коммивояжёра и теории графов, при желании реальная карта района для примера.

Что получится

Программа или таблица с расчётами, гистограмма отклонений для разных расположений точек и вывод о средней и наибольшей потере правила ближайшей точки по сравнению с лучшим маршрутом.

Частые ошибки

  • Сделать вывод по одному набору точек вместо серии случайных наборов
  • Использовать прямые расстояния и не сказать, что по дорогам они другие
  • Забыть, что маршрут должен вернуться в начальную точку, или считать это по-разному
  • Брать слишком много точек для перебора и не дождаться ответа программы

Теги

Тему и план подготовили эксперты фестиваля. Это отправная точка: вопрос, объём опытов и вывод можно менять под себя и вместе с руководителем.

Пишете работу? Пришлём шаблон в Word: все разделы с подсказками, что писать в каждом, и оформление по положению фестиваля.

Похожие работы участников

Все работы школьников по математике

Ещё темы по математике

10–11 класс Исследование

Математическая модель очереди в столовой

Понаблюдайте за очередью в столовой: сколько людей приходит в минуту и сколько обслуживают. Постройте модель и предложите, как сократить время ожидания.

10–11 класс Проект

Модель школьного расписания без накладок на основе раскраски графа

Представьте уроки как вершины графа, а конфликты (один учитель, один класс) как рёбра. Составьте программу или таблицу, которая раскрашивает граф и распределяет уроки по времени без накладок. Проверьте её на упрощённых данных и сравните число занятых уроками слотов с ручным расписанием.

10–11 класс Исследование

Фракталы: бесконечная геометрия природы

Изучите, что такое фракталы, и найдите их в природе: капуста романеско, снежинки, береговые линии. Постройте несколько фракталов в программе и оцените их размерность.

Все темы проектов по математике

Сделали работу по этой теме? Пришлите её на фестиваль

Принимаем исследовательские, проектные и научно-творческие работы учащихся 1–11 классов. Эксперты оценят работу, финалисты защищают её онлайн перед жюри.