Каковы хорошие примеры проблем, которые графы могут решить лучше, чем альтернатива?

Ответ 1

Компьютерные сети: Модель графиков интуитивно моделирует компьютерные сети и Интернет. Часто узлы представляют собой конечные системы или маршрутизаторы, а ребра представляют собой соединения между этими системами.

Структуры данных: Любая структура данных, использующая указатели для соединения данных вместе, использует какой-то граф. Это включает в себя древовидные структуры и связанные списки, которые используются все время.

Путь и карты:. Попытка найти кратчайшие или длинные пути из определенного места в пункт назначения использует графики. Это может включать в себя путь, как вы видите в приложении, таком как карты Google, или вычисление путей для символов AI для принятия видеоигры и многих других подобных проблем.

Удовлетворение ограничений:. Общей проблемой в ИИ является поиск некоторой цели, которая удовлетворяет списку ограничений. Например, для университета, чтобы установить его расписания курсов, он должен убедиться, что определенные курсы не противоречат друг другу, что профессор не учит одновременно двум курсам, что лекции происходят во время определенных временных интервалов и т.д., Проблемы с ограничениями, подобные этому, часто моделируются и решаются с использованием графиков.

Молекулы: Графы могут использоваться для моделирования атомов и молекул для изучения их взаимодействия и структуры между прочим.

Ответ 2

Меня очень интересует теория графов, и я использовал ее для решения многих различных проблем. Вы можете решить много проблем, связанных с путём, сопоставить проблему, проблемы структуры с использованием графика.

• Проблемы с контентом имеют множество приложений.

  Это было в вопросе интервью с вопросом о карьере. Скажем, вы хотите найти самую длинную сумму вспомогательного массива. Например, [1, 2, 3, -1] имеет самую длинную сумму из 6. Моделируйте ее как Direct Acitlic Graph (DAG), добавьте фиктивный источник, фиктивный пункт назначения. Подключите каждый node к краю, который имеет вес, соответствующий числу. Теперь для решения этой проблемы используйте алгоритм Longest Path в DAG.

  Аналогично, проблемы арбитража в финансовом мире или даже проблемы геометрии нахождения самой длинной перекрывающейся структуры - это аналогичная проблема пути.

• Некоторые очевидные проблемы будут сетевыми проблемами (где в вашей сети могут быть компьютеры, организационные диаграммы и т.д.).
  Вы можете собрать много структурной информации, например

  • точка которого разбивает график на две части.
  • Каков наилучший способ их подключения.
  • Каков наилучший способ добраться до одного места до другого.
  • есть способ добраться до одного места от другого и т.д.

• Я решил много проблем с управлением проектами, используя графики. Последовательность событий может быть изображена как ориентированный граф (если у вас нет циклов, то это еще лучше). Итак, теперь вы можете

  • сортировать события в соответствии с их приоритетом
  • вы можете найти событие, которое является самым важным (то есть освободит много других проектов).
  • вы можете найти продолжительность, необходимую для решения общего проекта (проблема пути) и т.д.

• Много проблем соответствия могут быть решены графиком. Например, если вам нужно сопоставить процессоры с рабочей нагрузкой или сопоставить работников с их заданиями. В моем последнем экзамене мне приходилось сопоставлять людей с столами в ресторанах. Он следует тому же принципу (бипартиментное согласование → алгоритмы сетевого потока). Его простой, но мощный.

• Специальный граф, дерево, имеет множество приложений в мире компьютерных наук. Например, в синтаксисе языка программирования или в структуре индексирования базы данных.

• Совсем недавно я также использовал графики в компиляторе. Я использую книгу Моргана, которая учит меня увлекательным приемам.

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

Если вы хотите начать работу над теорией графа, получите хорошую новизну дискретной математической книги (Rosen), и вы можете покупать книги у авторов, например Fould или Даже. CLRS также имеет хорошие алгоритмы графа.

Ответ 3

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

Указатели образуют структуры графов. Все, что касается указателей, выполняет какую-то манипуляцию с графами.

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

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

Трудно думать о чем-то, что вы делаете, что не связано с какой-то структурой графика.

Ответ 4

Пример большинства людей знакомы: системы сборки. Make - типичный пример, но почти любая хорошая система сборки опирается на Direct Acyclic Graph. Основная идея заключается в том, что направление моделирует зависимость между источником и целью, и вы должны "ходить" по графику в определенном порядке, чтобы правильно строить вещи → это пример топологической сортировки.

Другим примером является система управления версиями: снова на основе DAG. Он используется для объединения, например, для поиска общего родителя.

Ответ 5

Хорошо, что многие алгоритмы оптимизации программ, используемые компиляторами, основаны на графиках (например, диаграмма выводов, управление потоком, много статического анализа).

Многие проблемы оптимизации основаны на графике. Поскольку многие проблемы сводятся к окраске графов и аналогичным проблемам, тогда многие другие проблемы также основаны на графике.

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

Ответ 6

OCR. Настройте страницу текста, сканируемого под углом, с некоторым шумом на изображении, где вы должны найти пробел между строками текста. Один из способов - составить график пикселей и найти кратчайший путь с одной стороны страницы на другую, где разница в яркости - это расстояние между пикселями.

Этот пример из Руководство по разработке алгоритмов, в котором есть много других реальных примеров проблем графа.

Ответ 7

Одним из популярных примеров является сбор мусора.

Коллекционер начинается с набора ссылок, затем пересекает все объекты, которые они ссылаются, затем все объекты, на которые они ссылаются, и так далее. Все, что он находит, добавляется в график достижимых объектов. Все остальные объекты недоступны и собраны.

Ответ 8

Чтобы узнать, могут ли две молекулы совмещаться. При разработке препаратов часто интересуется, могут ли молекулы лекарственного средства вписаться в более крупные молекулы в организме. Проблема с определением того, возможно ли это, состоит в том, что молекулы не являются статическими. Различные части молекулы могут вращаться вокруг своих химических связей, так что молекула может превращаться в довольно много разных форм.

Каждая фигура может быть указана как точка в пространстве, состоящем из фигур. Решение этой проблемы связано с поиском пути через это пространство. Вы можете сделать это, создав дорожную карту в пространстве, которая по существу представляет собой график, состоящий из юридических форм и выражающий форму, в которую может превращаться форма. Используя алгоритм поиска по алгоритму A * через эту дорожную карту, вы можете найти решение.

Хорошо, это было много болтовни, которые, возможно, были не совсем понятными или понятными. Но я хотел сказать, что графики возникают во всех видах проблем.

Ответ 9

На основе теории графов следуют следующие:

• Двоичные деревья и другие деревья, такие как красно-черные деревья, деревья расцветок и т.д.
• Связанные списки
• Все, что смоделировано как конечный автомат (GUI, сетевые стеки, процессоры и т.д.)
• Деревья принятия решений (используемые в ИИ и других приложениях)
• Наследование комплексного класса

Ответ 10

Графы отлично подходят для управления зависимостями.

Недавно я начал использовать контейнер Castle Windsor, после проверки ядра я нашел свойство GraphNodes. Castle Windsor использует граф для представления зависимостей между объектами, так что инъекция будет работать правильно. Проверьте статью.

Я также использовал простую теорию графа для разработки плагина, каждый график node представляет собой плагин, как только зависимости определены. Я могу пересечь график, чтобы создать порядок загрузки плагина.

Я планирую изменить алгоритм для реализации алгоритма Дейкстра, чтобы каждый плагин взвешивался с определенной версией, поэтому простое изменение будет загружать только последнюю версию плагина.

Я с этим обнаружил это раньше. Мне нравится эта цитата "Всякий раз, когда кто-то дает вам проблему, подумайте о графиках". Я определенно считаю, что это правда.

Ответ 11

Графики не являются структурами данных. Это математическое представление отношений. Да, вы можете мыслить и теоретизировать о проблемах с использованием графиков, и об этом много теории. Но когда вам нужно реализовать алгоритм, вы выбираете структуры данных, чтобы лучше всего представлять проблему, а не графики. Существует много структур данных, которые представляют общие графики и даже больше для специальных видов графиков.

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

Ответ 12

ИМХО Большинство моделей доменов, которые мы используем в обычных приложениях, являются графиками некоторого значения. Если вы посмотрите на диаграммы UML, вы заметите, что с направленным, помеченным графом вы можете легко перевести их непосредственно в модель персистентности. Есть несколько примеров этого в Neo4j

Приветствия

/питер

Ответ 13

Профилирование и/или бенчмаркинг алгоритмов и реализаций в коде.

Ответ 14

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

Ответ 15

Вы можете взглянуть на некоторые примеры в вики Neo4j,

http://wiki.neo4j.org/content/Domain_Modeling_Gallery

и проекты, в которых используется Neo4j (известные)

http://wiki.neo4j.org/content/Neo4j_In_The_Wild.

В противном случае рекомендательные алгоритмы являются хорошим использованием для графов, см., Например, PageRank и другие материалы на

https://github.com/tinkerpop/gremlin/wiki/pagerank

Ответ 16

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

Может быть, это поможет вам придумать примеры, поскольку большинство вещей легко смоделированы в РСУБД.

Ответ 17

Графики можно использовать в любом месте, где вы можете определить объекты проблемных объектов в узлах, а решение - как поток управления и/или данных между узлами.

Учитывая тот факт, что деревья действительно связаны с ациклическими графами, есть еще больше областей, в которых вы можете использовать теорию графов.

Ответ 18

Анализ транзакции serialisability в теории баз данных.

Ответ 19

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

К моему опыту, я интенсивно использовал график в проблемах сетевого потока, который используется во многих областях, таких как маршрутизация и оптимизация телекоммуникационной сети, назначение рабочей нагрузки, сопоставление, оптимизация цепочки поставок и планирование общественного транспорта.

Еще одна интересная область - это моделирование социальной сети, как упоминалось в предыдущем ответе.

Существует гораздо больше, например, интегральная интеграция и т.д.