Дидактические цели
Есть задачи, которые мы не умеем решать, а фургоны всё равно выезжают каждое утро. Лаборатория начинается с задачи коммивояжёра — сколько маршрутов, почему мы даже не умеем проверить, что маршрут лучший, и как ограничить ошибку, — а затем смотрит на пять существ, решающих её варианты так, что ни одна особь не знает задачи целиком: муравьёв, термитов, слизевика, пчёл и рабочих муравейника, делящих работу. Всё измеряется при фиксированном бюджете, относительно границы и классических методов, и результат сообщается, даже если он не льстит существам. Третья часть трилогии об оптимизации после Линейной оптимизации и Эвристической оптимизации. Рассчитана на университет; блоки A и B доступны в старших классах.
Чему учит
- Комбинаторному взрыву в задаче коммивояжёра: (n − 1)!/2 маршрутов, откуда каждый множитель и почему компьютер в тысячу раз быстрее покупает лишь две остановки (залы 1-2).
- Разнице между проверкой маршрута и удостоверением его оптимальности, P против NP, и сделке всей лаборатории: отказу от оптимума ради ответа с ограниченной ошибкой (залы 3-5).
- Эксперименту с двойным мостом на настоящих муравьях, правилу выбора с параметром α, испарению ρ и стигмергии Грассе — общению через среду (залы 6-9).
- Переходу от моста к карте: маршруты вручную, жадный алгоритм и его последний участок, обмен 2-opt и муравьиная колония Дориго со следом и зрением (залы 10-14).
- Настройке колонии при фиксированном бюджете: сколько муравьёв, сколько забывать, сколько весят след и зрение, сколько бродить вначале и кто откладывает след. Для каждой ручки больше — не значит лучше, и ученик это измеряет (залы 15-19).
- Измерению и смешиванию: граница минимального остовного дерева, колония со шлифовкой 2-opt и честный турнир, в котором одна колония проигрывает (залы 20-23).
- Ещё трём механизмам с тем же рецептом: слизевику, проектирующему дешёвые и надёжные сети, пчёлам, распределяющим попытки между вариантами неизвестного качества и решающим кворумом, и муравьям Pheidole, распределяющим работу без начальника с помощью порогов реакции (залы 24-33).
- Тому, что на самом деле даёт децентрализация: не качество, а приспособляемость при изменении задачи и устойчивость к отказам (залы 8, 22, 23, 32, 33 и 34).
Ключевые математические идеи
- При закреплённом складе и одинаковой длине обратного маршрута n точек дают (n − 1)!/2 маршрутов. Факториал растёт так быстро, что 29!/2 ≈ 4,42·10³⁰: при тысяче маршрутов в секунду — десять миллиардов возрастов Вселенной.
- Разрешающая версия задачи коммивояжёра NP-полна, но удостоверить оптимальность ещё труднее. Зато можно ограничить: МОД ≤ оптимум ≤ мой маршрут, потому что без одного участка лучший маршрут становится путём через все точки. Разрыв относительно границы — пессимистичная гарантия.
- Правило выбора P = (c + τ)^α / Σ превращает малые преимущества в большие при α > 1 (нелинейное подкрепление). На карте P ∝ τ^α · η^β сочетает память (след) и зрение (1/расстояние).
- Испарение τ ← (1 − ρ)τ гасит след геометрически (0,9¹⁰ ≈ 0,35). Без затухания выученное каменеет; при избытке ничего не выучивается.
- Все сравнения — при фиксированном бюджете, считаемом в вычислениях расстояний. Без этой валюты больше муравьёв или больше кругов всегда выигрывают, и компромисса не найти.
- Энтропия матрицы феромона показывает, сколько сомнений осталось у колонии: кривая результатов не отличает «медленно» от «мертво», а энтропия отличает.
- Слизевик следует dD/dt = |Q|^μ − D с потоком по законам Кирхгофа: малое μ сохраняет циклы (дорогая надёжная сеть), большое μ приближается к дереву (дёшево и хрупко).
- У дилеммы «исследовать или использовать» (многорукий бандит) всегда два способа провала: решить по слишком малым данным или потратить бюджет на разглядывание.
- Пороги реакции P = s^n / (s^n + θ^n) распределяют работу без начальника; у их разброса есть компромисс (все разом или многие без дела), а если пороги учатся, из одинаковых универсалов выходят специалистки.
- Единственные доказанные гарантии лаборатории — у классических методов: Кристофидес (не более 1,5 оптимума в метрическом случае) и Грэм (жадное правило распределения не хуже 4/3 − 1/(3m)). Существа гарантий не дают; они дают приспособляемость.
Содержание по залам
Зал 1 · Задача из 1832 года
Фургон проезжает по карте города 30 точек доставки в порядке поступления заказов (111 км). Ученик вслепую оценивает важность задачи, затем читает современный и исторический контекст (немецкое пособие 1832 года; Данциг, Фалкерсон и Джонсон, 1954). В конце тот же фургон проезжает лучший известный маршрут: 43 км.
Задания для ученика
- Оценить важность задачи, ничего не прочитав.
- Узнать среди четырёх новых ситуаций ту же задачу в другом обличье.
Зал 2 · Тридцать точек
Оценка вслепую: сколько займёт перебор всех маршрутов через 30 точек, а затем подсчёт самим учеником: 24 перестановки 4 остановок, почему каждый маршрут встречается дважды (по парам километров на 24 миниатюрах со стрелками) и запись 29!/2 (лаборатория понимает факториалы). В конце — лестница времён и главная фраза: компьютер в тысячу раз быстрее покупает лишь две остановки.
Задания для ученика
- Посчитать перестановки 4 остановок.
- Объяснить, почему каждый маршрут встречается дважды.
- Записать число маршрутов при 30 точках.
Зал 3 · Мы даже проверить не умеем
Разделяются проверка маршрута (дёшево) и удостоверение, что он лучший (быстро никто не умеет); вводится P против NP. Задание с маршрутом 460 и границей 430 даёт идею, спасающую задачу на практике: ограничить ошибку, не зная решения.
Задания для ученика
- Отличить «быстрый алгоритм неизвестен» от «его нет».
- Решить, что можно утверждать по маршруту и границе.
Зал 4 · Отказаться от оптимума
Точный рекорд (85 900 городов в 2006 году) против фургона, выезжающего в семь. Задаётся словарь лаборатории: граница, разрыв и anytime-метод, с полосой на реальном примере.
Задания для ученика
- Выбрать, когда стоит платить за точный оптимум.
- Посчитать, во что автопарку обходятся лишние 4%.
Зал 5 · Зачем смотреть на насекомое
Витрина из четырёх анимированных сцен (муравьи со следом, слизевик, плетущий сеть, пчёлы и их танец, термиты, возводящие арку). Что даёт колония, чего нет у написанного человеком алгоритма, и честная оговорка: природа не оптимизирует, а довольствуется. Последний вопрос повторяется в зале 33.
Задания для ученика
- Найти ложное утверждение о природных методах.
- Выбрать, у кого списать метод для трамвайной сети.
Зал 6 · Двойной мост
Эксперимент Госса и Денёбура (1989) с аргентинскими муравьями: ученик предсказывает распределение движения, выпускает 200 муравьёв и видит, как след утолщается на короткой ветви, с живым графиком. Числовое задание о рейсах раскрывает механизм: выбравший короткую ветвь раньше возвращается откладывать след.
Задания для ученика
- Предсказать распределение до выпуска муравьёв.
- Ответить, какой муравей решил идти по короткой ветви.
- Посчитать, сколько капель на короткой ветви приходится на каплю длинной.
Зал 7 · Единственное правило
Правило выбора P = (c+τ)^α / Σ, два расчёта вручную и интерактивная развилка. Затем вторая половина опыта Госса (короткая ветвь открывается поздно) и кривая компромисса по α: при малом α колония не определяется, при большом — замыкается на длинной ветви и не исправляется.
Задания для ученика
- Посчитать вероятность ветви при α = 1 и α = 4.
- Измерить итоговое движение для нескольких α и объяснить крайности.
Зал 8 · Вовремя забыть
Испарение τ ← (1 − ρ)τ и задание с 0,9¹⁰. В середине опыта хорошую ветвь перерезают, и ученик измеряет, сколько муравьёв теряется при каждом ρ: без испарения колония каменеет, при избытке — страдает амнезией. Этот зал оправдывает лабораторию: колония выигрывает приспособляемостью, а не скоростью.
Задания для ученика
- Посчитать, сколько следа останется через 10 шагов.
- Измерить кривую ρ и назвать оба провала.
Зал 9 · Писать на земле
Термиты Грассе (1959) возводят колонны без чертежа: каждый бросает глину, где сильнее пахнет свежей глиной. С запахом вырастают колонны, без него — плоский слой. Определяется стигмергия и выводится рецепт всей лаборатории: подкрепление, затухание и шум.
Задания для ученика
- Ответить, кто решает, где встанет колонна.
- Найти систему, которая не является стигмергией.
- Предсказать, что будет с колонией без шума.
Зал 10 · Сделай сам
Ученик прокладывает маршрут через 12 точек (19 958 400 маршрутов), нажимая на остановки. Нужно меньше 30 км: ни порядок списка, ни жадный алгоритм этого не дают. Фургон проезжает маршрут ученика и лучший, ученик считает свой разрыв. Подсказка после двух попыток, выход открыт после четырёх.
Задания для ученика
- Проложить маршрут короче 30 км.
- Посчитать разрыв своего маршрута относительно оптимума.
Зал 11 · Всегда к ближайшему
Ближайший сосед по шагам, с кандидатами на каждой остановке. В конце дорога домой почти 10 км при среднем участке 2: жадный оставляет себе объедки и выходит на 49% хуже лучшего маршрута.
Задания для ученика
- Вслепую предсказать, насколько хуже будет жадный.
- Посчитать превышение в процентах.
- Объяснить, почему он не может исправить последний участок.
Зал 12 · Распутать пересечения
2-opt Кроэса (1958) вручную: ученик нажимает два пересекающихся участка, и они меняются; если обмен удлиняет маршрут, он отклоняется. С 50 км жадного — ниже 36. Видно, почему обмен смотрит лишь 4 расстояния и почему 2-opt застревает в локальном оптимуме.
Задания для ученика
- Распутывать пересечения, пока не станет меньше 36 км.
- Сказать, сколько расстояний смотрит один обмен.
Зал 13 · Муравей на карте
Правило Дориго (1992): P ∝ τ^α · η^β, след и зрение. После числового задания муравей выбирает остановку за остановкой с веером вероятностей на виду, а ученик меняет α и β.
Задания для ученика
- Посчитать вероятность одного кандидата.
- Объяснить поведение муравья при β = 0 и при α = 0.
Зал 14 · Полный цикл
Построить, отложить, испарить: десять муравьёв на 30 точках за 41 круг. Первые три показаны по муравью; след превращается из клубка в скелет, внизу — кривые разрыва и энтропии. В конце — три снимка следа, которые надо упорядочить во времени.
Задания для ученика
- Посчитать след трёх муравьёв на одном ребре.
- Упорядочить три снимка следа.
Зал 15 · Миллион муравьёв?
Первый зал блока настройки, с фиксированным бюджетом. Ученик предсказывает, считает, сколько кругов помещается, и измеряет кривую числа муравьёв: один подкрепляет шумно, у 160 нет времени учиться, хорошая зона — около дюжины.
Задания для ученика
- Посчитать, сколько кругов помещается в бюджет.
- Измерить кривую и объяснить крайности.
Зал 16 · Сколько длится память
Испарение на карте с двумя кривыми сразу: разрыв и энтропия следа. Три перемешанные колонии (очень малое, здоровое и очень большое ρ), которые надо узнать по графикам.
Задания для ученика
- Измерить кривую ρ.
- Узнать застойную и нерешительную колонию по энтропии.
Зал 17 · Память против зрения
Сетка из 30 колоний (α × β), которые измеряются нажатием и окрашиваются по разрыву. Столбец β = 0 — стена, строка α = 4 хуже строки α = 2.
Задания для ученика
- Найти клетку ниже 6%.
- Объяснить провал β = 0 и большого α.
Зал 18 · Прогулка вначале
Начальный феромон τ₀ в колонии, доверяющей следу (α = 3, β = 1). Каждое измерение показывает, сколько кругов прошли почти случайно: при крошечном τ₀ — ни одного, при огромном — все.
Задания для ученика
- Измерить кривую τ₀.
- Объяснить, почему обе крайности проваливаются.
Зал 19 · Все ли красят?
AS, элитарная и MAX-MIN при трёх бюджетах в таблице. Сюрприз: MMAS худшая при малом бюджете и лучшая при большом, потому что её пол следа поддерживает исследование.
Задания для ученика
- Заполнить столбцы 4000 и 40 000.
- Объяснить, почему победитель зависит от бюджета.
Зал 20 · Пол для оптимума
Минимальное остовное дерево растёт участок за участком под жадным маршрутом и даёт границу: не зная лучшего маршрута, гарантируется, что жадный хуже не более чем на 45%. Хелд–Карп и Кристофидес — в раскрывающемся блоке.
Задания для ученика
- Посчитать гарантированный разрыв относительно границы.
- Решить, что можно утверждать при 3% от границы.
Зал 21 · Муравьи с ножиком
Колония шлифует каждый маршрут 2-opt на 60 точках при фиксированном бюджете. Ученик измеряет, сколько проходов выгодно: шлифовка спасает почти всё, а после некоторого предела съедает круги колонии.
Задания для ученика
- Измерить кривую проходов 2-opt.
- Объяснить пользу шлифовки и вред излишней.
Зал 22 · Турнир
Шесть методов на четырёх картах с одинаковым бюджетом. Одна колония проигрывает 2-opt с перезапусками везде; побеждает колония со шлифовкой, и только на большой карте. Это говорится прямо, а зал 8 объясняет настоящую ценность колонии.
Задания для ученика
- Прочитать турнир по картам.
- Объяснить, зачем колония, если она не выигрывает по мощности.
Зал 23 · Бой
Пять методов соревнуются вживую на 60 точках: вначале только 48 остановок, а в середине бюджета приходят 12 новых заказов. До смены лидирует колония со шлифовкой (0,65%); сразу после выигрывает 2-opt, который чинит маршрут (1,72%), а одна колония проваливается (45%), потому что старый след указывает на маршруты без новых остановок. Память помогает или мешает в зависимости от того, постепенная смена или резкая и объявлена ли она.
Задания для ученика
- Предсказать, кто быстрее оправится.
- Объяснить, почему память колонии мешает после резкой смены.
- Сказать, когда колония оправдывает себя.
Зал 24 · Слизевик в лабиринте
Открывает блок Physarum: дешёвая сеть против сети с циклами, Накагаки (Nature, 2000) и счёт дерева (35 связей) против 630 возможных. Затем слизевик заполняет лабиринт и оставляет лишь 23 участка кратчайшего пути; без атрофии ничего не отсекается.
Задания для ученика
- Посчитать связи дерева и возможные связи.
- Объяснить, что будет без атрофии.
Зал 25 · Сеть Токио
Овсяные хлопья на 36 городах вокруг Токио и слизевик, плетущий сеть (Теро и др., Science 2010). Одним параметром μ ученик ищет сеть не дороже двух минимальных деревьев, которую почти не разрывает ни один обрыв.
Задания для ученика
- Найти μ с приемлемыми стоимостью и хрупкостью.
- Объяснить, почему минимального дерева мало.
Зал 26 · Тот же рецепт, другая кухня
Двойной мост из трубок слизевика (остаётся короткая ветвь), таблица «муравьи против слизевика» по ингредиентам и какое существо копировать для какой задачи.
Задания для ученика
- Назвать затухание у слизевика.
- Выбрать механизм для оптоволоконной сети и для маршрута сбора.
Зал 27 · Исследовать или использовать
Дилемма бандита (Роббинс, 1952; Чарнов, 1976) в A/B-тестах, клинических испытаниях и соцсетях. Пчела с 300 визитами и пятью цветками: ученик измеряет, сколько проб на цветок выгодно перед выбором.
Задания для ученика
- Посчитать, сколько визитов останется после разведки.
- Измерить кривую и объяснить крайности.
Зал 28 · Танец
Фон Фриш и виляющий танец; завербованные за круг танца. Эксперимент Сили (1991): две кормушки меняются в середине. При слишком большом коэффициенте вербовки улей остаётся у кормушки, которая уже не хороша.
Задания для ученика
- Посчитать последовательниц танца.
- Измерить кривую коэффициента и объяснить блокировку.
Зал 29 · Выбор жилья
Рой выбирает дупло кворумом (Сили, Honeybee Democracy). Низкий кворум решает быстро и ошибается; высокий — верно, но поздно. Ученик измеряет ценность решения для нескольких кворумов.
Задания для ученика
- Измерить кривую кворума.
- Объяснить оба провала.
Зал 30 · Распределить работу
Makespan для 7 операций и 3 операционных: ученик распределяет их на диаграмме Ганта, пока всё не закончится за 9 часов. Жадное правило Грэма (1969) даёт 11 — ровно худший случай его гарантии 4/3 − 1/(3m).
Задания для ученика
- Найти распределение, заканчивающееся за 9 часов.
- Посчитать, насколько хуже жадное правило.
Зал 31 · У каждой свой порог
Пороги реакции P = s^n/(s^n+θ^n) в колонии из 100 рабочих. При одинаковых порогах колония работает рывками; при большом разбросе часть не работает никогда. Ученик ищет середину.
Задания для ученика
- Посчитать, сколько рабочих возьмутся при данном стимуле.
- Найти разброс, удовлетворяющий обоим условиям.
Зал 32 · Учиться делая
Пороги, снижающиеся с практикой: из 100 одинаковых универсалов выходят специалистки (гистограмма с двумя горбами). Если специалисток убрать, их место займут остальные без переназначения.
Задания для ученика
- Посчитать порог после 10 шагов практики.
- Объяснить, кто решает специализацию.
Зал 33 · Когда задача меняется
Точный план, план с пересчётом каждые 100 шагов и колония с порогами перед спросом, который без предупреждения меняется местами. До смены выигрывает план, со сменой — колония.
Задания для ученика
- Сказать, кто выигрывает до и после смены.
- Выбрать, когда уместна каждая политика.
Зал 34 · Испытательный стенд
Свободная площадка без заданий: создаётся карта из 6–40 точек (до 13 — с точным оптимумом), и можно выпускать муравьёв, слизевика или пчёл, видя все параметры. Каждый запуск плавно анимируется и сохраняется на диаграмме следа на той же карте; кнопка «ещё 100» показывает медиану. Порогов здесь нет намеренно: они делят работу, а не строят маршруты и сети.
Задания для ученика
- Испытать три метода на одной карте и сравнить результаты.
- Менять параметры и смотреть по диаграмме следа, меняется ли медиана.
Зал 35 · Никто не выигрывает везде
Таблица рецепта для пяти механизмов с одной пустой клеткой, какую задачу решает каждый, снова вопрос зала 5 (с напоминанием, что выбрал ученик) и честный финал трилогии.
Задания для ученика
- Дополнить рецепт пчёл.
- Снова ответить на вопрос зала 5.
Залы для показа
Самые наглядные для показа и обсуждения в классе.