Метка «графы»

в 9:27, , рубрики: Алгоритмы, графы, метки: ,

Число Бейкона

Немного история, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми снимался он, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).

А теперь давайте поговорим о том как это игру можно представить и как можно вычислить число Бейкона при помощи графа.
Читать полностью »

в 17:18, , рубрики: Алгоритмы, графы, метки: ,

Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат. Читать полностью »

в 16:33, , рубрики: framework, Node, python, Simulink, Visio, wxpython, графы, интерфейс, интерфейсы, нодовый интерфейс, Программирование, метки: , , , , , , , ,

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

В прошлой части я рассказал о задаче и начал описывать процесс реализации, а точнее рендеринг объектов. Теперь же пришла пора реализовать взаимодействие с пользователем.

Часть 1: Учимся рисовать

Кому интересно, добро пожаловать под кат…
Читать полностью »

в 15:46, , рубрики: framework, python, Simulink, UI, Visio, wxpython, графы, интерфейс, интерфейсы, Программирование, метки: , , , , , ,

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

А начиналось все так: понадобилось мне для одного проекта сделать UI, где надо последовательность обработки сообщений редактировать. Что-то наподобии Simulink'а. Соответственно, полез искать готовые либы/фреймворки. Поначалу подумал, что задачка популярная и кто-нибудь уже сделал это велосипед, поискал, поискал и… не нашел. Точнее нашел много антикварных велосипедов, но кто же будет пользоваться чужим старым велосипедом, если можно сделать свой новый. Но раз уж делать новый велосипед, почему бы не сделать его универсальным, мало ли, где еще пригодится.

Так что попробую в нескольких статья описать процесс разработки с нуля до работающего примера. Ну и чтобы было интересно, а ферймворк был универсален, первая задача для него будет не подобие Simulink'а, а софтина для рисования блок-схем а-ля Visio, но со своим блек-джеком и остальными участниками:)

Кому интересно, добро пожаловать под кат…
Читать полностью »

в 20:51, , рубрики: Алгоритмы, графы, метки: ,

Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлоеВ предыдущих частях цикла мы рассмотрели алгоритмы DFS и BFS, позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.
Читать полностью »

в 14:08, , рубрики: bfs, Алгоритмы, графы, метки: , ,

Добрый день, уважаемыее!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.
Читать полностью »

в 21:19, , рубрики: bfs, Алгоритмы, графы, метки: , ,

В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
Читать полностью »

в 19:07, , рубрики: dfs, Алгоритмы, графы, метки: , ,

В этой статье хотелось бы рассказать об одном из самых распространенных алгоритмов на графах — об обходе в глубину — на примере решения задачи о нахождении пути сквозь лабиринт. Всем, кому это интересно — добро пожаловать под кат!
Графы для самых маленьких: DFS
Читать полностью »

в 8:49, , рубрики: bfs, dfs, Алгоритмы, графы, метки: , ,

Многие объекты окружающей действительности могут быть смоделированы с использованием графов: карта метро, лабиринт, знакомства в соцсетях, возможные ходы в настольной игре — все это графы. Самое простое и частое действие, которое можно сделать с графом — это перебрать его вершины в каком-то порядке. Под катом я бы хотел рассказать про два самых известных алгоритма на графах — об обходах в глубину и в ширину.

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

в 9:24, , рубрики: Алгоритмы, биоинформатика, генетика, геномика, геномы, графы, поисковые системы, происхождение видов, эволюция, метки: , , , , , ,

Думаю многие ИТ-специалисты интересуются не только программированием, но и вопросами более земными и частенько их можно застать рассуждающими о происхождении человека, разума и т.д. Мы обратимся к самому началу — происхождению видов бактерий. И хотя там есть много узкоспециальных вопросов, сам принцип построения филогенетических деревьев не такой легкий, но захватывающий. О нем то мы и будем говорить.

Чуть ранее я написал статью Систематика прокариот — дальние родственники, где сообщил о грубых результатах и методе их получения. Он несколько не классический, но вполне укладывается в научную парадигму. Достаточно «жесткий» диалог с Davidov, который имел место быть в этой статье, может создать впечатление проблематичности метода о котором я говорю. Но мы потом сели и спокойно обсудили, и подвели некоторые итоги. Суть диалога представляет некоторый интерес и я его вначале частично опубликую.

А затем хочу продемонстрировать один наглядный пример построения дерева «происхождения видов» с помощью моего подхода (назовем его «детерминированный подход»). По сути метод можно обобщить, и тогда он не будет относится только к филогенетике и его можно использовать в других областях, когда нужно граф превратить в дерево, выкинув слабые связи.

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

12
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js