Pull to refresh
  • by relevance
  • by date
  • by rating

Максимальный поток минимальной стоимости

Algorithms *
Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.

Путешествие в тысячу миль начинается с первого шага
Total votes 173: ↑165 and ↓8 +157
Views 76K
Comments 76

Графы для самых маленьких: BFS

Algorithms *
В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
Читать дальше →
Total votes 35: ↑26 and ↓9 +17
Views 87K
Comments 2

Графы для самых маленьких: BFS 0-1

Algorithms *
Добрый день, уважаемые хабровчане!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.
Читать дальше →
Total votes 10: ↑8 and ↓2 +6
Views 21K
Comments 3

Реализация алгоритма BFS на GPU

GPGPU *Concurrent computing *

Аннотация


В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.

Введение


В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.
Читать дальше →
Total votes 28: ↑26 and ↓2 +24
Views 11K
Comments 7

Поиск в ширину (BFS) на С#

Delirium coding Algorithms *C# *
Sandbox
Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.

Устно об алгоритме:

Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).

Последовательность алгоритма заключается в следующим:

1. Выбирается произвольно вершина графа (отмечается серым).
2.Последовательно рассматриваются вершины (так же отмечаются серым), связанные с нашей первой вершиной (после этого она становится не серой, а чёрной).
3. Выполняется пункт 2 для отмеченных (серых) вершин до тех пор, пока все вершины не будут закрашены чёрным.


Читать дальше →
Total votes 16: ↑6 and ↓10 -4
Views 37K
Comments 3

Самая быстрая и энергоэффективная реализация алгоритма BFS на различных параллельных архитектурах

High performance *C++ *Algorithms *GPGPU *Concurrent computing *

Оффтоп


В названии статьи не поместилось — данные результаты считаются таковыми по версии рейтинга Graph500. Также хотелось бы выразить благодарность компаниям IBM и RSC за предоставленные ресурсы для проведения экспериментальных запусков во время исследования.


Введение


Поиск в ширину (BFS) является одним из основных алгоритмов обхода графа и базовым для многих алгоритмов анализа графов более высокого уровня. Поиск в ширину на графах является задачей с нерегулярным доступом к памяти и с нерегулярной зависимостью по данным, что сильно усложняет его распараллеливание на все существующие архитектуры. В статье будет рассмотрена реализация алгоритма поиска в ширину (основного теста рейтинга Graph500) для обработки больших графов на различных архитектурах: Intel х86, IBM Power8+, Intel KNL и NVidia GPU. Будут описаны особенности реализации алгоритма на общей памяти, а также преобразования графа, которые позволяют достичь рекордных показателей производительности и энергоэффективности на данном алгоритме среди всех одноузловых систем рейтинга Graph500 и GreenGraph500.

Нажми и прочитай про самый быстрый BFS в мире!
Total votes 13: ↑13 and ↓0 +13
Views 8.2K
Comments 4

В чём уникальность BeOS и HaikuOS

Working with icons *System Programming *Interfaces *Software
Translation
Первое, на что следует обратить внимание в бета-версии Haiku — это работа с пакетами.

Когда мы говорим просто «пакеты», то подразумеваем только запуск пакетного менеджера на GNU/Linux, и т.д., но Haiku умеет гораздо больше.

Как я уже упоминал в обзоре Haiku Beta, это первый официальный релиз функции управления пакетами. Если сформулировать вкратце, то представьте PackageFS как нечто похожее (но не такое же) на старую систему модулей Slax 6, но со всеми обычными инструментами для «пакетов».

Систему управления пакетами можно описать в пяти кратких пунктах:

  • универсальные инструменты командной строки (как и следовало ожидать);
  • HaikuDepot;
  • средство обновления программ;
  • мониторинг состояния пакетов и/или системы;
  • PackageFS (где все пакеты плавно монтируются и подключаются при загрузке), с побочным эффектом — аккуратным слоем безопасности.
Читать дальше →
Total votes 49: ↑48 and ↓1 +47
Views 17K
Comments 20

Техническая презентация нового космического корабля Starship/BFS от SpaceX планируется в марте-апреле 2019-го года

Astronautics

Ссылка на картинку (апдейт от 05.01.2019)
Благодаря товарищу Chris (Robotbeat) у нас появилось много ответов от Илона Маска по поводу нового космического корабля от SpaceX. Так, пользователь в твиттере написал сообщение Маску с фотографиями непонятных конструкций в Техасе и спросил, есть ли что нам показать. Как оказалось, идет полным ходом сборка тестовой части Starship. Крайне удачным оказался еще другой пользователь – любитель космоса, Everyday Astronaut. Он задал много вопросов, на которые Маск ответил.
Total votes 41: ↑38 and ↓3 +35
Views 14K
Comments 75

Разбор задачи с собеседования Google: поиск соотношения

Entertaining tasks Programming *Algorithms *
Translation


Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.
Читать дальше →
Total votes 47: ↑41 and ↓6 +35
Views 37K
Comments 73

Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript

Website development *JavaScript *Programming *.NET *
Translation
Доброго времени суток.

Представляю вашему вниманию перевод статьи «Algorithms on Graphs: Let’s talk Depth-First Search (DFS) and Breadth-First Search (BFS)» автора Try Khov.

Что такое обход графа?


Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.

Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).

Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views 53K
Comments 1