How to become an author
Search
Write a publication
Pull to refresh

Comments 70

Любопытно, как меняются стереотипы. А ведь еще совсем недавно «самый первый пример который приходит в голову», был о решении транспортной задачи. :)
Total votes 13: ↑12 and ↓1+11
Согласен =)
Сейчас первое что пришло в голову это люди и дружба между ними (читай: социальная сеть)
Total votes 1: ↑1 and ↓0+1
Я думаю есть куча менее очевидных, но более интересных применений. Интересно было бы привести именно такие примеры.
Total votes 1: ↑1 and ↓0+1
Вот отличный пример: в игре «11й час» была головоломка. Обрезок шахматной доски, на котором чёрных и белых коней нужно было поменять местами (скриншот). Мы долго бились, перебирали варианты.

В универе мы только начинали изучать дискретную математику, в частности — теорию графов.

И неожиданно мне в голову пришла мысль: а что, если ситуацию в виде графа, где узлы — клетки доски, которые соединяются возможными ходами коней. Сказано — сделано. В итоге получилась настолько простая картинка, что головоломка становилась детской (а-ля головоломка с поездом и сменой порядка вагонов при том, что есть тупиковый запасной путь). Однако на шахматной доске эти пути были как бы завязаны в узел, потому головоломка казалась сложной :)
Total votes 2: ↑2 and ↓0+2
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части =)
Total votes 2: ↑2 and ↓0+2
Фундаментальная книжка. По мне, так каждый должен прочитать )
Total votes 1: ↑1 and ↓0+1
Согласен. Но людей надо заинтересовать, я надеюсь что такими статьями можно заинтересовать людей которые совсем не знакомы с темой. И о Кормене откуда-то нужно узнать.
Сам читал Кормена несколько раз и считаю что каждый Программист (именно с большой буквы) должен прочитать. Идея в том, что нужно где то один раз наткнуться на тему а дальше каждый сам решает если ему достаточно такого описания или он пойдет читать Кормена.
Total votes 3: ↑3 and ↓0+3
Так или иначе, написано довольно адекватно. Я бы заинтересовался %)
Total votes 2: ↑2 and ↓0+2
Заинтересовался, спасибо.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Ф. Харари — Теория графов. Замечательная книжка. Но для программирования обычно хватает университетского учебника по дискретной математике + описания необходимого алгоритма.
This comment wasn’t rated yet0
BFS уже был в этом же блоге, помогло при подготовке к экзамену по дискре =)
This comment wasn’t rated yet0
Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).

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

Total votes 15: ↑13 and ↓2+11
+++
Ничего лишнего и всё правильно!!! В википедию закиньте, плз!
Total votes 3: ↑2 and ↓1+1
Вы про эквивалентность определений слышали? В той же дискретке даётся как минимум 5 определений дерева ;)
Total votes 2: ↑2 and ↓0+2
К слову, в дискретке нет понятий «вершина», «ребро», а есть понятия «множество», «n-арное отношение». Я не посягаю на эквивалентность определений.
This comment wasn’t rated yet0
Выше чётко сказано, что вершинами называют элементы множества, а рёбрами — пары элементов относительно бинарной операции(отношения). Не думаю что эти термины где-то определены по-другому.

А насчёт базовых определений — никто (надеюсь, никто) не спорит. Без них никуда.
Total votes 1: ↑1 and ↓0+1
И кто вам такое сказал. Я учусь на специальности прикладная математика и подобные определения вроде вершина, ребро, ориентированность и подобные очень часто используются. Тем более, что определение графа использует эти понятия.
This comment wasn’t rated yet0
Определение графа дано выше. В нем только 2 основных понятия из дискретной математики. Все остальное — то, что входит в раздел «теория графов». Именно там:
— будем называть элементы множества вершинами;
— элементы бинарного отношения — ребрами etc.
This comment wasn’t rated yet0
Вот из-за того, что большинство учёных — анектдотические армянские пионеры (которые, как известно, выбирают сложный путь), наука непопулярна.
Total votes 2: ↑1 and ↓10
UFO just landed and posted this here
Мне тоже такое определение больше по душе, но всеж статья как бы ликбез, поэтому определение «на пальцах» тут гораздо уместнее, иначе пришлось бы писать все сопутствующие определения (бинарные отношения etc)
This comment wasn’t rated yet0
такое определение не расширяется на мультиграфы, то есть на графы с кратными ребрами (несколько ребер между одной и той же парой вершин)

Наиболее четкое математическое определение графа выглядит так:
тройка (V, E, phi) множества вершин V, множества ребер E и отображения из множества ребер в множество пар вершин phi.

Но согласитесь, что в статье для широкой аудитории определение из статьи будет наиболее понятно и достаточно математически корректно)
Total votes 4: ↑4 and ↓0+4
UFO just landed and posted this here
Вот самое правильное определение. :)
И все-таки оно не достаточно корректно, так как из него не очень понятно (читай совсем непонятно) как соотносятся элементы из V с элементами из E
хотя в жизни все конечно пишут просто (V,E) а не (V,E,phi), ибо лень просто. phi держим в уме :)
А по жизни скорее бинарные отношения любят представлять в виде графа, а не наоборот.
This comment wasn’t rated yet0
оно = определение из статьи. зарапортовался, простите.
This comment wasn’t rated yet0
Первое определение может и не очень четкое, но как-то больше располагает неподготовленного читателя.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Из такого определения напрочь выпадает специфика графа.
This comment wasn’t rated yet0
Не упомянуты основы:

1. Cмешанный граф — когда есть ребра с ориентацией и без;
2. Формально ребер между двумя вершинами может быть несколько (мультиграф);
3. Ребро может быть петлей (соединяет вершину саму с собой): A[i=j] > 0;

Яркие примеры: разводка печатных плат и транспортные задачи.
Total votes 7: ↑7 and ↓0+7
Мне кажется, что это не совсем основы.
Total votes 4: ↑3 and ↓1+2
Ну мультиграфы — вполне основы и многие алгоритмы с ними и работают. Псевдографы — да, реже применяются.
Total votes 1: ↑1 and ↓0+1
Это _тоже_ основы.
Изложенные в статье без этого недостаточно полно.
Total votes 3: ↑0 and ↓3-3
Мультиграф это просто обобщение теории…
Total votes 3: ↑3 and ↓0+3
О котором неплохо бы упомянуть…
Total votes 2: ↑2 and ↓0+2
Замечательно написано, жду следующих статей с великим нетерпением!
Total votes 4: ↑2 and ↓20
Спасибо конечно за ссылку, но таким образом я просто хотел сказать автору спасибо за труды праведные.
Total votes 1: ↑1 and ↓0+1
Возьмите книгу Седжвика, пятую часть Фундаментальных алгоритмов, всяко книга лучше статей, хотя и их читать тоже полезно.
Total votes 1: ↑1 and ↓0+1
чтобы не томить себяожиданием можно открыть учебник, все то же самое только без комментов
This comment wasn’t rated yet0
Эх, а когда преподавали это в универе, казалось «Что это? Зачем это мне надо? Кто поставил эту ересь в предметную сетку?»
А сейчас так очень даже интересно ))
Total votes 8: ↑6 and ↓2+4
Сейчас ответ очевиден — чтобы не придумывать велосипед с квадратными колесами =).
Интересно — за что тебя минусуют?
This comment wasn’t rated yet0
Ну да. Вообще, очень многое из того, что на учебе кажется ненужным, оказывается крайне полезным спустя каких-то несколько лет.
А минусуют — да боги с ними. Один одаренный и до кармы добрался ))
Total votes 4: ↑4 and ↓0+4
1. Не сказано о массиве смежностей, как одного из способов представления графа, который является экономным по требуемой памяти, но эффективен, когда нет необходимости корректировать граф.
2. Раз уж речь пойдет об алгоритмах, то следует в базовые понятия включить определение «алгоритма» и «сложности алгоритма»

В общем, получилось достаточно легковесно и доступно, с удовольствием буду следить за продолжением… Спасибо.
This comment wasn’t rated yet0
3. Не было сказано о взвешенных графах… Это тоже одна из основных вещей.
This comment wasn’t rated yet0
1) Описание не привязано к языку программирования. Массивы есть не в каждом языке.

2) Конечно, про сложность каждого алгоритма нужно будет своевременно сказать. Но не было их ещё. А забивать статью сторонними (алгоритм, сложность..) определениями всё же не стоит. Они довольно интуитивны, и найти формальное определение нетрудно.
Total votes 2: ↑2 and ↓0+2
оригинал xpic99:
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части

Код будет, либо на псевдоязыке, который необходимо было описать вводной части, либо на конкретном.
Также матрица смежностей и списки смежностей представлены в виде массива, если их можно представить в «без массивных» языках, то и массив смежностей тоже можно представить.

2) Вторая статья уже посвящена алгоритму, чтобы ее не разбавлять всякими лирическими отступлениями, то лучше в этой ввести все определения.

Total votes 2: ↑1 and ↓10
А как насчёт абстракции от способа хранения? Например, делаем функцию, которая по идентификаторам вершин возвращает значение ячейки матрицы смежности.

2) Если исключить код и примеры, то по BFS можно сказать от силы с десяток предложений. Неинтересно же. К тому же эта статья и так довольно объёмная.
Total votes 1: ↑1 and ↓0+1
1) Все применимо к массиву смежностей :). От того, что в названии метода, присутствует слово «массив», не следует, что необходим для хранения именно массив как тип данных

2) Поиск в ширину лучше рассматривать с поиском в глубину… Рассказать, чем отличаются и чем обуславливается выбор конкретного алгоритма.
This comment wasn’t rated yet0
Матрица изначально все же математическая абстракция. Не стоит из-за некоторых языков не включать такую серьезную вещь.
This comment wasn’t rated yet0
Кстати, ищу книжку с «классическими» задачами дискретной математики, например, задача о коммивояжере. Уважаемое хабрасообщество не порекомендует какую-нибудь?
Total votes 2: ↑2 and ↓0+2
Асанов М.О., Баранский В.А., Расин В.В. — Дискретная математика: графы, матроиды, алгоритмы
Total votes 2: ↑2 and ↓0+2
Я бы порекомендовал Окулова
Прочитал всего. Там начинается с «длиной арифметики», а потом графы, коммивояжер, и максимальный поток, венгерский алгоритм (в качестве задачки)… Много интересных задач. И книжка всего на 300 страниц. =)
Total votes 1: ↑1 and ↓0+1
Просмотрел содержание — хорошая, годная книжка. Спасибо.
Total votes 1: ↑1 and ↓0+1
Графы также используются в телекоммуникациях, а именно в теории сетей, например. Ими очень удобно описывать структуру сети и решать сопутствующие задачи.
Total votes 1: ↑1 and ↓0+1
хм…
а как ЕЩЁ можно описать структуру сети, без графов?
This comment wasn’t rated yet0
Мне очень понравилось давно хотел с граффами окончательно разобраться! Спасибо
Total votes 2: ↑2 and ↓0+2
Здорово, что кто-то решился написать об этом :)

Правда, мне кажется, в «вводной» статье Вы упустили достаточно важный момент — возможность существования весов у ребер. Без этого, например, задача о поиске кратчайшего пути кажется не такой интересной :)
Total votes 2: ↑2 and ↓0+2
Не так давно была чудеснейшая статья об алгоритме Дейкстры… Было бы хорошо дать линк на нее, ибо это было бы неплохим примером с замечательными иллюстрациями :)
This comment wasn’t rated yet0
Я прошу простить, ответил не туда, куда хотел :)
This comment wasn’t rated yet0
спасибо
как раз искал способ построения коротких путей на карте по опр.точкам
This comment wasn’t rated yet0
А про матрицу инцидентности что же не написали? В некоторых алгоритмах она тоже используется.
Ну и не забывайте, что в ориентированных графах не ребра, а дуги (arcs). ;)
Total votes 1: ↑1 and ↓0+1
Вот почему, в универе это все так напрягало и казалось сложным. А сейчас просто на досуге интересно читать?
Total votes 1: ↑1 and ↓0+1
препод хреновый?
или учёба только в ночь перед сессией…
Total votes 1: ↑1 and ↓0+1
И то, и другое.
Усваивал уже когда понадобилось для работы, термины многие не помню — но представляю, как работает и для чего нужно.

Я вобще к тому, что с каждым годом все интереснее учится — когда не заставляет никто и не подгоняет, но на это все меньше свободного времени.
Да и просто материала тонны в интернете стало, видео, лекции, статьи — на высоком уровне.
This comment wasn’t rated yet0
только хотел написать об это
те кому нужно еще в универе это усвоили и использовали, а остальным и сейчас не нужно:)
This comment wasn’t rated yet0
я пока только рабираюсь с основами алгоритмов, поэтому оч простой вопрос: а матрица смежности заполняется тоже по какому-то алгоритму или вручную, т е вижу связь — заношу «1» не вижу -«0»?
за материал, спасибо-)
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Change theme settings

Your account

Sections

Information

Services

Support
© 2006–2024, Habr