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