Алгоритмы обучения графику

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

Это языковой агностик, но я больше всего знаком с python и не имею большого опыта работы с FP.

Ответ 1

Оба они очень хороши:

Руководство по разработке алгоритмов
Алгоритмы в С++ Часть 5: Алгоритмы графиков (Не беспокойтесь о бит С++, также имеет псевдокод)

Бесплатный материал:

Глава 5. Графики и алгоритмы графа

Ответ 2

Стив Йегге говорит this - потрясающая книга об алгоритмах, в которых широко используются графики.

Ответ 3

Я много узнал о графиках из приведенной ниже книги... это одна из моих любимых книг: http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics
J. H. van Lint, R. M. Wilson
Cambridge University Press
ISBN 0 521 00601 5

Ответ 4

Я бы предположил, что когда вы изучаете какие-либо алгоритмы, тогда не думайте о его кодировании. Алгоритмы полностью математичны, и вы должны относиться к ним одинаково. Когда вы изучаете что-то вроде алгоритма Graph Spanner, не думайте, как его кодировать, как представлять их. Сначала оцените, почему алгоритм важен и нетривиальен. Затем попробуйте некоторые тривиальные решения и сравните их сложность. Далее посмотрите, как выглядят оптимальные решения и пытаются получить их свойства. Используйте бумагу и ручку, а не IDE, попробуйте вывести и доказать леммы и так далее. Затем, наконец, посмотрите, как вы можете написать псевдокод для решения проблемы. Если вы сделаете это, тогда вы разработаете интимное отношение к алгоритмам, и тогда вы обнаружите, что гораздо проще их решить, так как вы не думаете при кодировании, почему я это делаю.

К сожалению, из-за огромных требований к программисту программист сегодняшних дней не математик, и они сталкиваются с проблемами при решении новых проблем. Программистом предыдущих дней, такими как Дон Кнут, Макхарти были математики и хорошие исследователи. Следовательно, программист в настоящее время является относительно дешевым словом по сравнению с компьютерными учеными.

Ответ 5

Алгоритм Беллмана-Форда: Самый короткий путь от источника ко всем остальным узлам в взвешенном ориентированном графике даже с -евым весом кромки (а не циклом). медленнее, но универсальнее, чем Дийсктра. Сложность: O (| V |. | E |)

BFS: Найдите путь от одной заданной вершины к другим узлам в невзвешенном ненаправленном графе. Сложность: O (| V | + | E |). это быстрее, когда вы знаете вершины вперед и используете соответствующую структуру данных. iFeO Que для выяснения, какая уже обработанная вершина, чем сложность, может быть уменьшена до O (| V |)

DFS: Найдите самый короткий путь от источника к другим узлам. в дереве, а также в графе. График может содержать цикл, который означает, что node можно было бы посещать снова и снова. поэтому мы можем использовать логический массив для отслеживания посещенных узлов. иначе алгоритм не остановится. более того, он выглядит глубже и глубже и доходит до конца ветки дерева. Сложность: O (| V | + | E |). и Сложность: O (| V |) пространство для хранения вершин.

Алгоритм Floyed Warshal: Найти все парные кратчайшие пути в Направленный невзвешенный график с весом квеста eve, -eve (not cycle). но он не возвращает детали самих путей. он может быть использован для обнаружения -веса весового цикла в графе. когда он находит один, он заканчивается. он сравнивает весь возможный путь через график между каждой парой вершин. поэтому он использует динамический подход, а не жадный подход. Сложность: O (| V ^ 3 |)

Алгоритм Джонсона: найдите все пары кратчайшего пути в ориентированном взвешенном разреженном графике, когда вес края равен + eve, -eve, но не -eve cycle. он сначала использует алгоритм belman-ford для вычисления преобразованного графа из исходного графа. он удаляет -eve веса края. то Дейкстра применяется для поиска путей. Сложность: O (V ^ 2 Log V + VE)

Алгоритм Дейкстры: исходная версия этого алгоритма не использует Priority Que, поэтому сложность O (| V ^ 2 |), но более новая версия использует эту структуру данных, поэтому сложность становится O (E + V log V). и это более быстрый алгоритм кратчайшего пути с одним источником. он работает, назначая предварительный вес посетителю node и бесконечность для посещенных узлов для посещенных node ищет все его нераскрытые края и выбирает с минимальным весом. и добавьте его в набор путей.

Алгоритм Крушкала:, чтобы найти MST, где он обнаруживает край наименьшего возможного веса, который соединяет любые два дерева в лесу с ненаправленным взвешенным графиком. это жадный алгоритм. он также найдет минимальный опалубный лес. Сложность: O (E log V)

Алгоритм Prim: он находит подмножество ребер, которые образуют дерево на ненаправленном взвешенном графике. но не может найти MS Forest, как алгоритм Крушкала.

Алгоритм Brouvka: Проблема с этим алгоритмом заключается в том, что веса должны быть уникальными в графе. он находит MST, исследуя каждую вершину, а затем помещая ее с меньшим весом. этот алгоритм является параллельным по своей природе, но не быстрее, чем Prim Algorithm.

Такая же сложность, как алгоритм Крушкала.

Ответ 6

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