Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.
Читать полностью »
Метка «граф»
Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами
2014-06-10 в 9:13, admin, рубрики: Алгоритмы, граф, покрытие, метки: граф, покрытиеДиаграммы и графы в LaTeX с использованием PGF/TikZ 3.0
2014-05-29 в 13:59, admin, рубрики: latex, граф, диаграмма, метки: latex, граф, диаграмма 
Несколько месяцев назад вышел графический пакет для LaTeX PGF/TikZ 3.0, и в нём появилось немало интересных штук. В этой статье мы попробуем их применить для рисования простой блок-схемы. Нарисуем, например, кусочек известной схемы определения языка по письменности. Средства, уже рассмотренные в ранее опубликованной статье, трогать не будем, а поговорим об упрощённой нотации записи графов и управлением позиционированием узлов и ветвлением графа.
Теория памяти человека, зачатки ИИ
2014-02-25 в 11:22, admin, рубрики: биоинформатика, граф, ИИ, искусственный интеллект, нейроны, оптимизация памяти, связи, метки: граф, ИИ, нейроны, оптимизация памяти, связиТеория памяти человека, зачатки ИИ
Наверняка всем Вам очень хорошо известны такие моменты, когда нужно что-то вспомнить, но извлечь информацию из мозга становится большим пазлом.
Почему же такое происходит. Для начала немного теории работы нейрона, можно почитать тут или тут
Предположим, а может так оно и есть, все нейроны объединены в одни очень большой граф со сложной структурой. Данная структура сложна и не может работать хаотично, т.е. передаваемые импульсы передаются строго в определённом порядке, поэтому тут есть 2 варианта:
- Ребра графа имеют только положительные веса
- Ребра графа могут иметь, как положительные так и отрицательные веса
Рассматривая второй случай в реальной работе памяти человека, можно предположить, что такая ситуация возникает при провалах памяти человека, т.е. к нейрону содержащему ту информацию которая нам необходимо либо поступает недостаточно сигналов, для накопления и дальнейшей передачи, либо этих сигналов вообще нет. В случае с графами это можно представить, как узел у которого мало путей, либо они отрицательны, либо их вообще нет (рис 1).
Что же касается первого случая, когда все ребра имеют положительные веса, т.е. головной мозг человека не поврежден. Тогда почему же человек не может вспомнить моменты из своего детства? Ответ прост: “Любое тело стремится к покою”, так же и наша с вами нейронная сеть старается оптимизировать свою работу. (Владельцам навигаторов должно быть знакомо, что прокладка маршрута, как раз таки строится на принципах работы графа, нахождения кратчайшего пути и т.д.). Мозг человека более изощренная система и его оптимизация заключается в разрыве связей с малыми весами, и построении новых связей с более высокими. (рис. 2). Таким образом объяснятся многочисленные разрывы и новые соединения нейронов. Чем больше узел имеет связей, тем легче вспомнить необходимую информацию.
Читать полностью »
Маскируем класс под граф Boost. Часть 3: Находим путь
2014-02-17 в 11:20, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Часть 2: Завершаем реализацию поддержки концепций
В прошлых статьях цикла описывался процесс адаптации класса клеточного игрового поля под концепции графов boost. Сейчас рассмотрим собственно то, ради чего все затевалось — поиск пути на клеточном поле. Реализация поиска boost позволяет достаточно тонко настраивать алгоритм, в этой статье будет приведет только один пример такой параметризации — возможность задавать различную длину ребер графа.
Читать полностью »
Маскируем класс под граф Boost. Часть 2: Завершаем реализацию поддержки концепций
2014-02-10 в 22:34, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Кратко напомню задачу. Есть двумерное игровое поле из клеток, часть из которых свободна, а часть занята. Требуется найти путь по свободным клеткам из одной позиции поля в другую. Алгоритм поиска пути реализован в Boost. Но он требует, чтобы наше поле подходило под определение графа. Точнее класс должен удовлетворять двум концепциям — boost::VertexListGraph и boost:: IncidenceGraph. При этом интерфейс игрового поля менять не хочется — для всего остального проекта это не граф и графом никогда не станет.
В прошлой части было рассмотрено подключение внешних ассоциированных типов, необходимых для интерпретации класса как boost-графа. Конечно, одних типов недостаточно. Также требуется реализовать несколько функций с заданной сигнатурой и итераторов, с помощью которых библиотека сможет манипулировать игровым полем как графом.
Читать полностью »
Маскируем класс под граф Boost. Часть 1: Не трогаем интерфейс
2014-02-06 в 9:27, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «найди функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную гибкость использования, что негативно сказалось на простоте. В то же время и ничего смертельного — все лучше, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться желания не было, в то время как boost в проекте используется давно…
Читать полностью »
Пример использования WxPython для создания нодового интерфейса. Часть 5: Соединяем ноды
2013-11-13 в 4:48, admin, рубрики: framework, Node, python, wxpython, граф, интерфейс, нодовый интерфейс, Программирование, разработка, метки: framework, Node, python, wxpython, граф, интерфейс, нодовый интерфейс Медленно, но верно, я продолжаю делать серию туториалов о WxPython, где я хочу рассмотреть разработку ферймворка для создания нодового интерфейса с нуля и до чего-то вполне функционального и рабочего. В прошлых частях уже рассказано как добавлять ноды, в этой же части, мы их будем соединять, а на этой картинке показан результат, который мы в этой статье получим:
Еще не идеально, но уже вырисовывается что-то вполне полезное и рабочее.
Прошлые части живут тут:
Часть 1: Учимся рисовать
Часть 2: Обработка событий мыши
Часть 3: Продолжаем добавлять фичи + обработка клавиатуры
Часть 4: Реализуем Drag&Drop
Как найти девушку через общий топор — Майн объединяет владельцев вещей
2012-10-30 в 7:04, admin, рубрики: вещизм, граф, клуб, собственность, стартап, я пиарюсь, метки: вещизм, граф, клуб, собственность, стартап 
Нет, мы не сайт знакомств ни разу.
Mine — это всемирный граф частной собственности
Mine — это вконтактик для ваших мимимишечек
Если серьёзно, то Майн — это сайт, на котором люди связываются через свои вещи. Наконец-то вы сможете:
- Вступить в клуб владельцев перочинного ножа
- Пощекотать ваше толстое материалистическое эго
- Публично признаться в трогательной нежности к своему ноутбуку
- Показать всем чего вы стоите (буквально)
- Найти женщину-гика на белом Харлее и с приставкой денди
- Подкараулить владельца нового Vertu ночью у подъезда! (чтобы поболтать)
- Открыто ненавидеть обладателя 7-и айфонов! (и т.д.)
Почему мы считаем, что такая на первый взгляд лекгомысленная затея может стать крепким звеном мирового e-commerce рынка, зачем магазины должны вставать к нам в очередь и пара стратегических секретов — под катом.