Algoritme opgave

Det er en opgave i programmeringsalgoritmer, som du også har kørende her

https://www.studieportalen.dk/forums/thread.aspx?id=1463906

Men er der nogle som er gode til algoritmer, og kan komme med et godt hint til nogle af opgaverne, ville jeg sætte stor pris på det.

#3

Opg 1 er vel forholdsvis simpel. Man skal bare steppe gennem gitteret og tælle op, hvor mange gange man finder "G".

I Opg 2 skal man for hvert spøgelse G undersøge, om der er en fri vej fra G til P.

Selve opgaverne er simple nok ja, det er mere hvordan man skal formulerer det som en god algoritme, jeg ikke er helt sikker på.

#5

Hvd har du lavet indtil videre?

Har i opgave 1.1 skrevet at man bare kan køre banen igennem som et array på størrelse n*n, hvor man kører hver række igennem. Hvis der er et P har et index kan vi tælle en ghostcount op indtil arrayet ikke indeholder flere pladser.

Det må nødvendigvis have en køretid på O(n²)

Implementeringen er jeg ikke begyndt på endnu

I opgave 2 har jeg en ide om noget BFS søgning som en uorienteret graf.

Er jeg nogenlunde på rette vej?

#7

Du skal vel lave en algoritme, der undersøger, om to punkter (x1,y1) og (x2,y2) kan forbindes ved en fri vej i gitteret, og som i bekræftende fald beregner den korteste vej mellem punkterne.

giver lidt mere mening kan jeg godt se, så kunne man evt. formulere en algoritme der siger at hvis man følger en vej i gittet for et startpunkt for P, hvor ens naboer ikke er # eller allerede besøgte naboer, kan man finde et punkt som ikke er besøgt endnu. Hvis den frie plads i gitteret er et G, er der en sti mellem spøgelse og pacman

eller det vil nok være mere fornuftigt at vælge et startpunkt for et spøgelse og så søge efter P

#10

Lav en algoritme som beskrevet i #8 og benyt den på hver kombination (G,P) i det forelagte gitter.

Jeg har nu lavet opgave 1, og har skrevet følgende algoritme til opgave 2.1, hvilket jeg håber nogen vil kommentere, gerne med kritikpunkter hvis noget fremstår uklart eller forvirrende:

Svar:

Følgende betingelser skal opfyldes for en sti, hvis et spøgelse skal kunne fange Pacman:

Der er en startknudeknude (felt) af typen G og en slutknude P
Grafen er sammenhængende, idet at spøgelser og Pacman ikke kan hoppe mere end én nabo ad gangen og naboen skal være lige over, nedenunder, til højre eller til venstre for den selv.
Der kan ikke findes en vej, hvor # er en knude i denne.

I en BFS søgning markeres alle besøgte knuder med farver for at skelne mellem knuder som er besøgt og knuder som ikke er besøgt. Vi kalder vores nuværende knude for i og vi undersøger nu dets naboer i hver iteration og om der er en kant mellem knuderne. Hvis en naboknude har farven sort, har knuden allerede været besøgt, eller også er det en væg og skal derfor ikke besøges.

Algoritmen bliver som følger:

Kør BFS med de ekstra forbehold som beskrevet ovenover.
Kør en iteration over alle knuder og kontroller om de er blevet besøgt tidligere i BFS.
Hvis en vej findes mellem G og P opdateres en optællingsværdi ghostCount, startende med 0.
Hvis en knudes naboknuder er markeret med sort, har disse været besøgt, eller er en væg, og derfor findes der ikke en vej mellem startknuden G og P.
Gentag proceduren for alle startknuder P.