Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.Читать полностью »
Рубрика «алгоритм» - 13
Эвристика случайного поиска и теплоходы
2012-08-18 в 17:12, admin, рубрики: алгоритм, Алгоритмы, эвристика, метки: алгоритм, эвристикаСуперБан — что за зверь, и как с ним бороться
2012-08-14 в 20:46, admin, рубрики: алгоритм, Алгоритмы, скриптВ статье рассматривается так называемый «супербан», в отличии от обычных методов бана, таких как бан по IP-адресу, по нику или по кукам, «супербан» блокирует пользователя по индивидуальным характеристикам его машины.Читать полностью »
Минимакс на примере игры в зайца и волков
2012-06-21 в 22:56, admin, рубрики: алгоритм, Алгоритмы, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, Программирование, теория игр, метки: алгоритм, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, теория игр Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.Читать полностью »
Алгоритм моделирования многомерного массива данных, распределенных по нормальному закону
2012-06-06 в 7:38, admin, рубрики: c++, алгоритм, Алгоритмы, математическая статистика, Программирование, метки: c++, алгоритм, математическая статистикаПри разработке или исследовании готовых алгоритмов часто требуется определить качество их работы. Использовать для этой цели данные из реальных источников не всегда возможно, так как их свойства зачастую неизвестны и потому нельзя спрогнозировать результат выполнения исследуемых алгоритмов. В таком случае применяется моделирование данных по одному из хорошо известных законов распределения. Применяя исследуемый алгоритм к модельным данным, можно заранее предположить, каким окажется результат его выполнения. Если он окажется удовлетворительным, можно попробовать применить его и к реальным данным. Естественно, что это относится только к непараметрическим алгоритмам, то есть не зависящим от закона распределения данных.
Чаще всего используется моделирование данных, распределённых по нормальному закону. К сожалению, MS Excel и распространённые статистические пакетаы (SPSS, Statistica) позволяют моделировать только одномерные статистические распределения. Конечно, можно составить многомерное распределение из нескольких одномерных, но только в том случае, если переменные независимы. Если же нужно исследовать данные с зависящими друг от друга переменными, придётся писать программу.
Читать полностью »
Обход бинарных деревьев: рекурсия, итерации и указатель на родителя
2012-06-05 в 7:10, admin, рубрики: java, алгоритм, Алгоритмы, Программирование, метки: java, алгоритм Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Читать полностью »
О подходах к сравнению версий файлов
2012-04-24 в 4:45, admin, рубрики: алгоритм, Алгоритмы, контроль версий, оптимизация, Программирование, разработка, расстояние Левенштейна, сравнение, сравнение файлов, хэширование, метки: алгоритм, Алгоритмы, контроль версий, оптимизация, расстояние Левенштейна, сравнение, сравнение файлов, хэширование Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
Читать полностью »
Анализ альтернативного представления данных в задачах защиты информации
2012-04-16 в 12:23, admin, рубрики: алгоритм, Алгоритмы, криптография, метки: алгоритм, криптографияВ данной статье рассмотрены методы создания криптографических алгоритмов на основе SP-сетей. Приведены требования к криптографическим алгоритмам. Предложен метод для блочного шифрования данных на основе геометрического представления данных.
Оптимальный способ запоминания цифр
2012-04-16 в 7:08, admin, рубрики: алгоритм, запоминание, запоминание информации, Учебный процесс в IT, Цифры, метки: алгоритм, запоминание, запоминание информации, ЦифрыИтак, начнем.
Ежедневно людям приходится запоминать большое количество информации. При этом одни типы данных запоминаются легко, другие — сложно. Так мы без труда можем запомнить известное нам слово, состоящее из большого количества букв, но сталкиваемся с трудностями, если буквы не образуют слово. Подобная проблема возникает и при запоминании цифр, так как это абстрактная информация.
Читать полностью »
Код Хэмминга. Пример работы алгоритма
2012-03-26 в 12:12, admin, рубрики: алгоритм, Алгоритмы, Восстановление данных, код, пример, хэмминг, метки: алгоритм, код, пример, хэммингВступление.
Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Читать полностью »
Алгоритмы / [Из песочницы] Алгоритм Ляна-Кнута для расстановки мягких переносов
2012-02-13 в 9:38, admin, рубрики: c plus plus, c++, алгоритм, кнут, метки: c plus plus, c++, алгоритм, кнут
При работе с текстом часто возникает потребность корректно расставить переносы. Задача на первый взгляд не такая уж очевидная, нужно учитывать особенности каждого языка, чтобы решить, в каком месте разорвать слово. Как правильно формализовать такие требования, и как потом применить их в алгоритме? Одно из самых распространенных на сей день решений предложил Франклин Марк Лян, студент известного профессора Дональда Кнута. Алгоритм так и называется – «Алгоритм Ляна-Кнута», он применяется в издательской системе TeX, автор которой опять же Д. Кнут.
Алгоритм основан на сравнении исходного слова с набором правил (шаблонов). Чем большеЧитать полностью »