О целях хакатона.
У меня в окружении есть несколько человек, которые любят математику и имеют развитое аналитическое и алгоритмическое мышление. Они хотели бы участвовать в создании интересных программных решений, но при этом имеют достаточно ограниченные навыки программрования. А как известно - лучший способ улучшить свои навыки прогаммирования - программировать. Так же участвующие имеют возможность поразвивать свои problem solving skills.
Вот так получилось что я совершенно нечайно организовал для ребят маленький такой хакатон, в котором можно и потренироваться в программировании и столкнуться с базовыми задачами computer science. Впрочем, имея некоторый опыт преподавания, я бы сказал что подобный хакатон мог бы стать отличным для студентов изучающих программирование и основы computer science.
Очень красочная gif-ка, попалась в степях интернета )
Почему кубик рубика?
Итак, кубик рубика. Проблема с которой люди столкнулись давно и для которой найдены вполне хорошие решения. Однако для тренировки - самое оно. Попробовать решить, столкнуться с трудностями, преодолеть их, и параллельно посмотреть, как была решена проблема computer science сообществом, какова была эволюция решений. Потому как тривиальная на первый взгляд задача не так тривиальна как кажется. В чем проблема brute force и даже не совсем brute force решений для рубика? - Как всегда, в экспоненциальной, факториальной, и т.п. сложностях. Но об этом потом.Для интереса, можно почитать статью "Using the Rubik’s cube
to teach problem solving"
Постановка задачи.
План был такой. По скольку проблема решена, нужно сначала самим решить проблему, потом изучить "state of the art", а потом усовершенствовать свои алгоритмы с учетом новых знаний.В общем в одной - двух статьях я расскажу о хронологии хакатона. Кстати, если мне когда то придется кому то помогать в обучении программированию - будет полезно иметь такой материал в виде статьи.
Задачи:
- Смоделировать кубик рубика в памяти
- Реализовать все элементарные операции с кубиком (повороты)
- Реализовать сохранение состояний и операции сравнения состояний
- Подготовить контекст для выполнения (основной скрипт, который создает кубик, перемешивает ему, указывает целевое состояние, например собранный кубик, и вызывает код решающий кубик)
- Визуализировать кубик с состояниями и анимацией в 3d
- Не тратить время на оптимизацию кода по скорости и потреблению памяти, сосредоточиться на вопросе самих алгоритмов решения. (Так что операции и сруктуры в коде окажутся весьма неэкономными, но зато наглядными и понятными)
- Применить несолько подходов к решению кубика алгоритмически, найти хорошее решение.
- Получить кучу фана и потренироваться.
Инструменты
В качестве языка выбрали питон, потому что он наиболее простой и очевидный, и требует минимальных усилий для "борьбы с системой", так как можно не отвлекаться на многие рутинные задачи.
Для визуалиации используем два вывода - распечатка в консоль и отрисовка в 3D с момощью vpython - в ubuntu даже в репозиториях есть.
Хронология
Для начала я на коленке в поезде подготовил слегка монстрообразную структуру данных для представления кубика и сделал заглушки для всех элементарных опреаций, а так же для клонирования самого кубика, примитивные операции сравнения (никаких сравнений по хэш, а простое как двери сравнение всех ячеек "в лоб"). Реализовал заглушку методов перемешивания кубика, печати кубика в консоль в читабельном виде, ну и так далее.
После этого сделал минималистичный скрипт который создает кубик, применяет несколько операций к нему, распечатывая в консоль на каждом этапе. Для копирования кубика использовал весьма жесткую тактику - deepcopy самого объекта, естественно, это медленно, но наиболее поняно для окуржающих. И поскольку это учебный прототип, подходит идеально. В таком виде отдал код ребятам.
class Cube(): __global_visualizer = None def __init__(self, observer = None): ... def __init__fringes(self): ... def rotate(self, direction, is_recursive_call = False): previous_state = self.copy() if not direction in self.directions: print 'Cannot apply unsupported rotation:', direction return False if direction == 'L+': ... self.previous_state = previous_state def is_equal_to(self, cube): ... def randomize(self): ... def print_cube(self): ... def copy(self): ... def get_distance(self, cube): ... def get_color_distance(self, cube): ... def bind_visualizer(self, observer): ...
В общем те, кто уменют читать код, сразу увидят, что ребята получили базовый шаблон для кубик - рубика. Причем в заготовке кубика есть намеки на поддержку данных нужных для решения кубика с помощью A*.
Что осталось сделать тренирующимся:
- Реализовать повороты (заполнить заглушки кодом)
- Визуализировать кубик с состояниями и анимацией в 3d
- написать алгоритм решения кубика
Подход к решению проблемы
Итак, решение кубика удобно рассматривать как путь на графе. Вершины графа - состояния кубика. Из каждой вершины имеем 12 ребер - переходы в соседние состояния посредством прменения элементарных операций (тут уже возможны вариации в зависимости от алгоритма, но в общем идея сохраняется)
Решение в лоб (brute force) очень осложнено тем, что при глубине в 20 шагов мы могли бы иметь 12^20 переходов... Да и ссылаясь на комбинаторное решение из википедии имеем число всех достижимых различных состояний кубика Рубика 3x3x3 равно (8! × 38−1) × (12! × 212−1)/2 = 43 252 003 274 489 856 000. Это число не учитывает то, что ориентация центральных квадратов может быть разной. С учётом ориентации центральных квадратов количество состояний возрастает до 88 580 102 706 155 225 088 000 состояний. Однако при сборке кубика ориентацию центральных квадратов обычно не учитывают, поскольку на большинстве кубиков нет пометок, которые позволяли бы её отслеживать.
Если применять Brute-Force алгоритм на нашей модели, то именно такое (43 252 003 274 489 856 000) количество состояний нужно нужно было бы просчитать, сравнить и т.п. и оно обычно валится по таймауту. В Google вычеслитильные супермощьности позволили ответить на много вопросов относительно этой проблемы, однако мы же хотим находить приемлимые решения в реальном времени... Можно применить A*, но какую эвристику выбрать?
Если применять Brute-Force алгоритм на нашей модели, то именно такое (43 252 003 274 489 856 000) количество состояний нужно нужно было бы просчитать, сравнить и т.п. и оно обычно валится по таймауту. В Google вычеслитильные супермощьности позволили ответить на много вопросов относительно этой проблемы, однако мы же хотим находить приемлимые решения в реальном времени... Можно применить A*, но какую эвристику выбрать?
Конечно, мировое сообщество давно пришло к общему знаменателю и весьма хорошо продвинулось в решении проблемы кубика. Но прежде чем читать это, это, это и так далее, стоит потренироваться в мышлении самим.
Проходящим тренировку предстоит ответить для себя на вопросы:
- Cуществует ли алгоритм поиска оптимального решения с полиномиальным временем?
- Если алгоритм существует, каков он?
- Если не существует, можно ли найти не оптимальное, но достаточно хорошее решение за полиномиальное или хотя бы практически приемлимое время?
- На сколько ваше решение окажется более эффективным чем реализация всем известного человеческого алгоритма (распространяется в виде инструкции к самому кубику), который позволяет очень быстро и совсем неоптимально решить кубик (в общем случае)?
- И вообще узнать многое о кубике рубика, об аглоритмах, графах, problem reduction, problem solving и т. п.
Что дальше?
В результате все конечно было сделано и переделано. Хоть основные вещи ребята реализовали, хакатон пока еще а процессе, так как усовершенствуется визуализация, фиксятся бажки и дорабатывваются решения, так что в специальном репозитории на github потихоньку происходят изменения. Сам я занимаюсь тем, что стараюсь поддерживать код в относительно чистом виде, но идеи про алгоритмы держу при себе, а кое что реализую сам, не распространяя пока.
---обновление---
В новом посте выложено видео по АПИ для кубика, приведу его и тут, для тех, кому в лом заглянуть в английскую статью:
Комментариев нет:
Отправить комментарий