Diskussion:Kürzester Pfad

es scheint zu funzen. Man könnte natürlich auch noch das Array mit Knoten ersetzen. Und noch was macht mir Angst: die Gehirnemulation. Bei dieser Rekursionskontrolle(Rekursionszähler, etc.) kann man nämlich jeden parallelen Prozeß sequentiell simulieren. Man bräuchte bloß noch im CT-Scan das Gehirn auszulesen, daraus verkettete Struct-Pointer zu erstellen und dann hier statt der Flutung die elektrische Reizleitung parallellrekursiv zu simulieren. Ich frage mich, ob das geht. Deswegen hab ich es auch geschrieben.

1. include <stdlib.h>

1. define UNPASSABLE 1
2. define PASSABLE 0
3. define ALREADY_PASSED 2
4. define GOAL 3
5. define MARK 4

1. define FX_SIZE 7
2. define FY_SIZE 7

unsigned char field[FX_SIZE][FY_SIZE];

typedef struct {

int x,y;
unsigned   rec_count;
signed int  prevID;
signed int ID;
unsigned   inactivated;

void *prev, *next; /* Ende mit NULL terminiert */

} rec_control;

rec_control *iteration_buf; rec_control *Start;

signed int ID_upcount;
unsigned ID_subtract;

void insert_pos(int x, int y, int rec_count, int ID ) {

rec_control *getlast, *old ;

if( field[x][y]==ALREADY_PASSED )return;
else field[x][y]=ALREADY_PASSED;

printf("Haenge Position %d %d in die Kette...\n",x,y);

 getlast=Start;

while( getlast->next != NULL )
{
 getlast=getlast->next;

}

old=getlast;

getlast->next=malloc(sizeof ( rec_control ));
getlast=getlast->next;

getlast->prev=old;
getlast->next=NULL;
getlast->x=x;
getlast->y=y;
getlast->rec_count=rec_count+1;
getlast->inactivated=0;
getlast->ID=ID_upcount;
getlast->prevID=ID;

ID_upcount++;

/* Kettedumpen debug */
  getlast=Start;
  while(getlast!= NULL )
  {
   printf("Pointer in der Kette hat die Koordinaten %d %d und die Aktivierung %d...\n",
           getlast->x, getlast->y, getlast->inactivated );

    getlast=getlast->next;
  }

/* bis hier */

}

int fill( rec_control *pos) {

printf("Bin am Anfang der Fuellfunktion mit den Koordinaten %d %d...\n",pos->x, pos->y ); /*debug */
while ( pos->inactivated==1 && pos->next!= NULL ) pos=pos->next;
 if ( pos->inactivated==1 ) return 0;
pos->inactivated=1;
ID_subtract=0;

printf("Bin am Anfang der Fuellfunktion mit den Koordinaten %d %d...\n",pos->x, pos->y ); /*debug */

if ( pos->x-1 >= 0 ) if (field[pos->x-1][pos->y]==0 )
{

 insert_pos(pos->x-1, pos->y, pos->rec_count, pos->ID);

}
if ( pos->x-1 > 0 )
{
 if ( field[pos->x-1][pos->y]==3 ) {iteration_buf=pos; return 1; }
}

if ( pos->x+1 < FX_SIZE ) if ( field[pos->x+1][pos->y]==0 )
{

 insert_pos(pos->x+1, pos->y, pos->rec_count, pos->ID);

}

if (pos->x+1 < FX_SIZE )
{
 if ( field[pos->x+1][pos->y]==3 ){iteration_buf=pos;  return 1; }
}

if ( pos->y-1 >= 0 ) if ( field[pos->x][pos->y-1]==0 )
{

 insert_pos(pos->x, pos->y-1, pos->rec_count, pos->ID );

}
if (pos->y-1 >= 0 )
{
 if ( field[pos->x][pos->y-1]==3 ){iteration_buf=pos;  return 1; }
}

if ( pos->y+1 < FY_SIZE ) if( field[pos->x][pos->y+1]==0 )
{

 insert_pos(pos->x, pos->y+1, pos->rec_count, pos->ID);

}
if (pos->y+1 < FY_SIZE )
{
 if( field[pos->x][pos->y+1]==3 ){iteration_buf=pos;  return 1; }
}

return 0;

}

void backsort() {

rec_control *buf;

do
{
iteration_buf=Start;

if ( iteration_buf->next != NULL )
{

  while(  iteration_buf->rec_count <=
         ((rec_control *)(iteration_buf->next ))->rec_count )
  {
    printf("in der Suchschleife ... debug ");
    if( iteration_buf->next != NULL ) iteration_buf=iteration_buf->next;
    else break;
    if ( iteration_buf->next == NULL ) break;

  }
} else break;

 if ( iteration_buf->next != NULL )
 {

  printf("Habe einen Treffer gelandet %d %d, vertausche...\n",
           iteration_buf->rec_count, ((rec_control *)(iteration_buf->next))->rec_count); /*debug*/

   if ( iteration_buf != Start )
   ((rec_control *) (iteration_buf->prev ))->next=iteration_buf->next;

    printf("vorm if debug\n");

   if(

      (rec_control *) (  (rec_control *) (iteration_buf->next ))
      ->next

      != NULL )
   {
      ( (rec_control *) (  (rec_control *) (iteration_buf->next ))
      ->next ) -> prev=iteration_buf;
   }

    printf("hinterm if debug...\n");

   ((rec_control *) (iteration_buf->next ))->prev=iteration_buf->prev;
   iteration_buf->prev=iteration_buf->next;

    printf("eins weiter...\n");

   buf=
   ((rec_control *) (iteration_buf->next ))->next;

   ((rec_control *) (iteration_buf->next ))->next=iteration_buf;
   iteration_buf->next=buf;

   printf("bin durch...\n");
 }

}while ( iteration_buf->next != NULL );

iteration_buf=Start;

printf("Am Ende der Sortierfunktion...\n");

}

void mark_path() {

int older_ID;

for(;;)
{
 field[iteration_buf->x][iteration_buf->y]=MARK;
 printf("Id hat den Wert %d an den Koordinaten %d %d...\n", iteration_buf->prevID,
 iteration_buf->x, iteration_buf->y );

 older_ID=iteration_buf->prevID;

 if (older_ID != -1 )
 {
  iteration_buf=Start;
  while(iteration_buf->ID!= older_ID )
                  iteration_buf=iteration_buf->next;
 }
 else break;

}

}

void find_path(unsigned x, unsigned y) /* entspricht der Kontrollfunktion */ {

Start=malloc(sizeof(rec_control));

Start->prev=NULL;
Start->next=NULL;
Start->x=x;
Start->y=y;
Start->rec_count=0;
Start->inactivated=0;
Start->prevID=-1;
Start->ID=-1;
Start->next=NULL;
iteration_buf=Start;

while ( fill(iteration_buf) == 0 ) { printf("Rufe die Ruecksortier-\n"
                                           "funktion auf...\n"); /* debug*/ backsort(); }

mark_path();

}

int main(void) {

int x,y;
char c;

ID_upcount=0;y=0;
ID_subtract=0;

printf("Das Feld hat die Groesse %d mal %d .\n"
       "Leerzeichen fuer Durchgangsweg, x fuer Block und g fuer Ziel...\n"
        ,FX_SIZE, FY_SIZE );
do
{
 x=0;
 do
 {
  do{ c=getch();} while (c!=' ' && c != 'x' && c != 'g' );
  putch(c);
  if(c==' ') field[x][y]=PASSABLE;
       else  if (c=='g' ) field[x][y]=GOAL;
       else  field[x][y]=UNPASSABLE;

  x++;
 }
 while(x<FX_SIZE);

 printf("\n");

 y++;
}
while( y<FY_SIZE );

printf("\nBitte Startkoordinaten X und Y eingeben:\n");
scanf("%d %d",&x,&y);

find_path(x,y);

y=0;
do
{
 x=0;
 do
 {
  if (field[x][y]==MARK )putch('p');
  else if ( field[x][y]==UNPASSABLE ) putch('x');
  else if ( field[x][y]==PASSABLE || field[x][y]== ALREADY_PASSED ) putch(' ');
  else if ( field[x][y]==GOAL ) putch('g');

  x++;
 }
 while(x<FX_SIZE);

 printf("\n");

 y++;
}
while( y<FY_SIZE );

 getch();
return (0);

} (nicht signierter Beitrag von 109.43.53.174 (Diskussion) 19:52, 15. Apr. 2012 (CEST))