Chinaunix

标题: 请指点－－迷宫求所有路径 [打印本页]

---

作者: yuexun    时间: 2005-06-07 21:06
标题: 请指点－－迷宫求所有路径
菜菜我照着课本写了个迷宫路径的程序， 想求所有路径， 请高手指点...
严蔚敏的《数据结构》P50

---

作者: aero    时间: 2005-06-08 10:01
标题: 请指点－－迷宫求所有路径
回溯，找到路径后仍然回溯，直到找到所有。

^_^，要有心理准备哦。解空间估计会很大。

---

作者: yuexun    时间: 2005-06-08 10:53
标题: 请指点－－迷宫求所有路径
怎么这么难的。。。

---

作者: bleem1998    时间: 2005-06-08 11:06
标题: 请指点－－迷宫求所有路径
以前和同事讨论过这个问题
我认为最接近生活的的办法是每经过一处打一个标记
当走不通的时候就往回走
如果有了标记帮忙就不需要递归了
如果我掉进了迷宫我就这么干

---

作者: rootclown    时间: 2005-06-08 11:35
标题: 请指点－－迷宫求所有路径
我们当时也用的那本书，介绍的很详细吧。
用栈容易实现呀

---

作者: bigapple2008    时间: 2005-06-08 12:38
标题: 请指点－－迷宫求所有路径
在搜索的时候可以加上个评估函数，按照深度和自定义的一个函数为目前的状态做出评估。这样可以保证搜索不会太偏离正确的方向。
具体就是AI里的东西，楼主可以去看看

---

作者: zerozero_nine    时间: 2005-06-08 13:00
标题: 请指点－－迷宫求所有路径
用递归函数去实现回溯, 先画一下树, 才有具体概念.

---

作者: yuexun    时间: 2005-06-08 23:43
标题: 请指点－－迷宫求所有路径
这是源程序,  我是菜菜， 请帮忙改改－－求所有路径， 打印出来

#include <malloc.h>;
#include <stdio.h>;
#define STACKSIZE 2000
#define ERROR -1
#define OK 1
#define FALSE 0
#define TRUE 1


typedef struct node
{
int i;
int j;
int from; // 前一步
int to;   // 下一步
struct node *next;
} ElemType,Stack;

int initStack(Stack *s)
{
s->;i=s->;j=s->;to=s->;from=-1;
s->;next=NULL;
return OK;
}

int push(Stack *s,ElemType *e)
{
e->;next=s->;next;
s->;next=e;
return OK;
}

ElemType *pop(Stack *s)
{
ElemType *e;
if (!s->;next) return NULL;
e=s->;next;
s->;next=s->;next->;next;
return e;
}

int EmptyStack(Stack *s)
{
if (s->;next==NULL) return TRUE;
else return FALSE;
}

ElemType *nextone(ElemType *e,int *maze[], int size)
{
//如果下一步可行, nextone 函数返回下一步地址, 否则返回 NULL


  int flag=OK, t;  //标记赋初始值 OK
  ElemType *temp;

  // 将 e 的值赋给 temp
  temp = (ElemType *) malloc ( sizeof(ElemType) );
  temp->;i = e->;i;
  temp->;j = e->;j;
  temp->;from = e->;from;
  temp->;to = e->;to;

  // 测试 e 的四个方向, 是否可行
  for (t=temp->;to; t<4; t++)
  {

   temp->;i = e->;i;
   temp->;j = e->;j;
   temp->;from = e->;from;  //前一步
   temp->;to = e->;to;   //下一步
   flag = OK;

   switch(t)
   {
    case 0:  // e 的下方
      if (temp->;j+1 < size)
      {
       temp->;j++; // temp 向下移动
       temp->;from = 2;  //temp 的上一步的方向
      }
      else   // 碰到迷宫下边
       flag = ERROR;
      break;
   
    case 1: // e 的右方
      if (temp->;i+1 < size)
      {
       temp->;i++; // temp 向右移动
       temp->;from = 3; // temp 的上一步方向
      }
      else  // 碰到迷宫右边
        flag=ERROR;
      break;

    case 2: // e 的上方
      if (temp->;j-1 >;= 0)
      {
       temp->;j--; // temp 向上移动
       temp->;from = 0; // temp 的上一步方向
      }
      else //碰到迷宫上边
        flag = ERROR;
      break;

    case 3: // e 的左方
      if (temp->;i-1 >;= 0)
      {
       temp->;i--; // temp 向左移动一步
       temp->;from = 1; // temp 的上一步方向
      }
      else //碰到迷宫左边
        flag = ERROR;
      break;

    default:
      flag = ERROR;
    break;
  }//for

  //没有碰边, temp 所在点非1, 方向不重复, 即这个方向可行

  if (flag==OK && maze[temp->;i][temp->;j]==0 && temp->;from!=temp->;to)
  {
   temp->;to = 0; // temp 方向归 0
   e->;to = t+1;  // e 的下一个方向
   if (e->;to == e->;from)
     e->;to++;
   maze[temp->;i][temp->;j] = 2; // 标记该节点为可行路径

   return temp; //返回该节点地址
  }
}


  maze[e->;i][e->;j] = 0; //非可行路径上的节点赋值为 0, 空格输出
  e->;to = t; //右方设为下个判断点
  return NULL;
}
void print(int *maze[], int size)
{
//如果路径存在打印路径, 否则打印迷宫图形

int i,j;


for(i=0;i<size;i++)
   {
     printf("\n";
     for(j=0;j<size;j++)
        switch (maze[j])
        {
         case 2:   // 标记为 2 的点为可行路径, * 号输出
           printf("*";break;
         case 1:   // 标记为 1 的点为墙壁, 输出 1
           printf("%d", maze[j]);break;
         default:
           printf(" "; // 标记为 0 的点不是路径上的节点, 空格输出
        }
   }
}


void main()
{
Stack p;
int size, *maze[100], i, j;
ElemType *e, *ne, exit;
int find=FALSE;  // 标记 find 赋初始值为 FALSE

printf ("输入迷宫行数:";
scanf ("%d", &size);

for (i = 0; i < size; i++)
   maze = (int *) malloc (size * sizeof(int));
printf ("\n迷宫行数输入成功!\n";

printf ("请按行输入迷宫\n";
printf ("墙壁请输入 1, 其余请输入 0, 如 行数为 4 的可以输入:0 0 1 1\n";

for (i=0; i < size; i++)
{
  printf ("\n输入第 %d 行: \n", i+1);
  for (j = 0; j < size; j++)
  {
   scanf ("%d", &maze[j]);
  }
  printf ("\n第 %d 行输入成功...\n", i+1);
}

initStack(&p);

// 出口地址赋值 exit
exit.i = size - 1;
exit.j = size - 1;

// 入口的值赋给 e
e = (ElemType *) malloc ( sizeof(ElemType) );
e->;i=0;
e->;j=0;
e->;to=1;
e->;from=-1;

push(&p,e);

do   //栈不为空
{
  e = pop(&p); // 出栈
  if ( e->;i==exit.i && e->;j==exit.j ) // e 为出口
  {
   printf("\n路径完成\n";
   find=TRUE;
   break;    // find 赋 TRUE, 跳出循环
  }

  ne=nextone(e, maze, size);  // ne 为下一步
  if (ne)    // ne 不为空
  {
   push(&p, e);  // 前一步 e 入栈
   push(&p, ne); // ne 入栈
  }
  else
   free(e);  // ne 为空, 释放 e
}while (!EmptyStack(&p));

if(!find)
   printf("找不到路径!\n";
printf ("\n迷宫为:\n";

print(maze, size);

putchar ('\n');


}

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2