Vă mulțumim pentru susținere

Ce probleme pot fi rezolvate sau rezolvate mai ușor, folosind grafice și copaci?

Care sunt cele mai frecvente probleme care pot fi rezolvate cu ambele structuri de date?

Ar fi bine pentru mine să am recomandări și pentru cărți care:

  • Implementați structurile
  • Implementați și explicați raționamentul algoritmilor care le utilizează
0
adăugat editat

9 răspunsuri

Primul lucru la care mă gândesc atunci când citesc această întrebare este: ce tipuri de lucruri folosesc grafice / arbori? și apoi mă gândesc înapoi la modul în care i-aș putea folosi.

De exemplu, luați două utilizări comune ale unui copac:

  • DOM
  • Sisteme de fișiere

The DOM, and XML for that matter, resemble tree structures.
alt text

Are sens, de asemenea. Are sens din cauza modului în care trebuie aranjate aceste date . Și un sistem de fișiere. Pe un sistem UNIX există un nod rădăcină și ramificat mai jos. Când montați un dispozitiv nou, îl atașați pe copac.

De asemenea, ar trebui să vă întrebați: datele cad în acest tip de structură? Creați structuri de date care să aibă sens la problemă, iar restul va urma.

În ceea ce privește ușurarea, cred că este relativă. Ești bun cu funcțiile recursive pentru a traversa un copac / grafic? Ce se întâmplă dacă trebuie să echilibrezi copacul?

Gândiți-vă la un program care rezolvă un puzzle de căutare de cuvinte. Puteti harta tuturor literelor cuvantului de cautare intr-un graf si verificati nodurile inconjuratoare pentru a vedea daca sirul corespunde oricarei cuvinte. Dar nu ai putea să faci același lucru cu o singură matrice? Tot ce trebuie să faceți este să mutați un index pentru a verifica literele la stânga și la dreapta și la lățimea pentru a verifica literele de mai sus și de mai jos. Rezolvarea acestei probleme cu un grafic nu este dificilă, dar poate crea o mulțime de lucruri suplimentare și dificultăți dacă nu vă simțiți bine să le folosiți - desigur că nu ar trebui să vă descurajeze să o faceți, mai ales dacă învățați despre lor.

Sper că vă ajută să vă gândiți la aceste structuri. În ceea ce privește o recomandare de carte, trebuie să merg cu Introducere în algoritmi .

0
adăugat

Scenele grafice pentru desenarea grafică în jocuri și aplicații multimedia folosesc foarte mult copaci și grafice. Nodurile reprezintă obiecte care trebuie redate, transformări, controale, grupuri, ...

Diagramele grafice au de obicei mai multe straturi și atribute, ceea ce înseamnă că puteți desena doar un nod al unui grafic (atribute) într-o ordine specificată (straturi). În funcție de tipul graficului pe care îl aveți, acesta poate avea două structuri paralerale: declarații și instanțiere. Th

0
adăugat

Există un curs pentru astfel de lucruri la universitatea mea: CSE 326 . Nu credeam că cartea a fost prea utilă, dar proiectele sunt distractive și vă învață un pic despre punerea în aplicare a unor structuri mai simple.

Ca de exemplu, una dintre cele mai frecvente probleme (prin numărul de persoane care o utilizează) care este rezolvată cu copaci este cea a introducerii textului telefonului mobil. Puteți folosi copaci, nu neapărat binare, pentru a reprezenta spațiul posibilelor cuvinte care pot ieși din orice listă de numere pe care un utilizator o loveste foarte repede.

0
adăugat

The Algorithm Design Manual contains some interesting case studies with creative use of graphs. Despite its name, the book is very readable and even entertaining at times.

0
adăugat

Aproximativ fiecare problemă poate fi re-scris în termeni de teorie grafică. Nu glumesc, uita-te la orice carte despre NP probleme complete, există unele probleme destul de wacky care se transformă în teoria grafului, deoarece avem instrumente bune pentru a lucra cu grafice ...

0
adăugat

Copacii sunt folosiți mult mai mult în limbile de programare funcțională din cauza naturii lor recursive.

De asemenea, graficele și arborii reprezintă o modalitate bună de a modela o mulțime de probleme de AI.

0
adăugat

Jocurile utilizează adesea grafice pentru a facilita găsirea căilor în lumea jocurilor. Reprezentarea grafică a lumii poate avea algoritmi, cum ar fi căutarea pe lățimea primei pagini sau A *, pentru a găsi un traseu peste el.

De asemenea, adesea folosesc copaci pentru a reprezenta entități din lume. Dacă aveți mii de entități și trebuie să găsiți unul într-o anumită poziție, iterarea liniară printr-o listă poate fi ineficientă, mai ales dacă trebuie să o faceți deseori. Prin urmare, zona poate fi împărțită într-un copac pentru a permite ca aceasta să fie căutată mai repede. La fel cum un spațiu liniar poate fi căutat eficient cu o căutare binară (și astfel împărțită într-un copac binar), spațiul 2D poate fi împărțit într-un spațiu quadtree și spațiul 3D într-un octree .

0
adăugat

Diagrame de circuite.

Compilație (grafice direcționate aciclice)

Hărți. Foarte compact ca grafice.

Probleme privind fluxul de rețea.

Decizia arbori pentru sisteme expert (sic)

Diagrame de pește pentru identificarea defecțiunilor, îmbunătățirea procesului, analiza siguranței. Pentru punctele bonus, implementați codul de recuperare a erorilor ca obiecte care sunt diagrama de pește.

0
adăugat

@DavidJoiner / toate:

FWIW: O nouă versiune a Manual de proiectare al algoritmului se va desfășura în orice zi.

Întregul curs pe care Prof Skiena la dezvoltat pentru această carte este, de asemenea, disponibil pe web:

http://www.cs.sunysb.edu/~ algorith / video-conferințe / 2007-1.html

0
adăugat