#математика #комбинаторика #оптимизация
#теорияалгоритмов

Комбинаторный взрыв

🧮 Многие из вас рано или поздно встречались или встретитесь с проблемой перебора. Очень часто простые задачи с небольшим количеством данных можно решить, просто перебрав все варианты.

🎒Условно, если вам нужно уложить в два рюкзака три вещи наиболее удачным способом, можно просто всё перепробовать (вариантов немного – всего 8, даже учитывая те, когда используется только один рюкзак), но если рюкзаков хотя бы 5, а вещей хотя бы 20, то количество вариантов для перебора уже достаточно велико. Причем, работая с маленькими величинами, наш мозг отказывается признавать, что в какой-то момент увеличение количества произойдет лавинообразно. И подобную ситуацию в математике называют комбинаторный взрыв.

💥 Комбинаторный взрыв — важное понятие в оптимизации при создании алгоритмов.

🏁 Есть классическая математическая легенда, иллюстрирующая этот взрыв. Когда изобретатель шахмат попросил 1 рисовое зернышко за первую клетку и в два раза больше зернышек за каждую последующую.

🏔 Общее количество риса получается не космическое, но заоблачное. Примерно с гору Эльбрус.

🌺 И когда полный перебор требует подобного количества вариантов, поневоле начинаешь задумываться о каких-то других путях решения. Ровно поэтому, пока для создания «думающих роботов» использовался полный перебор, они сильно уступали человеку и при решении задач, и в том числе при игре в шахматы. Так как человек никогда не делает полный перебор, отбрасывая многие варианты из опыта или по каким-то другим, ему понятным, причинам.

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

По мотивам поста из канала Алексея Тарасова