Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 70
Любопытно, как меняются стереотипы. А ведь еще совсем недавно «самый первый пример который приходит в голову», был о решении транспортной задачи. :)
Согласен =)
Сейчас первое что пришло в голову это люди и дружба между ними (читай: социальная сеть)
Сейчас первое что пришло в голову это люди и дружба между ними (читай: социальная сеть)
Я думаю есть куча менее очевидных, но более интересных применений. Интересно было бы привести именно такие примеры.
Вот отличный пример: в игре «11й час» была головоломка. Обрезок шахматной доски, на котором чёрных и белых коней нужно было поменять местами (скриншот). Мы долго бились, перебирали варианты.
В универе мы только начинали изучать дискретную математику, в частности — теорию графов.
И неожиданно мне в голову пришла мысль: а что, если ситуацию в виде графа, где узлы — клетки доски, которые соединяются возможными ходами коней. Сказано — сделано. В итоге получилась настолько простая картинка, что головоломка становилась детской (а-ля головоломка с поездом и сменой порядка вагонов при том, что есть тупиковый запасной путь). Однако на шахматной доске эти пути были как бы завязаны в узел, потому головоломка казалась сложной :)
В универе мы только начинали изучать дискретную математику, в частности — теорию графов.
И неожиданно мне в голову пришла мысль: а что, если ситуацию в виде графа, где узлы — клетки доски, которые соединяются возможными ходами коней. Сказано — сделано. В итоге получилась настолько простая картинка, что головоломка становилась детской (а-ля головоломка с поездом и сменой порядка вагонов при том, что есть тупиковый запасной путь). Однако на шахматной доске эти пути были как бы завязаны в узел, потому головоломка казалась сложной :)
а BFS для не осиливших Кормена?
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части =)
Фундаментальная книжка. По мне, так каждый должен прочитать )
Согласен. Но людей надо заинтересовать, я надеюсь что такими статьями можно заинтересовать людей которые совсем не знакомы с темой. И о Кормене откуда-то нужно узнать.
Сам читал Кормена несколько раз и считаю что каждый Программист (именно с большой буквы) должен прочитать. Идея в том, что нужно где то один раз наткнуться на тему а дальше каждый сам решает если ему достаточно такого описания или он пойдет читать Кормена.
Сам читал Кормена несколько раз и считаю что каждый Программист (именно с большой буквы) должен прочитать. Идея в том, что нужно где то один раз наткнуться на тему а дальше каждый сам решает если ему достаточно такого описания или он пойдет читать Кормена.
BFS уже был в этом же блоге, помогло при подготовке к экзамену по дискре =)
Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
У меня в университете преподаватель по дискретке, который этими самыми графами и алгоритмами на них уже не один десяток лет занимается, такую формулировку пресекал на корню.
«Граф есть множество и бинарное отношение на нем» — это как четкое математическое определение.
+++
Ничего лишнего и всё правильно!!! В википедию закиньте, плз!
Ничего лишнего и всё правильно!!! В википедию закиньте, плз!
Вы про эквивалентность определений слышали? В той же дискретке даётся как минимум 5 определений дерева ;)
К слову, в дискретке нет понятий «вершина», «ребро», а есть понятия «множество», «n-арное отношение». Я не посягаю на эквивалентность определений.
Выше чётко сказано, что вершинами называют элементы множества, а рёбрами — пары элементов относительно бинарной операции(отношения). Не думаю что эти термины где-то определены по-другому.
А насчёт базовых определений — никто (надеюсь, никто) не спорит. Без них никуда.
А насчёт базовых определений — никто (надеюсь, никто) не спорит. Без них никуда.
И кто вам такое сказал. Я учусь на специальности прикладная математика и подобные определения вроде вершина, ребро, ориентированность и подобные очень часто используются. Тем более, что определение графа использует эти понятия.
Мне тоже такое определение больше по душе, но всеж статья как бы ликбез, поэтому определение «на пальцах» тут гораздо уместнее, иначе пришлось бы писать все сопутствующие определения (бинарные отношения etc)
такое определение не расширяется на мультиграфы, то есть на графы с кратными ребрами (несколько ребер между одной и той же парой вершин)
Наиболее четкое математическое определение графа выглядит так:
тройка (V, E, phi) множества вершин V, множества ребер E и отображения из множества ребер в множество пар вершин phi.
Но согласитесь, что в статье для широкой аудитории определение из статьи будет наиболее понятно и достаточно математически корректно)
Наиболее четкое математическое определение графа выглядит так:
тройка (V, E, phi) множества вершин V, множества ребер E и отображения из множества ребер в множество пар вершин phi.
Но согласитесь, что в статье для широкой аудитории определение из статьи будет наиболее понятно и достаточно математически корректно)
Вот самое правильное определение. :)
И все-таки оно не достаточно корректно, так как из него не очень понятно (читай совсем непонятно) как соотносятся элементы из V с элементами из E
хотя в жизни все конечно пишут просто (V,E) а не (V,E,phi), ибо лень просто. phi держим в уме :)
А по жизни скорее бинарные отношения любят представлять в виде графа, а не наоборот.
И все-таки оно не достаточно корректно, так как из него не очень понятно (читай совсем непонятно) как соотносятся элементы из V с элементами из E
хотя в жизни все конечно пишут просто (V,E) а не (V,E,phi), ибо лень просто. phi держим в уме :)
А по жизни скорее бинарные отношения любят представлять в виде графа, а не наоборот.
оно = определение из статьи. зарапортовался, простите.
Первое определение может и не очень четкое, но как-то больше располагает неподготовленного читателя.
Из такого определения напрочь выпадает специфика графа.
Не упомянуты основы:
1. Cмешанный граф — когда есть ребра с ориентацией и без;
2. Формально ребер между двумя вершинами может быть несколько (мультиграф);
3. Ребро может быть петлей (соединяет вершину саму с собой): A[i=j] > 0;
Яркие примеры: разводка печатных плат и транспортные задачи.
1. Cмешанный граф — когда есть ребра с ориентацией и без;
2. Формально ребер между двумя вершинами может быть несколько (мультиграф);
3. Ребро может быть петлей (соединяет вершину саму с собой): A[i=j] > 0;
Яркие примеры: разводка печатных плат и транспортные задачи.
Замечательно написано, жду следующих статей с великим нетерпением!
Можно не ждать:
www.intuit.ru/department/algorithms/ingrth/class/free/status/
www.intuit.ru/department/algorithms/ingrth/class/free/status/
Возьмите книгу Седжвика, пятую часть Фундаментальных алгоритмов, всяко книга лучше статей, хотя и их читать тоже полезно.
чтобы не томить себяожиданием можно открыть учебник, все то же самое только без комментов
Эх, а когда преподавали это в универе, казалось «Что это? Зачем это мне надо? Кто поставил эту ересь в предметную сетку?»
А сейчас так очень даже интересно ))
А сейчас так очень даже интересно ))
1. Не сказано о массиве смежностей, как одного из способов представления графа, который является экономным по требуемой памяти, но эффективен, когда нет необходимости корректировать граф.
2. Раз уж речь пойдет об алгоритмах, то следует в базовые понятия включить определение «алгоритма» и «сложности алгоритма»
В общем, получилось достаточно легковесно и доступно, с удовольствием буду следить за продолжением… Спасибо.
2. Раз уж речь пойдет об алгоритмах, то следует в базовые понятия включить определение «алгоритма» и «сложности алгоритма»
В общем, получилось достаточно легковесно и доступно, с удовольствием буду следить за продолжением… Спасибо.
3. Не было сказано о взвешенных графах… Это тоже одна из основных вещей.
1) Описание не привязано к языку программирования. Массивы есть не в каждом языке.
2) Конечно, про сложность каждого алгоритма нужно будет своевременно сказать. Но не было их ещё. А забивать статью сторонними (алгоритм, сложность..) определениями всё же не стоит. Они довольно интуитивны, и найти формальное определение нетрудно.
2) Конечно, про сложность каждого алгоритма нужно будет своевременно сказать. Но не было их ещё. А забивать статью сторонними (алгоритм, сложность..) определениями всё же не стоит. Они довольно интуитивны, и найти формальное определение нетрудно.
xpic99:
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части
Код будет, либо на псевдоязыке, который необходимо было описать вводной части, либо на конкретном.
Также матрица смежностей и списки смежностей представлены в виде массива, если их можно представить в «без массивных» языках, то и массив смежностей тоже можно представить.
2) Вторая статья уже посвящена алгоритму, чтобы ее не разбавлять всякими лирическими отступлениями, то лучше в этой ввести все определения.
А как насчёт абстракции от способа хранения? Например, делаем функцию, которая по идентификаторам вершин возвращает значение ячейки матрицы смежности.
2) Если исключить код и примеры, то по BFS можно сказать от силы с десяток предложений. Неинтересно же. К тому же эта статья и так довольно объёмная.
2) Если исключить код и примеры, то по BFS можно сказать от силы с десяток предложений. Неинтересно же. К тому же эта статья и так довольно объёмная.
1) Все применимо к массиву смежностей :). От того, что в названии метода, присутствует слово «массив», не следует, что необходим для хранения именно массив как тип данных
2) Поиск в ширину лучше рассматривать с поиском в глубину… Рассказать, чем отличаются и чем обуславливается выбор конкретного алгоритма.
2) Поиск в ширину лучше рассматривать с поиском в глубину… Рассказать, чем отличаются и чем обуславливается выбор конкретного алгоритма.
Матрица изначально все же математическая абстракция. Не стоит из-за некоторых языков не включать такую серьезную вещь.
Кстати, ищу книжку с «классическими» задачами дискретной математики, например, задача о коммивояжере. Уважаемое хабрасообщество не порекомендует какую-нибудь?
Асанов М.О., Баранский В.А., Расин В.В. — Дискретная математика: графы, матроиды, алгоритмы
Я бы порекомендовал Окулова
Прочитал всего. Там начинается с «длиной арифметики», а потом графы, коммивояжер, и максимальный поток, венгерский алгоритм (в качестве задачки)… Много интересных задач. И книжка всего на 300 страниц. =)
Прочитал всего. Там начинается с «длиной арифметики», а потом графы, коммивояжер, и максимальный поток, венгерский алгоритм (в качестве задачки)… Много интересных задач. И книжка всего на 300 страниц. =)
Графы также используются в телекоммуникациях, а именно в теории сетей, например. Ими очень удобно описывать структуру сети и решать сопутствующие задачи.
Мне очень понравилось давно хотел с граффами окончательно разобраться! Спасибо
Здорово, что кто-то решился написать об этом :)
Правда, мне кажется, в «вводной» статье Вы упустили достаточно важный момент — возможность существования весов у ребер. Без этого, например, задача о поиске кратчайшего пути кажется не такой интересной :)
Правда, мне кажется, в «вводной» статье Вы упустили достаточно важный момент — возможность существования весов у ребер. Без этого, например, задача о поиске кратчайшего пути кажется не такой интересной :)
спасибо
как раз искал способ построения коротких путей на карте по опр.точкам
как раз искал способ построения коротких путей на карте по опр.точкам
А про матрицу инцидентности что же не написали? В некоторых алгоритмах она тоже используется.
Ну и не забывайте, что в ориентированных графах не ребра, а дуги (arcs). ;)
Ну и не забывайте, что в ориентированных графах не ребра, а дуги (arcs). ;)
Вот почему, в универе это все так напрягало и казалось сложным. А сейчас просто на досуге интересно читать?
препод хреновый?
или учёба только в ночь перед сессией…
или учёба только в ночь перед сессией…
И то, и другое.
Усваивал уже когда понадобилось для работы, термины многие не помню — но представляю, как работает и для чего нужно.
Я вобще к тому, что с каждым годом все интереснее учится — когда не заставляет никто и не подгоняет, но на это все меньше свободного времени.
Да и просто материала тонны в интернете стало, видео, лекции, статьи — на высоком уровне.
Усваивал уже когда понадобилось для работы, термины многие не помню — но представляю, как работает и для чего нужно.
Я вобще к тому, что с каждым годом все интереснее учится — когда не заставляет никто и не подгоняет, но на это все меньше свободного времени.
Да и просто материала тонны в интернете стало, видео, лекции, статьи — на высоком уровне.
только хотел написать об это
те кому нужно еще в универе это усвоили и использовали, а остальным и сейчас не нужно:)
те кому нужно еще в универе это усвоили и использовали, а остальным и сейчас не нужно:)
я пока только рабираюсь с основами алгоритмов, поэтому оч простой вопрос: а матрица смежности заполняется тоже по какому-то алгоритму или вручную, т е вижу связь — заношу «1» не вижу -«0»?
за материал, спасибо-)
за материал, спасибо-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы на графах — Часть 0: Базовые понятия