1. Постановка задачи
Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.
Читать полностью »
Рубрика «алгоритм» - 12
Поиск гамильтонова цикла в большом графе (задача коммивояжера)
2012-11-24 в 15:00, admin, рубрики: c++, алгоритм, гамильтонов цикл, Программирование, метки: c++, алгоритм, гамильтонов циклПоиск пути: алгоритм для новичков
2012-11-20 в 8:06, admin, рубрики: javascript, jquery, алгоритм, логика, поиск пути, метки: javascript, jquery, алгоритм, логика, поиск путиПоиск пути — неотъемлемая часть игр, встречающаяся в большинстве современных игровых жанров. Наиболее часто задача поиска пути возникает в стратегиях, в которых игрок дает команды игровым юнитам двигаться через область карты, которая содержит препятствия. Игры постоянно усложняются, а поиск пути эволюционирует и развивается вместе с ними.
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), данная статья основана на данном алгоритме и содержит реализацию на JavaScript.
Читать полностью »
Инкрементальный алгоритм привязки GPS-трека к дорожному графу
2012-11-08 в 12:32, admin, рубрики: gps, алгоритм, Блог компании Mail.Ru Group, Геоинформационные сервисы, метки: gps, алгоритм 
Геоинформационные системы постепенно входят в повседневный быт.
Большинство мобильных устройств снабжены GPS/ГЛОНАСС-приёмниками. Это позволяет разработчикам получать записи пути своих пользователей (треки). Треки можно использовать для решения целого ряда задач — от навигации по карте и информирования о местоположении друзей до построения пробок и предсказания дорожной ситуации.
К сожалению, без дополнительной обработки трек пользователя малоинформативен, поэтому требуется этап связи внешних данных и внутренней карты приложения. Для этого существуют специальные алгоритмы привязки данных (map matching algorithms).
Эта статья посвящена алгоритму привязки трека к дорожному графу и результатам его применения в проекте Карты@Mail.ru.
Читать полностью »
Алгоритм обратного распространения ошибки с регуляризацией на c#
2012-10-15 в 11:39, admin, рубрики: .net, data mining, алгоритм, искусственный интеллект, нейронные сети, обратное распространение ошибки, регуляризация, метки: c++, алгоритм, искусственный интеллект, нейронные сети, обратное распространение ошибки, регуляризацияПривет. Я хочу продолжить тему реализации методов машинного обучения на c#, и в этой статье я расскажу про алгоритм обратного распространения ошибки для обучения нейронной сети прямого распространения, а также приведу его реализацию на языке C#. Особенность данной реализации в том, что реализация алгоритма абстрагирована от реализаций целевой функции (той, которую нейросеть пытается минимизировать) и функции активации нейронов. В итоге получится некий конструктор, с помощью которого можно поиграться с различными параметрами сети и алгоритма обучения, посмотреть и сравнить результат. Предполагается, что вы уже знакомы с тем, что такое искусственная нейросеть (если нет, то настоятельно рекомендую для начала изучить википедию или одну из подобных статей). Интересно? Лезем под кат.
Алгоритмизация творчества: можно ли создать интересную рекламу без креатива?
2012-10-15 в 5:16, admin, рубрики: алгоритм, Алгоритмы, искусственный интеллект, творчество, Учебный процесс в IT, метки: алгоритм, творчество 
Предвидя негодование по поводу использования слова «креатив», спешу заметить, что в контексте этой статьи трудно использовать синоним. Честно.
Основная мысль — алгоритмизировать можно абсолютно любой мозговой процесс. Я взял рекламу в качестве примера для доказательства потому, что:
- Понять и оценить интересную рекламу может каждый человек;
- Реклама сильно завязана на творчестве и нестандартном мышлении, которое обычно представляется хаотичным и слабо поддающимся алгоритмизации;
- Я просто очень сильно люблю рекламу. И алгоритмы.
Перед тем, как начать, было бы нечестным не упомянуть о том, что в алгоритме все же есть небольшие хитрости. Понявшему их — плюсов в карму. Итак.
Читать полностью »
Нужно отправить SMS, что может быть «проще»?
2012-10-04 в 7:11, admin, рубрики: Apache, CAMEL, sms, алгоритм, Алгоритмы, Веб-разработка, разработка, рассылки, метки: apache, camel, sms, алгоритм, рассылкиНаконец, в вашем проекте потребовалось организовать рассылку SMS с помощью какой-нибудь службы, работающей через Интернет.
На первый взгляд ничего сложного:
Алгоритм Диффи — Хеллмана
2012-09-17 в 9:39, admin, рубрики: алгоритм, Алгоритмы, дискретный логарифм, криптография, математика, простые числа, шифрование, метки: алгоритм, дискретный логарифм, криптография, математика, простые числа, шифрованиеОдна из фундаментальных проблем криптографии – безопасное общение по прослушиваемому каналу. Сообщения нужно зашифровывать и расшифровывать, но для этого обеим сторонам нужно иметь общий ключ. Если этот ключ передавать по тому же каналу, то прослушивающая сторона тоже получит его, и смысл шифрования исчезнет.
Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью Читать полностью »
Эвристика случайного поиска и теплоходы
2012-08-18 в 17:12, admin, рубрики: алгоритм, Алгоритмы, эвристика, метки: алгоритм, эвристикаКогда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.Читать полностью »
СуперБан — что за зверь, и как с ним бороться
2012-08-14 в 20:46, admin, рубрики: алгоритм, Алгоритмы, скриптВ статье рассматривается так называемый «супербан», в отличии от обычных методов бана, таких как бан по IP-адресу, по нику или по кукам, «супербан» блокирует пользователя по индивидуальным характеристикам его машины.Читать полностью »
Минимакс на примере игры в зайца и волков
2012-06-21 в 22:56, admin, рубрики: алгоритм, Алгоритмы, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, Программирование, теория игр, метки: алгоритм, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, теория игр 
Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.Читать полностью »