Hej

Jag har ett problem med lite modellering av ett problem.

Jag har en graf som ser ut såhär:

O--O--O--O--O
| X X X X |
O--O--O--O--O
| X X X X |
O--O--O--O--O
| X X X X |
O--O--O--O--O
| X X X X |
O--O--O--O--O

Dvs en matris där alla noder är förbundna med alla grannar.

Problemet:
Jag vill ha en lista på alla möjliga sätt att röra sig i grafen, med följande begränsningar:
- Man måste gå minst 3 steg.
- Man får inte gå till samma nod två gånger

Lösningen skall hälst vara så allmän att man även kan lägga till och plocka bort noder från modellen.

Det sätt jag hittills kommit på är följande:

Lotta sig igenom grafen till dess att man borde ha gått igenom alla möjliga sätt. Dock kommer detta troligen ta rätt lång tid och kommer ändå inte vara helt säkert.

Tacksam om någon skulle vilja hjälpa mig.

I princip ser jag nog ingen annan möjlig lösning än en sk uttömmande sökning (gå igenom allt). Det är ju dock otroligt segt. Om det alltid är just "fyrkanter", etc., så kan du skapa lite mer generella lösningar för de som ligger mer än 3 noder från kanten (alla får exakt samma utseende).

Faktum är att du kan få ett antal 5*5 matriser som agerar mallar, utifrån vilka du kan utgå, men det kräver ganska stora grafer för att vara meningsfullt. Har du hyfsat reguljära eller hyfsat stora grafer så skulle jag nog satsa på den iden

Men som sagt: det krävs att man bara har anslutningar i ett kvadratiskt mönster på det sättet du har.

Har "rörelsen" en riktning - spelar det någon roll var man börjar och var man slutar?

Hittade en liten algoritm som kanske kan hjälpa dig med det här:
http://www.mwolson.org/notes/AlgorithmsFirstExam.html

Längst ner på sidan hittar du en algoritm för att hitta alla vägar i en graf. Lycka till.

mvh Joakim.

Den tror jag inte är så bra i detta fallet. För det första verkar det som den hittar vägar av godtycklig längd, det var ju inte intressant i detta fallet. För det andra så utnyttjar man då inte regulariteten.