Hvilke problemer kan løses, eller taklet lettere, ved hjelp av grafer og trær?

stemmer
10

Hva er de vanligste problemene som kan løses med begge disse datastrukturer?

Det ville være bra for meg å ha også anbefalinger om bøker som:

  • Implementere strukturene
  • Gjennomføre og forklare begrunnelsen av algoritmer som bruker dem
Publisert på 06/08/2008 klokken 00:56
kilden bruker
På andre språk...                            


10 svar

stemmer
16

Det første jeg tenker på når jeg leser dette spørsmålet er: hvilke typer ting bruke grafer / trær? og så tenker jeg bakover til hvordan jeg kunne bruke dem.

For eksempel ta to vanlige bruk av et tre:

  • DOM
  • filsystemer

DOM og XML for den saks skyld, ligner trestrukturer.
alt tekst

Det er fornuftig, også. Det er fornuftig på grunn av hvordan disse dataene må ordnes . Et filsystem, også. På et UNIX-systemet er det en rotnode, og forgrening ned nedenfor. Når du monterer en ny enhet, du feste den på treet.

Du bør også spørre deg selv: Har dataene faller inn i denne type struktur? Opprett datastrukturer som gir mening til problemet og resten vil følge.

Så langt som å være lettere, tror jeg det er relativ. Er du flink med rekursive funksjoner for å krysse et tre / graf? Hva om du trenger å balansere treet?

Tenk på et program som løser et ord søk puslespill. Du kan kartlegge alle bokstavene i ordet søk i en graf og sjekke rundt knutepunkter for å se om den strengen er samsvar noen av ordene. Men kunne du ikke bare gjøre det samme med med en enkelt array? Alt du trenger å gjøre er å flytte en indeks for å sjekke bokstaver til venstre og høyre, og ved bredden for å sjekke over og under bokstavene. Å løse dette problemet med en graf er ikke vanskelig, men det kan skape mye ekstra arbeid og problemer hvis du ikke er komfortabel med å bruke dem - selvfølgelig som ikke bør hindre deg fra å gjøre det, spesielt hvis du lærer om dem.

Jeg håper det hjelper deg tenke på disse strukturene. Som for en bok anbefaling, jeg må gå med Introduksjon til algoritmer .

Svarte 06/08/2008 kl. 01:28
kilden bruker

stemmer
4

Koblingsskjemaer.

Sammenstillingen (Directed asykliske grafer)

Maps. Svært kompakt som grafer.

Nettverk flow problemer.

Beslutningstrær for ekspertsystemer (sic)

Fiskebein diagrammer for feilsøking, fremgangsmåte for forbedringer, sikkerhetsanalyse. For bonuspoeng, implementere feilretting koden som objekter som er fiskebein diagram.

Svarte 28/08/2008 kl. 03:29
kilden bruker

stemmer
3

Omtrent alle problemer kan bli re-skrevet i form av grafteori. Jeg tuller ikke, se på noen bok om NP komplette problemer, er det noen ganske sprø problemer som blir omgjort til grafteori fordi vi har gode verktøy for å arbeide med grafer ...

Svarte 09/03/2009 kl. 13:54
kilden bruker

stemmer
2

Algoritmen Design Manual inneholder noen interessante case-studier med kreativ bruk av grafer. Til tross for navnet, er boken svært lesbar og selv underholdende til tider.

Svarte 12/08/2008 kl. 20:59
kilden bruker

stemmer
1

Spill bruker ofte grafer til rette for å finne stier over hele spillverdenen. Grafen representasjon av verden kan ha algoritmer som bredde-først-søk eller A * for å finne en rute over det.

De har også ofte bruke trær til å representere enheter i verden. Hvis du har tusenvis av enheter og trenger å finne en på en bestemt posisjon deretter itera lineært gjennom en liste kan være ineffektive, spesielt hvis du trenger å gjøre det ofte. Derfor området kan deles inn i et tre for å tillate det å bli søkte raskere. Bare som et lineært rom kan effektivt søkt med et binært søk (og således delt i et binært tre), kan 2D mellomrom deles inn i et firertre og 3D-rom inn i en octree .

Svarte 01/07/2010 kl. 11:11
kilden bruker

stemmer
1

Trær blir brukt mye mer i funksjonelle programmeringsspråk på grunn av sin rekursive natur.

Også grafer og trær er en god måte å modellere en rekke AI problemer.

Svarte 09/03/2009 kl. 13:25
kilden bruker

stemmer
1

@DavidJoiner / alle:

FWIW: En ny versjon av algoritmen Design Manual er grunn ut noen dager nå.

Hele kurset som han Prof Skiena utviklet denne boken for er også tilgjengelig på nettet:

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

Svarte 26/08/2008 kl. 23:56
kilden bruker

stemmer
1

Scenegraf for tegning grafikk i spill og multimedia applikasjoner tungt bruke trær og grafer. Noder betegner gjenstander som skal gjengis, transformasjoner, kontroller, grupper, ...

Scenegraf vanligvis har flere lag og egenskaper som gjør at man kan trekke bare noen node av en kurve (attributter) i en bestemt rekkefølge (lag). Avhengig av hva slags scene grafen har du det kan ha to parralel strukturer: erklæringer og oppretting. th

Svarte 08/08/2008 kl. 15:58
kilden bruker

stemmer
1

Algoritmer for Java: Del 5 av Robert Sedgewick handler om grafiske algoritmer og datastrukturer. Dette ville være et godt første bok å arbeide gjennom hvis du ønsker å gjennomføre noen grafalgoritmer.

Svarte 08/08/2008 kl. 15:46
kilden bruker

stemmer
1

Det er et kurs for slike ting på mitt universitet: CSE 326 . Jeg trodde ikke at boken var også nyttig, men prosjektene er gøy og lære deg en god del om å implementere noen av de enklere konstruksjoner.

Som for eksempel, er en av de vanligste problemene (etter antall personer som bruker det) som er løst med trær er at av mobiltelefon tekst. Du kan bruke trær, ikke nødvendigvis binære, å representere løpet av mulige ord som kan komme ut av en gitt liste med tall som en bruker slag i svært raskt.

Svarte 06/08/2008 kl. 01:18
kilden bruker

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