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

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

Для меня было бы хорошо иметь рекомендации по книгам, которые:

  • Реализуйте структуры
  • Реализуйте и объясните обоснование алгоритмов, которые их используют
6.08.2008 00:56:05
10 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

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

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

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

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

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

17
28.03.2012 22:21:18

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

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

1
6.08.2008 01:18:12

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

1
8.08.2008 15:46:05

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

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

1
8.08.2008 15:58:36

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

2
12.08.2008 20:59:54

@DavidJoiner / all:

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

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

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

1
26.08.2008 23:56:47

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

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

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

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

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

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

4
28.08.2008 03:29:30

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

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

1
9.03.2009 13:25:49

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

3
9.03.2009 13:54:37

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

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

1
1.07.2010 11:11:32