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

голоса
10

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

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

  • Реализовать структуры
  • Реализовать и объяснить рассуждения алгоритмов, которые используют их
Задан 06/08/2008 в 01:56
источник пользователем
На других языках...                            


10 ответов

голоса
16

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

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

  • DOM
  • Файловые системы

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

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

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

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

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

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

Ответил 06/08/2008 d 02:28
источник пользователем

голоса
4

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

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

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

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

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

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

Ответил 28/08/2008 d 04:29
источник пользователем

голоса
3

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

Ответил 09/03/2009 d 14:54
источник пользователем

голоса
2

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

Ответил 12/08/2008 d 21:59
источник пользователем

голоса
1

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

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

Ответил 01/07/2010 d 12:11
источник пользователем

голоса
1

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

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

Ответил 09/03/2009 d 14:25
источник пользователем

голоса
1

@DavidJoiner / всего:

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

Весь курс, что он профессор Skiena разработал эту книгу также можно найти на веб-сайте:

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

Ответил 27/08/2008 d 00:56
источник пользователем

голоса
1

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

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

Ответил 08/08/2008 d 16:58
источник пользователем

голоса
1

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

Ответил 08/08/2008 d 16:46
источник пользователем

голоса
1

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

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

Ответил 06/08/2008 d 02:18
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more