农夫过河问题？

chaisave

我觉得用 scheme 的 amb 表达式做的话，会简单一些。
主要就是用回溯来试探，最后比较出一个最优解。

sipingal

哪位能否稍加说明

1. 
   
2. /* 用队列解决农夫过河问题的算法*/
   
3. 
   
4. 
   
5. #include<stdio.h>
   
6. #include<stdlib.h>
   
7. 
   
8. #define  MAXNUM   20
   
9. 
   
10. typedef int DataType;
    
11. struct  SeqQueue {              /* 顺序队列类型定义 */
    
12.     int  f, r;
    
13.     DataType q[MAXNUM];
    
14. };
    
15. 
    
16. typedef struct SeqQueue *PSeqQueue;     /* 顺序队列类型的指针类型 */
    
17. 
    
18. PSeqQueue createEmptyQueue_seq( void ) {
    
19.     PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    
20.     if (paqu == NULL)
    
21.         printf("Out of space!! \n");
    
22.     else
    
23.         paqu->f = paqu->r = 0;
    
24.     return (paqu);
    
25. }
    
26. 
    
27. int isEmptyQueue_seq( PSeqQueue paqu ) {
    
28.     return paqu->f == paqu->r;
    
29. }
    
30. /* 在队列中插入一元素x */
    
31. void  enQueue_seq( PSeqQueue paqu, DataType x ) {
    
32.     if ( (paqu->r + 1) % MAXNUM == paqu->f  )
    
33.         printf( "Full queue.\n" );
    
34.     else {
    
35.         paqu->q[paqu->r] = x;
    
36.         paqu->r = (paqu->r + 1) % MAXNUM;
    
37.     }
    
38. }
    
39. 
    
40. /* 删除队列头部元素 */
    
41. void  deQueue_seq( PSeqQueue paqu ) {
    
42.     if( paqu->f == paqu->r )
    
43.         printf( "Empty Queue.\n" );
    
44.     else
    
45.         paqu->f = (paqu->f + 1) % MAXNUM;
    
46. }
    
47. 
    
48. /* 对非空队列,求队列头部元素 */
    
49. DataType  frontQueue_seq( PSeqQueue paqu ) {
    
50.     return (paqu->q[paqu->f]);
    
51. }
    
52. 
    
53. int farmer(int location) {
    
54.     return 0 != (location & 0x08);
    
55. }
    
56. 
    
57. int wolf(int location) {
    
58.     return 0 != (location & 0x04);
    
59. }
    
60. 
    
61. int cabbage(int location) {
    
62.     return 0 != (location & 0x02);
    
63. }
    
64. 
    
65. int goat(int location) {
    
66.     return 0 !=(location & 0x01);
    
67. }
    
68. 
    
69. /* 若状态安全则返回true */
    
70. int safe(int location) {
    
71.     /* 羊吃白菜 */
    
72.     if ((goat(location) == cabbage(location)) &&
    
73.           (goat(location) != farmer(location)) )
    
74.         return 0;
    
75.     /* 狼吃羊 */
    
76.     if ((goat(location) == wolf(location)) &&
    
77.           (goat(location) != farmer(location)))
    
78.         return 0;
    
79.     return 1;    /* 其他状态是安全的 */
    
80. }
    
81. 
    
82. 
    
83. void farmerProblem( ) {
    
84.     int movers, i, location, newlocation;
    
85.     int route[16];        /*记录已考虑的状态路径*/
    
86.     PSeqQueue moveTo;
    
87.     /*准备初值*/
    
88.     moveTo = createEmptyQueue_seq( );
    
89.     enQueue_seq(moveTo, 0x00);
    
90.     for (i = 0; i < 16; i++) route[i] = -1;
    
91.     route[0]=0;
    
92. 
    
93.     /*开始移动*/
    
94.     while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1)) {
    
95.         /*得到现在的状态*/
    
96.         location = frontQueue_seq(moveTo);
    
97.         deQueue_seq(moveTo);
    
98.         for (movers = 1; movers <= 8; movers <<= 1) {
    
99.             /* 农夫总是在移动，随农夫移动的也只能是在农夫同侧的东西 */
    
100.             if ((0 != (location & 0x08)) == (0 != (location & movers))) {
     
101.                 newlocation = location^(0x08|movers);
     
102.                 if (safe(newlocation) && (route[newlocation] == -1)) {
     
103.                     route[newlocation] = location;
     
104.                     enQueue_seq(moveTo, newlocation);
     
105.                 }
     
106.             }
     
107.         }
     
108.     }
     
109. 
     
110.     /* 打印出路径 */
     
111.     if(route[15] != -1) {
     
112.         printf("The reverse path is : \n");
     
113.         for(location = 15; location >= 0; location = route[location]) {
     
114.             printf("The location is : %d\n",location);
     
115.             if (location == 0) return;
     
116.         }
     
117.     }
     
118.     else
     
119.         printf("No solution.\n");
     
120. }
     
121. 
     
122. 
     
123. int main() {
     
124.     farmerProblem( );
     
125.     return 0;
     
126. }
     

复制代码