Что такое хорошие примеры проблем, которые графики могут решить лучше, чем альтернатива? [закрытый]
У вас будет две таблицы, возможно, с столбцом в качестве псевдонима столбца rowid , это
, например
CREATE TABLE persons (
personid INTEGER PRIMARY KEY,
personname TEXT
);
CREATE TABLE orders (
orderid INTEGER PRIMARY KEY,
ordername TEXT,
person_reference INTEGER REFERENCES persons(personid)
);
- Обратите внимание , что вы должны включить обработку внешнего ключа, например, выполнив
PRAGMA foreign_keys = ON;(или истина). См. PRAGMA foreign_keys - в кодировании SQLite
column_name INTEGER PRIMARY KEY, который определяет этот столбец как псевдоним столбца rowid , и если значение не является для столбца при вставке, тогда будет назначено целочисленное значение. Начальное значение для первой строки будет равно 1, последующие значения обычно будут на 1 больше, чем наибольшее значение rowid (прочитайте ссылку выше, чтобы узнать, почему слово обычно использовалось) .
Если вы затем попытаетесь вставить Орден для несуществующего лица, вы получите конфликт по внешнему ключу.
Альтернативой определению уровня столбца было бы определение внешнего ключа (ей) на уровне таблицы, например
CREATE TABLE orders (
orderid INTEGER PRIMARY KEY,
ordername TEXT,
person_reference INTEGER,
FOREIGN KEY (person_reference) REFERENCES persons(personid)
);
В качестве примера рассмотрим следующее: -
INSERT INTO persons (personname) VALUES
('Fred'),
('Mary'),
('Sue'),
('Tom')
;
INSERT INTO orders (ordername, person_reference) VALUES
('Order 1 for Fred',1),
('Order 2 for Sue',3),
('Order 3 for Fred',1),
('Order 4 for Mary',2)
;
INSERT into orders (ordername, person_reference) VALUES
('Order 5 for nobody',100);
В результате получится: -
blockquote>INSERT INTO persons (personname) VALUES ('Fred'),('Mary'),('Sue'),('Tom') > Affected rows: 4 > Time: 0.453s INSERT INTO orders (ordername, person_reference) VALUES ('Order 1 for Fred',1),('Order 2 for Sue',3),('Order 3 for Fred',1),('Order 4 for Mary',2) > Affected rows: 4 > Time: 0.084s INSERT into orders (ordername, person_reference) VALUES ('Order 5 for nobody',100) > FOREIGN KEY constraint failed > Time: 0s, т.е. последний, поскольку в таблице лиц нет строки с персоной 100, то последняя вставка (на собственной демонстрации) завершается неудачей.
Вы можете обратиться к Поддержка внешнего ключа SQLite
.
18 ответов
Можно использовать графики где угодно, можно определить объекты проблемной области в узлы и решение как поток управления и/или данных среди узлов.
При рассмотрении того, что деревья являются действительно связанными графами без петель, существует еще больше областей, можно использовать теорию графов.
Профилирование и/или Сравнительное тестирование алгоритмов и реализаций в коде.
Следующее основано на теории графов:
- Двоичные деревья и другие деревья, такие как Красно-черные деревья, вывихните деревья и т.д.
- Связанные списки
- Что-либо это смоделировано как конечный автомат (графический интерфейсы пользователя, сетевые стеки, центральные процессоры, и т.д.)
- Деревья решений (используемый в AI и других приложениях)
- Сложное наследование классов
Графики являются большими для руководящих зависимостей.
Я недавно начал использовать замок Windsor Container после осмотра Ядра, я нашел свойство GraphNodes. Замок Windsor использует график для представления зависимостей между объектами так, чтобы инжекция работала правильно. Проверьте эту статью.
Я также использовал простую теорию графов для разработки сменной платформы, каждый узел графика представляют плагин, когда-то зависимости были определены, я могу пересечь график для создания сменного порядка загрузки.
Я - планирование изменения алгоритма для реализации алгоритма Dijkstra так, чтобы каждый плагин был взвешен с определенной версией, таким образом простое изменение только загрузит последнюю версию плагина.
Я с я обнаружил это раньше. Мне нравится эта кавычка "Каждый раз, когда кто-то дает Вам проблему, думайте графики". Я определенно думаю это правда.
Графики не являются структурами данных. Они - математическое представление отношений. Да, можно думать и theoretize о проблемах с помощью графиков, и существует большой раздел науки об этом. Но когда необходимо реализовать алгоритм, Вы выбираете структуры данных для лучшего представления проблемы, не графиков. Существует много структур данных, которые представляют общие графики, и еще больше для специальных видов графиков.
В Вашем вопросе Вы смешиваете эти две вещи. То же теоретическое решение может быть с точки зрения графика, но практические решения могут использовать различные структуры данных для представления графика.
Узнать, могут ли две молекулы совместиться. При разрабатывании лекарств каждый часто интересуется наблюдением, если молекулы препарата могут вписаться в большие молекулы в теле. Проблема с определением, возможно ли это, состоит в том, что молекулы не статичны. Различные части молекулы могут вращаться вокруг их химической привязки так, чтобы молекула могла измениться в довольно большое количество различных форм.
Каждая форма, как могут говорить, представляет точку в пространстве, состоящем из форм. Решение этой проблемы включает нахождение пути через это пространство. Можно сделать это путем создания дорожной карты через пространство, которое является по существу графиком, состоящим из легальных форм и говорящим, в какую форму форма может превратиться. При помощи* алгоритм поиска графика через эту дорожную карту можно найти решение.
Хорошо это было большим количеством лепета, который, возможно, не был очень понятен или ясен. Но моя точка была то, что графики открываются во всех видах проблем.
OCR. Изобразите страницу текста, просканированного под углом с некоторым шумом в изображении, где необходимо найти пространство между строками текста. Один путь состоит в том, чтобы сделать график пикселей и найти кратчайший путь с одной стороны страницы к другому, где различием в яркости является расстояние между пикселями.
Этот пример из Руководства по проектированию Алгоритма, которое имеет много других примеров реального мира проблем графика.
Одним популярным примером является сборка "мусора".
Коллектор запускается с ряда ссылок, затем пересекает все объекты, на которые они ссылаются, затем все объекты, на которые ссылаются там и так далее. Все это находки добавляется в график достижимых объектов. Все другие объекты недостижимы и собраны.
Ну, много алгоритмов оптимизации программы, что использование компиляторов основано на графиках (например, выясните граф вызовов, управление потоком, большой статический анализ).
Много проблем оптимизации основаны на графике. Так как много проблем приводимы к окраске графика и подобным проблемам, затем многими другими проблемами является также базирующийся график.
Я не уверен, что соглашаюсь, что графики являются лучшим способом представить каждое отношение, и я, конечно, стараюсь избегать, они "получили гвоздь, давайте найдем молоток" подходами. Графики часто имеют плохие представления памяти, и много алгоритмов на самом деле более эффективны (на практике) при реализации с матрицами, bitsets, и другими вещами.
Ваш исходный код является деревом, структурированным, и дерево является типом графика. Каждый раз, когда Вы слышите, что люди говорят о AST (Абстрактное синтаксическое дерево), они говорят о своего рода графике.
Указатели формируют структуры графика. Что-либо, что обходит указатели, делает некоторое управление графиком.
Сеть является огромным ориентированным графом. Ключевое понимание Google, которое привело их доминировать в поиске, то, что структура графика сети имеет сопоставимое или большее значение, чем текстовое содержание страниц.
Конечные автоматы являются графиками. Конечные автоматы используются в сетевых протоколах, регулярных выражениях, играх и всех видах других полей.
Довольно трудно думать о чем-либо, что Вы делаете, который не включает своего рода структуру графика.
Пример большинство людей знаком: системы сборки. Сделайте типичный пример, но почти любая хорошая система сборки полагается на Направленный Граф без петель. Основная идея состоит в том, что направление моделирует зависимость между источником и целью, и необходимо "обойти" график в определенном порядке создать вещи правильно-> это - пример топологического вида.
Другим примером является система управления исходным кодом: снова на основе DAG. Это используется для слияния, например, для нахождения общего родителя.
Компьютерные сети: модель Графиков интуитивно образцовые компьютерные сети и Интернет. Часто узлы будут представлять оконечные системы или маршрутизаторы, в то время как края представляют соединения между этими системами.
Структуры данных: Любая структура данных, которая использует указатели для соединения данных, использует график некоторого вида. Это включает древовидные структуры и связанные списки, которые используются все время.
Соединение каналом и Карты: Попытка найти самые короткие или самые длинные пути от некоторого местоположения до места назначения использует графики. Это может включать соединение каналом как Вы, посмотрите в приложении как карты Google или вычислении путей для символов AI для взятия в видеоигре и многих других подобных проблемах.
Ограничительная Удовлетворенность: типичная проблема в AI состоит в том, чтобы найти некоторую цель, которая удовлетворяет список ограничений. Например, чтобы Университет установил, это - расписания курса, это должно удостовериться, что определенные курсы не конфликтуют, что преподаватель не ведет два курса одновременно, что лекции происходят в течение определенных временных интервалов и так далее. Ограничительные проблемы удовлетворенности как это часто моделируются и решили графики использования.
Молекулы: Графики могут привыкнуть к образцовым атомам и молекулам для изучения их взаимодействия и структуры среди прочего.
IMHO most of the domain models we use in normal applications are in some respect graphs. Already if you look at the UML diagrams you would notice that with a directed, labeled graph you could easily translate them directly into a persistence model. There are some examples of that over at Neo4j
Cheers
/peter
Я очень интересуюсь теорией графов, и я использовал ее для решения множества различных проблем. Вы можете решить множество проблем, связанных с путями, проблемами сопоставления, проблемами структуры, используя граф.
Проблемы с путями имеют множество приложений.
Это было в вопросе интервью для кубка карьеры. Скажем, вы хотите найти самую длинную сумму подмассива. Например,
[1, 2, 3, -1]имеет самую длинную сумму из 6. Смоделируйте его как направленный ациклический граф ( DAG ), добавьте фиктивный источник, фиктивный пункт назначения. Соедините каждый узел ребром, вес которого соответствует номеру. Теперь используйте алгоритм Longest Path в группе DAG для решения этой проблемы.Аналогичным образом, проблемы арбитража в финансовом мире или даже проблемы геометрии поиска самой длинной перекрывающейся структуры - это аналогичная проблема пути.
Некоторыми очевидными из них могут быть сетевые проблемы (где в вашей сети могут быть компьютеры людей, организационные схемы и т. д.)
Вы можете почерпнуть много структурной информации , например- , какая точка разбивает график на две части
- как лучше всего их соединить
- как лучше всего добраться до одного места, чтобы еще
- есть способ добраться до одного места из другого и т. д.
Я решил множество проблем, связанных с управлением проектами , с помощью графов. Последовательность событий можно представить в виде ориентированного графа (если у вас нет циклов, то это даже лучше). Итак, теперь вы можете
- отсортировать события по их приоритету
- вы можете найти событие, которое является наиболее важным (которое освободило бы множество других проектов)
- вы можете найти продолжительность, необходимую для решения общий проект (проблема пути) и т. д.
Многие проблемы сопоставления могут быть решены с помощью графа. Например, если вам нужно сопоставить процессоры с рабочей нагрузкой или сопоставить рабочих с их работой. На последнем экзамене мне пришлось подбирать людей к столикам в ресторанах. Он следует тому же принципу (двустороннее соответствие -> алгоритмы сетевого потока). Его простой, но мощный.
Специальный граф, дерево , имеет множество приложений в мире компьютерных наук. Например, в синтаксисе языка программирования или в структуре индексации базы данных.
Совсем недавно я также использовал графики в задачах оптимизации компилятора . Я использую Книгу Моргана, которая учит меня увлекательным техникам.
Список действительно можно продолжать и продолжать. Графы - это красивая математическая абстракция для отношения . Вы действительно можете творить чудеса, если сможете правильно его смоделировать. А поскольку теория графов нашла так много приложений, в этой области ведется много активных исследований. А благодаря многочисленным исследованиям мы видим еще больше приложений, которые подпитывают исследования.
Если вы хотите начать изучать теорию графов, возьмите хорошую книгу по дискретной математике для начинающих (мне на ум приходит Розен ), и вы можете купить книги таких авторов, как Фулд или Даже . CLRS также имеет хорошие алгоритмы графов.
и вы можете покупать книги у таких авторов, как Фулд или Эвен . CLRS также имеет хорошие алгоритмы графов. и вы можете покупать книги у таких авторов, как Фулд или Эвен . CLRS также имеет хорошие алгоритмы графов.Шаблоны не способны делать такие вещи. Цель состоит в том, чтобы предотвратить вам возможность вносить вашу деловую логику в шаблоны, которые предназначены для решения только с макетом.
Таким образом, возможно, возможный способ сделать это - это определить функцию рассылки NewsletterPathLastelement (Self) в вашей модели информационной рассылки, и вызовите это из шаблона.
-121--3842670-Социальные связи между людьми делают интересный пример графа. Я пытался моделировать эти соединения на уровне базы данных, используя традиционные RDM, но слишком сильно нашел. Я закончил выбрать диаграмму базы данных, и это был отличный выбор, потому что он позволяет легко следовать соединениям (ребрам) между людьми (узлами).
Можно посмотреть некоторые примеры в вики Neo4j,
и проекты, в которых Neo4j используется (известные)
В противном случае, алгоритмы Рекомендаторов хорошо подходят для графиков, см. например PageRank, и другие материалы на
Анализ транзакции сериализуемости в теории баз данных.
Все, что может быть смоделировано как внешний ключ в реляционной базе данных, по сути, является ребром и узлами в графе.
Возможно, это поможет вам придумать примеры, поскольку большинство вещей легко моделируются в РСУБД.