Лично я могу по пальцам пересчитать случаи, когда я задумывался о применении каких-либо специализированных алгоритмов для софта, который я писал на работе.
Первое, что приходит в голову – задача выдачи денег в банкомате.
Клиент хочет сумму X, и в банкомате есть купюры нескольких номиналов. Если выбранная целевая функция – минимизировать количество выдаваемых купюр, то задача сводится к распространённой задаче выдачи сдачи и решается за O(N^2).
Но чаще выбирают иную целевую функцию – максимизировать интервалы между инкассациями. Для этого надо выдавать купюры так, чтобы их расход из каждой кассете был равномерный. Тут уже задачу надо решать в общем виде как оптимизационную задачу целочисленного программирования. Есть целевая функция, есть ограничения, и задача решается обычно какими-либо около переборными методами с различными эвристиками.
Но увы – данную задачу для банкомата при реальных ограничениях проще решать в лоб, перебором. Хотелось бы применить что-то интересное, но заканчиваем банальным брутфорсом.
Ещё мне приходилось реализовывать простейшие примитивы для рисования фигур на плоскости. Например, есть интересный алгоритм Брезенхэма, которым можно рисовать линии без применения вещественной арифметики (и тем более без всяких синусов и косинусов).
И увы, мой список на этом заканчивается.
А какие прикольные алгоритмы приходилось в реальной работе использовать вам?
Сообщения
Комментариев нет:
Отправить комментарий