[Alg] Breadth-first-search in n dimensies *

[Verwijderd]

Konichi-wa (ik bevind me momenteel in Japan)
Ik ben bezig met een specifiek probleem waarin ik een graaf doorzoek met een BFS methode. Het probleem is op dit moment een 'obstacle avoidance' in twee dimensies.
De bedoeling is dat ik een algemene oplossing vind voor dat probleem. Daarvoor moet ik dus uiteindelijk een n-dimensionale graaf doorzoeken.
Is er iemand die hier al eens mee gewerkt heeft.
Dit is geen script request oid. Ik wil gewoon even wat meningen of ervaringen horen.

[mbravenboer]

Wat versta je onder een n-dimensionale graaf?

[Juup]

Dat is nou irritant. Dan opent iemand een topic om stoer te doen en vervolgens post 'ie er niet meer in.
Bij deze een oproep: Als je een topic opent, LEES em dan regelmatig en beantwoord de vragen van ehhh... ons.

[Grijze Vos]

Give him a break. Hij zit in Japan, en heeft vast limited internet access.

On-topic:
Je moet toch ergens gedefinieerd hebben wat de onderlinge relaties zijn tussen de 'punten' in je graaf. Ik neem aan dat je nu relateert met je twee dimensies naar een vlak, met aaneengesloten punten. daarbij geld de relatie X,Y > X,Y+1 en X,Y > X,Y-1 etc etc...

Een graaf is normaliter een hoopje punten die verbonden zijn met elkaar (een relatie hebben met elkaar). Kortom, sluit ik me aan bij mbravenboer, wat is bij jou precies een n-dimensionale graaf?

[Verwijderd]

Juup schreef op 13 October 2003 @ 01:28:
Dat is nou irritant. Dan opent iemand een topic om stoer te doen en vervolgens post 'ie er niet meer in.
Bij deze een oproep: Als je een topic opent, LEES em dan regelmatig en beantwoord de vragen van ehhh... ons.

Ik zit in Japan, daar is het 7 uur later, en helaas heb ik mijn slaap ook nodig.
Als je het irritant vindt kun je misschien beter niet reageren .

Dat is juist het probleem, wat is een n-dimensionale graaf. En hoe definieer je die. Het zou een soort grid in een n-dimensionale ruimte moeten worden. Er is trouwens alleen afhankelijkheid tussen direct aangrenzende punten.

Ik denk dat ik elke dimensie in een aparte rij moet opslaan en daar een index aan moet verbinden, aan de hand van die indexen moet dan duidelijk zijn welke punten grenzen aan mijn huidige punt. Nog een voordeel is dat ik alleen maar aan een kant van mijn punt hoef te zoeken (dus niet in alle richtingen). Eigenlijk is het dus meer een soort boom.
In een 2d situatie heeft een punt dus 3 buurpunten:
zoiets dus (met startpunt O):

code:

         O

X        X         X

In een 3D situatie heb ik dus 5 buurpunten.
Dan heb ik er in een 4D situatie 7 zou ik denken (2n-1).
Dat is het probleem, ik kan er geen tekeningetje van maken en kijken of mijn veronderstelling klopt. Heeft er iemand ideeen om zoiets te onderbouwen.

[RickN]

In een graaf heb je alleen te maken met nodes (knopen) en edges (kanten), daar heb je dus helemaal niks met dimensies te maken. Aan een knoop kun je een label hangen waarin je b.v. coördinaten in een 3-dimensionale ruimte opslaat, maar dat is maar een label en dat is voor de graaf an sich volledig irrelevant.
Er zijn legio methoden om de nodes en edges van een graaf efficient op te slaan, elk met hun eigen voordelen, b.v. een adjacency matrix. Ook is er een mooie uitbreiding op de STL waarmee je grafen kunt modeleren en waarbij de meest standaard algorithmen al voor je zijn geimplementeerd.

[ Voor 4% gewijzigd door RickN op 13-10-2003 09:28 ]

[Verwijderd]

Ik zal er eens na kijken, bedankt.

[Apollo_Futurae]

Verwijderd schreef op 13 October 2003 @ 05:01:
In een 2d situatie heeft een punt dus 3 buurpunten:
zoiets dus (met startpunt O):

code:

         O

X        X         X

In een 3D situatie heb ik dus 5 buurpunten.
Dan heb ik er in een 4D situatie 7 zou ik denken (2n-1).
Dat is het probleem, ik kan er geen tekeningetje van maken en kijken of mijn veronderstelling klopt. Heeft er iemand ideeen om zoiets te onderbouwen.

Hm, ik weet niet zeker of ik begrijp wat je bedoelt. Jouw voorbeeld in dimensie 2 generaliserend, zou ik op zoiets uitkomen:

dimensie 1:

code:

O

X

dimensie 2:

code:

  O

X X X

dimensie 3:

code:

bovenaanzicht:
X X X
X O X
X X X
zij-aanzicht:
  O
X X X
onderaanzicht:
X X X
X X X
X X X

dus voor dimensie n heeft een parent 3^(n-1) childs.

Als dit niet is wat je bedoelt, mag je dit negeren .

[Verwijderd]

Dat zou ook kunnen. Ik was zelf meer aan het volgende aan het denken in de 3d situatie.

code:

Bovenaanzicht:
 X
XOX
 X

Onderaanzicht:
 X
XXX
 X

Het is maar waar je voor kiest. Maar klopt die 2n-1 reeks dan wel?

[Grijze Vos]

Je moet echt je wiskundige definities eens opschroeven, want wat je bedoelt is dus helemaal geen graaf. Alhoewel je het wel zou kunnen representeren als een graaf of boom. (Boom lijkt me makkelijker btw.)

Maar goed, welke info heb je over deze punten? Ik neem aan dat je co-ordinaten hebt in de n-dimensionele ruimte? Als je dat hebt, kun je toch formuleren welke punten buurpunten zijn, zeker als dit maar in bepaalde richtingen zo is en 'diagonalen' niet mogen. Dan ist een kwestie van:
in 3 dimensies met A(X,Y,Z). Dan geldt er dat B een child is van A als B(X+1,Y,Z) of B(X,Y+1,Z) of B(X,Y,Z+1).

Als je een boom aanlegt, dan abstraheer je je 'punten' tot een iets complexer object, en voeg je nog een 'parent-veld' toe i.c.m. de wiskundige regels die je hebt opgesteld om te bepalen wat een child is van wie kun je makkelijk een boom creeren. Deze boom is dan ook gelijk breadth-first te maken lijkt me...

Als je dit niet helemaal volgt wat ik hier heb gepost, wil ik mijn verhaal best wel op een andere manier proberen te verduidelijken. Ik kan me voorstellen dat mijn verhaal niet zo mega helder is

[Apollo_Futurae]

Verwijderd schreef op 15 October 2003 @ 12:05:
Het is maar waar je voor kiest. Maar klopt die 2n-1 reeks dan wel?

Dan klopt 2n-1 inderdaad. Maar precies zoals je zegt: het is maar waar je voor kiest. Wij kunnen zonder verdere informatie onmogelijk bepalen hoe jouw gegevens gerepresenteerd moeten worden.

[Verwijderd]

Grijze vos, dat is inderdaad the way to do it. Ik ben pas begonnen aan mijn stage en hoe de boom er precies uit gaat zien weet ik nog niet helemaal. Het maakt in ieder geval niet uit in welke dimensie je werkt, je kunt je punten immers zelf een index geven. Of die index nu bestaat uit 2, 3 of n getallen maakt niet zoveel uit. Ik heb geen ervaring met graphs en zoekalgoritmen. Vandaar dit topic. Ik denk dat ik er nu prima uit ga komen. Als het gewenst is kan ik mijn uiteindelijke bevindingen hier wel posten.
Iig bedankt voor de reacties allemaal!