Многие, наверное, пытались найти построение дерева общего вида, но поисковик находил только бинарные… Двоичное дерево поиска, обход двоичного дерева и могие другие алгоритмы.
Да, действительно, дерево общего вида нигде не используется, обход медленный, варианты использования небольшие.
Так вот, я задался этим вопросом и теперь поясню как все-таки дерево строится. Итак, в идеале структура дерева общего вида должна хранить три переменные:
Читать полностью »
Недавно искал алгоритм для расчета всех мультимножеств из заданного множества. Мультимножество удовлетворяет условию — сумма равна заданному числу. На самом деле нужно было перебрать все варианты периода времени от нескольких дней до недели, при условии, что весь период разбит на отрезки времени длиной в несколько часов (например 5,6, и 7).
Читать полностью »
Здравствуй. Во время похождения по итернетам в поисках годного алгоритма на эту тему я увидел одну интересную идею, которую на досуге развил и дополнил. Наверное, каждый более-менее опытный кодер встречал типовую задачу на пресечение нескольких прямоугольников в системе координат. Насколько я понял, вопрос годного алгоритма остается открытым, а потому я решил предложить свой.
Читать полностью »
При разработке ПО часто возникают интересные задачи. Одна из таких: работа с гео-координатами пользователей. Если вашим сервисом пользуются миллионы пользователей и запросы к РСУБД происходят часто, то выбор алгоритма играет важную роль. О том как оптимально обрабатывать большое количество запросов и искать ближайшие гео-позиции рассказано под катом.
Так уж получилось, что моим первым более-менее серьёзным проектом, связанным с программированием, была реализация шашек для «Шага в будущее». К несчастью, доделать его до конца у меня так и не получилось, так как через некоторое время концепция проекта резко поменялась. Несмотря на это, программа была практически готова и с ней даже можно было играть, к тому же сам процесс её написания оказался весьма интересным, поэтому я решил поделиться теми идеями и алгоритмами, которые сумел придумать.
Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.
Работа уникальная, в своём роде, потому что в этом случае графическое отображение особенно сложно сделать: ведь, по сути, нет данных для анализа. «Но алгоритмы также демонстрируют, что визуализация — это больше, чем просто инструмент для поиска закономерностей среди данных, — пишет Майк Босток. — Визуализация использует зрительную систему человека, чтобы расширить человеческий интеллект: с её помощью мы лучше понимаем важные абстрактные процессы и, надеюсь, другие вещи тоже».
Проще говоря, зрение помогает нам думать.
Читать полностью »
Немного история, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми снимался он, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).
А теперь давайте поговорим о том как это игру можно представить и как можно вычислить число Бейкона при помощи графа.
Читать полностью »
Думаю все заметили, что сейчас стало появляться множество всяких бродилок с выживанием в стиле Minecraft. Сделать такую решился и я. Начало было лёгким — Unity3d имеет огромный функционал для сознания простеньких игр (и не только). Персонаж, игровые объекты, в общем основу сделать быстро. Но какой minecraft без рандомно генерируемого мира? Это стало первой трудной задачей. И думаю не только для меня. Просмотрев весь гугл и потратив кучу времени на эту бесполезную вещь я решил написать эту статью дабы сократить страдания других.Читать полностью »
Первая мысль, которая посещает голову человека, столкнувшегося с проблемой планирования — это придумать собственную умную эвристику решения задачи маршрутизации.
Ну, ведь и правда. Пришел заказчик (а чаще привели), описал свою задачу, свои специфичные для бизнеса условия. Тут же приходит мысль, как решать именно его задачу, бороться с проблемами его бизнеса. В итоге анализ его данных и условий рождает собственный эвристический алгоритм, заточенный на эти условия.
Бывает и наоборот, сначала посетила мысль об умной эвристике, а уже потом нашли заказчика или нишу бизнеса, где этим алгоритмом решается задача.
Читать полностью »
В этом году в московском офисе Яндекса пройдёт юбилейная 25-я конференция Combinatorial Pattern Matching — главное в мире событие в области алгоритмов на строках.
Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:
