Какие проблемы можно решить с большей легкостью, используя графики и деревья?[закрыто]

Question

Каковы наиболее распространенные проблемы, которые могут быть решены с помощью обеих этих структур данных?

Было бы хорошо, если бы у меня были также рекомендации по книгам, которые:

• Внедрять структуры
• Реализуйте и объясняйте логику алгоритмов, которые их используют

Answer 1

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

Например, возьмем два распространенных варианта использования дерева:

• ДОМ
• Файловые системы

DOM и XML, если уж на то пошло, напоминают древовидные структуры.

В этом тоже есть смысл. Это имеет смысл из-за того, как эти данные должны быть упорядочены.И файловая система тоже.В системе UNIX есть корневой узел и ветвление ниже.Когда вы монтируете новое устройство, вы прикрепляете его к дереву.

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

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

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

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

Answer 2

Принципиальные схемы.

Компиляция (направленные ациклические графы)

Карты.Очень компактен, как графики.

Проблемы с сетевым потоком.

Решение деревья для экспертных систем (sic)

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

Answer 3

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

Answer 4

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

Answer 5

В моем университете есть курс для таких вещей: CSE 326.Я не думал, что книга была слишком полезной, но проекты - это весело, и они научат вас кое-чему о реализации некоторых более простых структур.

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

Answer 6

Алгоритмы для Java:Часть 5 автор: Роберт Седжвик - все о графовых алгоритмах и структурах данных.Это была бы хорошая первая книга для работы, если вы хотите реализовать некоторые графовые алгоритмы.

Answer 7

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

Графики сцен обычно имеют несколько слоев и атрибутов, что означает, что вы можете нарисовать только некоторый узел графика (атрибуты) в указанном порядке (слои).В зависимости от типа графика сцены, который у вас есть, он может иметь две параллельные структуры:объявления и создание экземпляров.Че

Answer 8

@DavidJoiner / все:

FWIW:Новая версия Руководство по разработке алгоритма должен выйти со дня на день.

Весь курс, для которого профессор Шиена разработал эту книгу, также доступен в Интернете:

http://www.cs.sunysb.edu /~algorith/video-lectures/2007-1.html

Answer 9

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

Кроме того, графики и деревья - хороший способ моделировать множество проблем искусственного интеллекта.

Answer 10

Игры часто используют графики, чтобы облегчить поиск путей по игровому миру.Графическое представление мира может содержать такие алгоритмы, как поиск в ширину или A *, чтобы найти маршрут по нему.

Они также часто используют деревья для представления сущностей внутри мира.Если у вас есть тысячи объектов и вам нужно найти один в определенной позиции, то линейная итерация по списку может быть неэффективной, особенно если вам нужно делать это часто.Таким образом, область может быть разделена на дерево, чтобы обеспечить более быстрый поиск.Точно так же, как линейное пространство может быть эффективно найдено с помощью двоичного поиска (и, таким образом, разделено на двоичное дерево), 2D-пространство может быть разделено на квадратное дерево и трехмерное пространство в восьмиугольник.