Метка «динамическое программирование»

Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.

# Весь код в статье написан на языке Python

Основы

Пожалуй, лучшее описание динамики в одно предложение, которое я когда либо слышал:

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Читать полностью »

Одним из главных преимуществ фреймворков является их предопределённая архитектура. Открываешь незнакомый проект и сразу знаешь, где и как искать код связи с БД, или HTML, или схему url. Кроме того, она позволяет разработчику не задумываться над структурой хранения кода и при этом быть уверенным, что проект будет выглядеть более менее адекватно. Но хочу рассказать о случае, когда реализация MVC в Django, а именно распределение логики по файлам models, forms, views, templates оказалась неудобной и какую на её основе построили альтернативу.

Встала у нас задача сделать движок для статистической отчетности на Django. Мы создали селекторы для получения данных из Oracle и виджеты для отображения этих данных в виде таблиц или графиков (с помощью HighChart). Но это всё чисто технологические решения, без особой магии. Если появятся интересующиеся, расскажу в отдельном посте. А сейчас хотелось бы обратить внимание на более необычную часть проекта. На предоставление составителям отчетов удобного способа эти отчеты составлять.
Читать полностью »

Раз уж неделя «Морского боя» на Хабре продолжается, добавлю и я свои два цента.
При попытке найти оптимальную стратегию для игры за компьютер довольно быстро приходим к такому приближению:

Допустим, что состояние некоторых клеток нам уже известно, и мы хотим сделать ход, максимально приближающий нас к победе. В таком случае имеет смысл выбирать клетку, которая занята кораблём противника в наибольшем числе возможных размещений кораблей, не противоречащих имеющейся информации

В самом деле. Если возможная конфигурация только одна, то мы заканчиваем игру за один ход, расстреливая его корабли по очереди (ведь конфигурация нам известна!) Если же конфигураций больше, то нам нужно уменьшить их число как можно сильнее, тем самым увеличив имеющееся у нас количество информации. Если мы попадём в корабль, то ничего не потеряем (ведь ход остаётся у нас!), а если промахнёмся — то число оставшихся комбинаций будет минимальным из возможных после этого хода.

Снова «Морской бой». Считаем число возможных расположений кораблей
Понятно, что это только приближение к отпимальной стратегии. Если противник будет знать о нашем плане, он постарается разместить корабли так, чтобы они не попадали в те клетки, куда мы будем стрелять в начале игры. Правда, ему это поможет мало — мы всё равно в конце концом зажмём его в угол — но возможно, что определённая гибкость нам не помешала бы. Кроме того, не исключено, что продуманная серия ходов, первый из которых не является оптимальным, привела бы к лучшему результату. Но не будем пока усложнять и без того сложную задачу, а попытаемся просчитать все конфигурации и построить карту вероятности заполнения поля.

На первый взгляд, задача кажется неподъёмной. Число конфигураций представляется порядка 1020 (на самом деле их несколько меньше — ближе к 1015), так что на полный перебор времени уйдёт слишком много. Перебирать раскраски поля и оставлять только допустимые — не лучше: всё равно нам каждую комбинацию придётся просмотреть.

Что же ещё попробовать? Любой олимпиадник тут же ответит — динамическое программирование. Но как его организовать?

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js