Code: Alles auswählen
//////////////////////////////////////////////////////////////////////
// Inhalt: Wegsuche für Jan
// Von Uli Tscharntke 07-Okt-2012
//////////////////////////////////////////////////////////////////////
#include "Common.ch"
#include "Inkey.ch"
#include "Gra.ch"
#include "Xbp.ch"
STATIC nAnzKnoten,aKnotenNachbarn
PROCEDURE Main
LOCAL nStartSeconds
SetBlink( .F. )
SetMouse( .T. )
SET CURSOR ON
SET SCOREBOARD OFF
SetColor( "W+/B" )
CLS
BildeTestdaten()
nStartSeconds := Seconds()
? Knotenentfernung( 3,3 ) // Entfernung zwischen Knoten 3 und 3 ausgeben: = 0 :-)
? Knotenentfernung( 3,7 ) // Entfernung zwischen Knoten 3 und 7 ausgeben
? Seconds()-nStartSeconds
Inkey(0)
RETURN
FUNCTION BildeTestdaten()
LOCAL I
// Testdaten, bei denen Knoten I immer Knoten I-1 und Konten I+1 als Nachbarn hat
nAnzKnoten := 1964
aKnotenNachbarn := array(nAnzKnoten)
FOR I := 1 TO nAnzKnoten // Testdaten
aKnotenNachbarn[I] := { IIF(I>1,I-1,nAnzKnoten),IIF(I<nAnzKnoten,I+1,1) }
NEXT I
RETURN( TRUE )
FUNCTION KnotenNachbarn( K ) // Liefert Array mit allen direkten Nachbarknoten zurück
RETURN( aKnotenNachbarn[K] )
FUNCTION KnotenNachbarnTeilmenge( K,aOhneKnoten ) // Liefert Array mit allen direkten Nachbarknoten ohne die aus aKnotenErreicht zurück
LOCAL aNachbarn,I
aNachbarn := KnotenNachbarn( K )
FOR I = len( aNachbarn ) TO 1 STEP -1
IF AScan( aOhneKnoten,aNachbarn[I] )<>0 // Diesen Knoten aus aNachbarn eliminieren
ARemove( aNachbarn,I/*nStartPos*/ )
ENDIF
NEXT I
RETURN( aNachbarn )
FUNCTION Knotenentfernung( K1,K2,nLevel,aKnotenErreicht,xMaxLevel )
LOCAL xResult,aNachbarn,I,xResult2,nLen
DEFAULT nLevel TO 0
DEFAULT aKnotenErreicht TO {K1}
IF K1==K2 // Entfernung bestimmt
xResult := nLevel
ELSEIF xMaxLevel<>NIL .AND. nLevel>=xMaxLevel
xResult := NIL // Es gibt schon eine kürzere Entfernung, diese Suche abbrechen!
ELSE
aNachbarn := KnotenNachbarnTeilmenge( K1,@aKnotenErreicht/*aOhneKnoten*/ ) // Den Weg von K1 zu K2 suchen
IF AScan( aNachbarn,{|K|K==K2} )<>0 // Weg gefunden!
xResult := nLevel+1
ELSE
AEval( aNachbarn,{|K,J|AAdd( aKnotenErreicht,K ) } ) // Alle Nachbarknoten in aKnotenErreicht eintragen
nLen := len( aKnotenErreicht )
FOR I := len( aNachbarn ) TO 1 STEP -1
xResult2 := Knotenentfernung( aNachbarn[I],K2,nLevel+1,@aKnotenErreicht,xMaxLevel,xResult/*xMaxLevel*/ )
IF xResult2<>NIL .AND. (xResult==NIL .OR. xResult2<xResult)
xResult := xResult2 // Lösung bzw. bessere Lösung gefunden
ENDIF
// xResult<>NIL: ein Ergebnis gefunden! Wenn I>1 noch nach besseren Lösungen suchen!
aSize( aKnotenErreicht,nLen ) // Erreichte Knoten wieder zurücksetzen!
NEXT I
ENDIF
ENDIF
RETURN( xResult ) // Wenn xResult==NIL: dann gibt es keine Lösung :-(
Code: Alles auswählen
[PROJECT]
COMPILE = xpp
COMPILE_FLAGS = /q
DEBUG = YES
GUI = NO
LINKER = ALink
LINK_FLAGS = /STACK:1000000,1000000
RC_COMPILE = arc
RC_FLAGS =
Project.xpj
[Project.xpj]
Wegsuche.exe
Eigentlich kein Problem, es gibt ja die Linker-Direktive LINK_FLAGS, mit der man den Standardwert von 10000 erhöhen kann.
Wenn ich jedoch den Wert wie oben in der XPJ-Datei erhöhe, kann ich trotzdem nicht mehr als 1963 Knoten angeben! Hat jemand eine Idee, was ich falsch mache?
Uli
.
. Meine Testdaten sind sicherlich seeehr theoretisch. Ein Pfad der unter Umständen über mehrere 10.000 Knoten gehen kann, ist sicher nicht normal. Dann kann der Algorithmus schon viele Sekunden brauchen. Ich glaube aber, dass dies in der Praxis nicht passieren wird!