HIT 人工智能导论实验知识表示

猴子摘香蕉问题

Code

DFS, Python

python">class MBP:def __init__(self, posMon, posBan, posBox, isOnBox = False, isGeBan = False):self.posMon, self.posBan, self.posBox, self.isOnBox, self.isGeBan = posMon, posBan, posBox, isOnBox, isGeBandef isilLegal(self):return self.isGeBan == True and self.posMon != self.posBan or self.isOnBox == True and self.posMon != self.posBoxdef move(self, dest):if self.isOnBox or self.posMon == dest:return Falseres = MBP(dest, self.posBan, self.posBox, self.isOnBox, self.isGeBan).solve('move')if res != False:return ['Monkey move from %s to %s' % (self.posMon, dest)] + resreturn Falsedef push(self, dest):if self.isOnBox or self.posMon != self.posBox or self.posMon == dest:return Falseres = MBP(dest, self.posBan, dest, self.isOnBox, self.isGeBan).solve('push')if res != False:return ['Monkey push box from %s to %s' % (self.posBox, dest)] + resreturn Falsedef getBana(self):if self.isGeBan or not self.isOnBox or self.posMon != self.posBan:return Falseres = MBP(self.posMon, self.posBan, self.posBox, self.isOnBox, True).solve('banana')if res != False:return ['Monkey get banana'] + resreturn Falsedef boxOnto(self):if self.isOnBox or self.posMon != self.posBox:return Falseres = MBP(self.posMon, self.posBan, self.posBox, True, self.isGeBan).solve('box')if res != False:return ['Monkey climb onto box'] + resreturn Falsedef boxDown(self):if not self.isOnBox:return Falseres = MBP(self.posMon, self.posBan, self.posBox, False, self.isGeBan).solve('box')if res != False:return ['Monkey jump off box'] + resreturn Falsedef solve(self, actPrev = None):if self.isilLegal():return ['Illegal initial state']acts = ['self.getBana()']if actPrev != 'move':acts += ['self.move(self.posBan)', 'self.move(self.posBox)']if actPrev != 'push':acts += ['self.push(self.posBan)']if actPrev != 'box':acts += ['self.boxOnto()', 'self.boxDown()']if self.isGeBan:return ['Complete\n']for act in acts:res = eval(act)if res != False:breakreturn resif __name__ == '__main__':res = MBP('A', 'B', 'C', False, False).solve()for act in res:print(act)res = MBP('A', 'B', 'A', True, False).solve()for act in res:print(act)

Result

Monkey move from A to C
Monkey push box from C to B
Monkey climb onto box
Monkey get banana
CompleteMonkey jump off box
Monkey push box from A to B
Monkey climb onto box
Monkey get banana
Complete

修道士和野人问题

Code

BFS, C

#include <stdio.h>#define DEBUG 0
#define COUNT 0
#define TYPE_P unsigned char
#define TYPE_S unsigned short
#define SIZE_P 15
#define SIZE_S 2 * (SIZE_P + 1) * (SIZE_P + 1)#if DEBUG && !COUNT
#undef COUNT
#define COUNT 1
#endif
static TYPE_P B, P, Q;
signed char ens(signed char b, TYPE_P p, TYPE_P q, TYPE_S *s)
{if(p < 0 || p > P || q < 0 || q > Q)return -1;if(p > 0 && q > 0 && p < q)return -1;if(p < P && q < Q && P-p < Q-q)return -1;*s = (Q + 1) * ((P + 1) * (b==-1 ? 1 : 0) + p) + q;return 0;
}
void des(signed char *b, TYPE_P *p, TYPE_P *q, TYPE_S s)
{*q = s % (Q + 1), s /= Q + 1;*p = s % (P + 1), s /= P + 1;*b = s ? -1 : 1;
}signed char mcp(const TYPE_P m, const TYPE_P c, const TYPE_P n)
{signed char b;TYPE_P i, p, q;TYPE_P d[SIZE_S][2];TYPE_S h, j, k=0, r=0, s, t;TYPE_S dis[SIZE_S], pre[SIZE_S], que[SIZE_S];#if COUNTunsigned long C[SIZE_P][SIZE_P], cnt[SIZE_S], sum[SIZE_S];#endifB = n, P = m, Q = c;for(j=0; j<2*(P+1)*(Q+1); j++)dis[j] = -1;for(i=1; i<=B; i++){if(i > 1)d[k][0] = 0, d[k][1] = i, k++;for(p=i/2; p<=i; p++)d[k][0] = p, d[k][1] = i-p, k++;}ens(1, 0, 0, &s);#if COUNTfor(i=0; i<=P || i<=Q; i++){C[i][0] = C[i][i] = 1;for(p=1; p<i; p++)C[i][p] = C[i-1][p] + C[i-1][p-1];}cnt[s] = sum[s] = 1;#endifdis[s] = 0, que[r++] = s;for(h=0; h<r; h++){s = que[h];des(&b, &p, &q, s);#if DEBUGprintf("From (S=%2u RM=%u RC=%u B=%c) cnt=%u sum=%u\n", s, p, q, b==1?'L':'R', cnt[s], sum[s]);#endiffor(j=0; j<k; j++){if(ens(-b, p + b * d[j][0], q + b * d[j][1], &t))continue;if(dis[t] == (TYPE_S)-1)#if COUNTcnt[t] = sum[t] = 0,#endifdis[t] = dis[s] + 1, pre[t] = s, que[r++] = t;#if COUNTif(dis[t] == dis[s] + 1)cnt[t] += cnt[s], sum[t] += sum[s] * C[b==1 ? P-p : p][d[j][0]] * C[b==1 ? Q-q : q][d[j][1]];#endif#if DEBUGif(dis[t] == dis[s] + 1)printf("  To (S=%2u RM=%u RC=%u B=%c)\n", t, p + b * d[j][0], q + b * d[j][1], b==-1?'L':'R');#endif}}ens(1, 0, 0, &s);ens(-1, P, Q, &t);if(dis[t] == (TYPE_S)-1){printf("No solution");return -1;}#if COUNTprintf("min=%u, cnt=%u, sum=%u\n", dis[t], cnt[t], sum[t]);#endiffor(r=0; t!=s; que[r++]=t, t=pre[t]);for(que[h=r]=s; h!=(TYPE_S)-1; h--){des(&b, &p, &q, que[h]);printf("%2d    L: M=%u C=%u    B:%c    R: M=%u C=%u\n", dis[que[h]], P-p, Q-q, b==1?'L':'R', p, q);}return 0;
}int main()
{mcp(3, 3, 2);return 0;
}

Result

 0    L: M=3 C=3    B:L    R: M=0 C=01    L: M=3 C=1    B:R    R: M=0 C=22    L: M=3 C=2    B:L    R: M=0 C=13    L: M=3 C=0    B:R    R: M=0 C=34    L: M=3 C=1    B:L    R: M=0 C=25    L: M=1 C=1    B:R    R: M=2 C=26    L: M=2 C=2    B:L    R: M=1 C=17    L: M=0 C=2    B:R    R: M=3 C=18    L: M=0 C=3    B:L    R: M=3 C=09    L: M=0 C=1    B:R    R: M=3 C=2
10    L: M=0 C=2    B:L    R: M=3 C=1
11    L: M=0 C=0    B:R    R: M=3 C=3