Школьный образовательный квест по теории графов "Оптимальный маршрут в городе"

Квест "Оптимальный маршрут в городе" ("Оптимизируй город") проводится для школьников 3-4 классов. Цель квеста состоит в том, чтобы привить участникам навыки научного мышления, в игровой форме обучить их основам Теории графов и научить решать комплексные оптимизационные задачи, такие как задача отыскания оптимального маршрута в городе, объединяясь для этого в большие и малые группы. Площадка, на которой проводится квест, представляет собой план большого города, разделённого на кварталы. Цель игры состоит в том, чтобы объединёнными усилиями найти в городе замкнутый маршрут, проходящий через все дома, у которого суммарная стоимость проезда по всем дорогам (улицам) минимальна. Таким образом, ребятам нужно решить задачу коммивояжёра в масштабах целого города.

На первом этапе участники разбиваются на группы по 2-4 человека, за каждой из которых закрепляется определённый квартал города. Задача группы - найти в своём квартале один или несколько оптимальных маршрутов, каждый из которых соединяют какие-то два дома, и проходит через все дома квартала. Группе нужно обойти квартал, следуя одним из таких маршрутов. По мере движения участники получают в каждом доме новые математические задания, от правильного решения которых зависит дальнейшее прохождение маршрута. Когда весь маршрут построен и полностью пройден, в последнем доме квартала участники группы получают специальный пароль и ключ от одной из дверей ратуши, находящейся в центре города. Открыв эту дверь и введя пароль в компьютер, они получают доступ к своей части базы данных, необходимых для успешного решения главной задачи проекта во всём городе. Эти данные содержат информацию о том, какие улицы соединяют исследованный ими квартал с другими кварталами города и какова стоимость проезда по этим улицам.

Теперь наступает второй, решающий этап проекта, во время которого участники из всех групп объединяются, обмениваются полученными данными и совместными усилиями находят в городе оптимальный гамильтонов цикл, содержащий все или некоторые из ранее построенных маршрутов в отдельных кварталах. Решение этой глобальной задачи становится возможным, только если до этого каждая группа полностью обошла свой квартал и правильно нашла оптимальные участки маршрута внутри него, а также получила все необходимые сведения о связях своего квартала с другими кварталами города. Тщательный анализ собранных данных, сопоставление различных вариантов построения обхода и финальный мозговой штурм с участием всех ребят приводят к успешному решению основной задачи проекта.