Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni
🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!06.12.2023
Дев-адвент 6: підбірка ламаної під графік
Результат роботи алгоритму (помаранчевим — підібрана ламана)
Одна з аналітичних функцій, яку я хотів зробити — це автоматичне виявлення динаміки — тобто, чи йде вага вгору, чи вниз, чи залишається на місці. Задача, яка людині здається зрозумілою, алгоритмічно нетривіальна.
Наївний підхід — виділяти проміжки монотонного зростання чи спадання — працює неприйнятно. Особливо в періоди відносно сталої ваги отримаємо проміжки в один-два дні, бо вага буде коливатись то в один бік, то в інший. Взагалі, алгоритм мусить бачити “загальну картину” та ігнорувати маленькі відхилення. При цьому, він також має вірно та чітко знаходити точки, в яких динаміка змінюється на протилежну — навіть якщо з першого погляду ця зміна починається теж з маленьких “відхилень”.
Я знаю багато алгоритмів, що описують навколо графіка криві — всякі сплайни, Безьє і так далі. Але мені то зовсім не потрібно — мені важливі періоди зростання/спадання та крайні точки. Поміркувавши, знайшов гідне рішення.
Побудував алгоритм за методом динамічного програмування. Задача побудови ламаної зводиться до розвʼязку для меншої кількості даних. Для двох позицій даних розвʼязок тривіальний. Далі, для кожної нової позиції i шукаємо таке j<i, щоб відрізки, що складають розвʼязок для позиції j - вже відомий — плюс новий відрізок від j до i мали оптимальну ціну з усіх можливих j. Залишається повторити для i від 2 до N і ламана побудована.
Щоб розвʼязати задачу динамічним програмуванням, потрібно визначити ціну розвʼязка. Я поки зупинився на (i-j)^1.2 * (1 - counter/amount). Тобто з першим множником все ясно — чим довше відрізок, тим краще (ступінь можна підібрати емпірично). А другий множник визначає, наскільки у відрізку багато позицій, що йдуть супротив його напрямку.
🧠 Мозок розімʼяв успішно, одним словом. А головне, що алгоритм працює — дивись ілюстрацію вище.