Задачка:
Расположить на плоскости 7 несовпадающих точек так, что бы в любой тройке из этих точек нашлась пара точек на расстоянии 1 (сантиметр, если это принципиально) друг от друга.
(задачка не моя, автора не знаю)
Немного истории:
Впервые с задачкой столкнулся в Логосе -- morfey принес с какого-то зачета.
Когда стало понятно, что навскидку коллектив решение не находит, suavik перешел на численные методы, бормоча про suashop, suascript и генетические алгоритмы.
И минут через 20 (ну, примерно...)) мы уже обсуждали, единственное ли это решение.
Решение:
Особи (набор 7 ген): координаты 7 точек
Начальная популяция: 500
Количество потомков: 4000 (2000 скрещиваний)
Кроссинговер: перехлест линейного массива ген в случайном месте
Мутация: случайное приращение случайной координаты случайной точки
Отбор: 400 лучших + 100 худших
Функция отбора (минимакс): квадрат наибольшего среди всех троек отличия от 1 самого близкого к 1 расстояния между парой в тройке
Порог остановки: 0.75
Число поколений: 100
ps:
Численно можно решать по-разному, в частности комбинаторно.
Да и suavik позже признался, что решал градиентным поиском )).
Но мне это кажется красивым примером для входа в тему.
Примечательно, что многие интуитивные отправные идеи "человеческих" поисков
(точки по кругу, треугольник и квадрат, три напротив четырех, ...) прослеживаются в эволюционно устойчивых, но недостаточно точных численных решениях. Можно задуматься о устройстве воображения.
Красивое про эволюционные методы на Unity: Evolution by Keiwan
todo:
Вынести параметры в настройки.
Подобрать параметры (численность популяции, способ кросинговера, величину и число мутаций) и исследовать их влияние на частоту правильных решений, скорость схождения к ним.
Добавить возможность просмотра генеалогии.