Jaké problémy mohou být vyřešeny, nebo řeší snadněji, pomocí grafů a stromy?

hlasů
10

Jaké jsou nejčastější problémy, které lze řešit s oběma těmito datovými strukturami?

Bylo by dobré pro mě mají také doporučení týkající se knih, které:

  • Implementovat struktur
  • Implementovat a vysvětlit úvahy algoritmů, které je využívají
Položena 06/08/2008 v 01:56
zdroj uživatelem
V jiných jazycích...                            


10 odpovědí

hlasů
16

První věc, kterou jsem přemýšlet o tom, když jsem si přečetl tato otázka zní: jaké typy věcí, pomocí grafů / stromy? a pak myslím, že zpět k tomu, jak bych je mohl použít.

Například, vzít dvě běžné využití stromu:

  • DOM
  • souborové systémy

DOM, a XML na to přijde, se podobají stromových struktur.
alt textu

To dává smysl, taky. To dává smysl, protože o tom, jak je třeba tyto údaje, které mají být uspořádány . Souborový systém, taky. V systému UNIX je tu kořen, a větvení dole. Při montáži nové zařízení, budete jej připojíte do stromu.

Ty by měly být také ptát sami sebe: Má data spadají do tohoto typu konstrukce? Vytvoření datové struktury, které mají smysl k problému a zbytek bude následovat.

Pokud jde o bytí snadnější, myslím, že to je relativní. Jste dobří s rekurzivních funkcí, které procházejí stromovou / graf? Co když je potřeba vyvážit strom?

Přemýšlet o program, který řeší slovo hledání puzzle. Dalo by se zmapovat všechna písmena slova hledání do grafu a nechte okolní uzlů aby zjistili, zda tento řetězec odpovídající některý ze slov. Ale nemohl si prostě udělat to samé s jediným polem? Vše, co opravdu potřebujete udělat, je přesunout index pro kontrolu dopisy vlevo a vpravo, a šířkou pro kontrolu nad a pod písmeny. Vyřešení tohoto problému s grafem není obtížné, ale může vytvořit spoustu práce navíc a obtíže, pokud nejste spokojeni s jejich použití - samozřejmě, že by se vám nemělo odradit od dělat to, zvláště pokud se učíte o jim.

Doufám, že vám pomůže přemýšlet o těchto struktur. Pokud jde o doporučení knihy, musel bych jít s Úvod do algoritmů .

Odpovězeno 06/08/2008 v 02:28
zdroj uživatelem

hlasů
4

Schémata.

Kompilace (Síťové grafy)

Mapy. Velmi kompaktní jako grafy.

Problémy toku v síti.

Rozhodovací stromy pro expertní systémy (sic)

Fishbone diagramy pro zjištění závad, proces zdokonalování, bezpečnostní analýzy. Za bonusové body, implementovat kód chyby zotavení jako objekty, které jsou na způsob rybí kosti diagram.

Odpovězeno 28/08/2008 v 04:29
zdroj uživatelem

hlasů
3

Jen asi každý problém může být re-psaný v podmínkách teorie grafů. Nedělám si legraci, podívejte se na jakoukoli knihu o NP úplných problémů, tam jsou některé docela nezvyklé problémy, které dostanete se změnil na teorie grafů, protože máme dobré nástroje pro práci s grafy ...

Odpovězeno 09/03/2009 v 14:54
zdroj uživatelem

hlasů
2

Algoritmus design Manuál obsahuje některé zajímavé případové studie s tvůrčím využitím grafů. Navzdory svému názvu kniha je velmi čitelný, a dokonce i zábavné občas.

Odpovězeno 12/08/2008 v 21:59
zdroj uživatelem

hlasů
1

Hry často používají grafy s cílem usnadnit hledání cest po celém herním světě. Graf reprezentace na světě může mít algoritmy, jako je vyhledávání do šířky nebo A * s cílem najít cestu přes to.

Oni také často používají stromy představují subjekty ve světě. Máte-li tisíce subjektů a je třeba najít ten, v určité poloze pak iteraci lineárně přes seznamu může být neefektivní, zvláště pokud potřebujete na to často. Proto oblast lze rozdělit do stromu, aby mohl být prohledány mnohem rychleji. Stejně jako lineární prostor lze efektivně prohledávat s binární vyhledávání (a tedy rozdělen do binárního stromu), 2D prostor lze rozdělit do QuadTree a 3D prostoru do octree .

Odpovězeno 01/07/2010 v 12:11
zdroj uživatelem

hlasů
1

Stromy jsou používány mnohem více ve funkcionálních programovacích jazyků, protože jejich rekurzivní povahu.

Také, grafy a stromy jsou dobrý způsob, jak modelovat mnoho problémů AI.

Odpovězeno 09/03/2009 v 14:25
zdroj uživatelem

hlasů
1

@DavidJoiner / all:

FWIW: nová verze Algoritmus Design Manual je každým dnem kvůli ven.

Celý kurz, který mu Prof Skiena vyvinul tuto knihu je rovněž k dispozici na webu:

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

Odpovězeno 27/08/2008 v 00:56
zdroj uživatelem

hlasů
1

Scéna grafy pro kreslení grafiky ve hrách a multimediálních aplikací silně použít stromy a grafy. Uzly reprezentuje objekty, které mají být poskytnuty, transformace, ovládací prvky, skupiny, ...

Scéna grafy obvykle mají několik vrstev a atributů, které znamená, že můžete čerpat pouze některé uzel grafu (atributů) v určeném pořadí (vrstev). V závislosti na typu grafu scény máte může mít dvě parralel struktury: prohlášení a instance. th

Odpovězeno 08/08/2008 v 16:58
zdroj uživatelem

hlasů
1

Algoritmy pro Javu: Část 5 Robert Sedgewick je o grafové algoritmy a datové struktury. To by byl dobrý první kniha k práci, pokud chcete realizovat některé grafových algoritmů.

Odpovězeno 08/08/2008 v 16:46
zdroj uživatelem

hlasů
1

K dispozici je hřiště pro takové věci v mé univerzity: CSE 326 . Nemyslel jsem si, že kniha byla příliš užitečná, ale projekty jsou zábavné a naučí vás je dost o kterou se provádějí některá jednodušších struktur.

Pokud jde o příklady, jeden z nejčastějších problémů (podle počtu lidí, kteří ji využívají), který je řešen stromů je to zadávání textu mobilních telefonů. Můžete použít stromy, ne nutně binární reprezentovat prostor možných slov, která může pocházet z jakéhokoli daného seznamu čísel, která uživatel údery na velmi rychle.

Odpovězeno 06/08/2008 v 02:18
zdroj uživatelem

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