|
||
|
||
|
||
|
||
|
 |
10.17.2011 |
Figured I'd post these here. I went through and stepped through the Tree Search Algorithm and produced this set to steps. Only steps that actually did something show up. I'm not including evaluations of if statements and so on. Yes I'm storing paths and not nodes, I was being lazy since I was doing this all by hand. I only bothered to do this for questions 4, 5 and 6. I felt question 7 was obvious enough I didn't need to prove my quick answers were right. Yes I also really did the ASCII art by hand. For anyone else wonder whaht this is about, it's for the AI Class being held online by Sebastian Thrun and Peter Norvig.
Question 4
a
______|______
/ | \
b c d
_|_ _|_ _|_
/ \ / \ / \
e f g h i j
initial = a
goal = f
========
BFS L->R
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->b}
frontier = {a->c, a->d}
2 s = b
frontier = {a->c, a->d, a->b->e, a->b->f}
---
path = {a->c}
frontier = {a->d, a->b->e, a->b->f}
3 s = c
frontier = {a->d, a->b->e, a->b->f, a->c->g, a->c->h}
---
path = {a->d}
frontier = {a->b->e, a->b->f, a->c->g, a->c->h}
4 s = d
frontier = {a->b->e, a->b->f, a->c->g, a->c->h, a->d->i, a->d->j}
---
path = {a->b->e}
frontier = {a->b->f, a->c->g, a->c->h, a->d->i, a->d->j}
5 s = e
---
path = {a->b->f}
frontier = {a->b->f, a->c->g, a->c->h, a->d->i, a->d->j}
6 s = f
return path
===
path = {a->b->f}
expanded = 6
========
DFS L->R
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->b}
frontier = {a->c, a->d}
2 s = b
frontier = {a->b->e, a->b->f, a->c, a->d}
---
path = {a->b->e}
frontier = {a->b->f, a->c, a->d}
3 s = e
---
path = {a->b->f}
frontier = {a->c, a->d}
4 s = f
return path
====
path = {a->b->f}
expanded = 4
========
BFS R->L
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->d}
frontier = {a->b, a->c}
2 s = d
frontier = {a->b, a->c, a->d->i, a->d->j}
---
path = {a->c}
frontier = {a->b, a->d->i, a->d->j}
3 s = c
frontier = {a->b, a->d->i, a->d->j, a->c->g, a->c->h}
---
path = {a->b}
frontier = {a->d->i, a->d->j, a->c->g, a->c->h}
4 s = b
frontier = {a->d->i, a->d->j, a->c->g, a->c->h, a->b->e, a->b->f}
---
path = {a->d->j}
frontier = {a->d->i, a->c->g, a->c->h, a->b->e, a->b->f}
5 s = j
---
path = {a->d->i}
frontier = {a->c->g, a->c->h, a->b->e, a->b->f}
6 s = i
---
path = {a->c->h}
frontier = {a->c->g, a->b->e, a->b->f}
7 s = h
---
path = {a->c->g}
frontier = {a->b->e, a->b->f}
8 s = g
---
path = {a->b->f}
frontier = {a->b->e}
9 s = f
return path
===
path = {a->b->f}
expanded = 9
========
DFS R->L
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->d}
frontier = {a->b, a->c}
2 s = d
frontier = {a->b, a->c, a->d->i, a->d->j}
---
path = {a->d->j}
frontier = {a->b, a->c, a->d->i}
3 s = j
---
path = {a->d->i}
frontier = {a->b, a->c}
4 s = i
---
path = {a->c}
frontier = {a->b}
5 s = c
frontier = {a->b, a->c->g, a->c->h}
---
path = {a->c->h}
frontier = {a->b, a->c->g}
6 s = h
---
path = {a->c->g}
frontier = {a->b}
7 s = g
---
path = {a->b}
frontier = {}
8 s = b
frontier = {a->b->e, a->b->f}
---
path = {a->b->f}
frontier = {a->b->e}
9 s = f
return f
===
path = {a->b->f}
expanded = 9
Question 5
a
______|______
/ | \
b c d
_|_ _|_ _|_
/ \ / \ / \
e f g h i j
_|_ |
/ \ |
k l m
initial = a
goal = m
========
BFS L->R
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->b}
frontier = {a->c, a->d}
2 s = b
frontier = {a->c, a->d, a->b->e, a->b->f}
---
path = {a->c}
frontier = {a->d, a->b->e, a->b->f}
3 s = c
frontier = {a->d, a->b->e, a->b->f, a->c->g, a->c->h}
---
path = {a->d}
frontier = {a->b->e, a->b->f, a->c->g, a->c->h}
4 s = d
frontier = {a->b->e, a->b->f, a->c->g, a->c->h, a->d->i, a->d->j}
---
path = {a->b->e},
frontier = {a->b->f, a->c->g, a->c->h, a->d->i, a->d->j}
5 s = e
---
path = {a->b->f}
frontier = {a->c->g, a->c->h, a->d->i, a->d->j}
6 s = f
---
path = {a->c->g}
frontier = {a->c->h, a->d->i, a->d->j}
7 s = g
frontier = {a->c->h, a->d->i, a->d->j, a->c->g->k, a->c->g->l}
---
path = {a->c->h}
frontier = {a->d->i, a->d->j, a->c->g->k, a->c->g->l}
8 s = h
frontier = {a->d->i, a->d->j, a->c->g->k, a->c->g->l, a->c->h->m}
---
path = {a->d->i}
frontier = {a->d->j, a->c->g->k, a->c->g->l, a->c->h->m}
9 s = i
---
path = {a->d->j}
frontier = {a->c->g->k, a->c->g->l, a->c->h->m}
10 s = j
---
path = {a->c->g->k}
frontier = {a->c->g->l, a->c->h->m}
11 s = k
---
path = {a->c->g->l}
frontier = {a->c->h->m}
12 s = l
---
path = {a->c->h->m}
frontier = {}
13 s = m
return path
===
path = {a->c->h->m}
expanded = 13
========
DFS L->R
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->b}
frontier = {a->c, a->d}
2 s = b
frontier = {a->c, a->d, a->b->e, a->b->f}
---
path = {a->b->e}
frontier = {a->c, a->d, a->b->f}
3 s = e
---
path = {a->b->f}
frontier = {a->c, a->d}
4 s = f
---
path = {a->c}
frontier = {a->d}
5 s = c
frontier = {a->d, a->c->g, a->c->h}
---
path = {a->c->g}
frontier = {a->d, a->c->h}
6 s = g
frontier = {a->d, a->c->h, a->c->g->k, a->c->g->l}
---
path = {a->c->g->k}
frontier = {a->d, a->c->h, a->c->g->l}
7 s = k
---
path = {a->c->g->l}
frontier = {a->d, a->c->h}
8 s = l
---
path = {a->c->h}
frontier = {a->d}
9 s = h
frontier = {a->d, a->c->h->m}
---
path = {a->c->h->m}
frontier = {a->d}
10 s = m
return path
===
path = {a->c->h->m}
expanded = 10
========
BFS R->L
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->d}
frontier = {a->b, a->c}
2 s = d
frontier = {a->b, a->c, a->d->i, a->d->j}
---
path = {a->c}
frontier = {a->b, a->d->i, a->d->j}
3 s = c
frontier = {a->b, a->d->i, a->d->j, a->c->g, a->c->h}
---
path = {a->b}
frontier = {a->d->i, a->d->j, a->c->g, a->c->h}
4 s = b
frontier = {a->d->i, a->d->j, a->c->g, a->c->h, a->b->e, a->b->f}
---
path = {a->d->j}
frontier = {a->d->i, a->c->g, a->c->h, a->b->e, a->b->f}
5 s = j
---
path = {a->d->i}
frontier = {a->c->g, a->c->h, a->b->e, a->b->f}
6 s = i
---
path = {a->c->h}
frontier = {a->c->g, a->b->e, a->b->f}
7 s = h
frontier = {a->c->g, a->b->e, a->b->f, a->c->h->m}
---
path = {a->c->g}
frontier = {a->b->e, a->b->f, a->c->h->m}
8 s = g
frontier = {a->b->e, a->b->f, a->c->h->m, a->c->g->k, a->c->g->l}
---
path = {a->b->e}
frontier = {a->b->f, a->c->h->m, a->c->g->k, a->c->g->l}
9 s = e
---
path = {a->b->f}
frontier = {a->c->h->m, a->c->g->k, a->c->g->l}
10 s = f
---
path = {a->c->h->m}
frontier = {a->c->g->k, a->c->g->l}
11 s = m
return path
===
path = {a->c->h->m}
expanded = 11
========
DFS R->L
========
frontier = {a} = {initial}
---
path = {a}
frontier = {}
1 s = a
frontier = {a->b, a->c, a->d}
---
path = {a->d}
frontier = {a->b, a->c}
2 s = d
frontier = {a->b, a->c, a->d->i, a->d->j}
---
path = {a->d->j}
frontier = {a->b, a->c, a->d->i}
3 s = j
---
path = {a->d->i}
frontier = {a->b, a->c}
4 s = i
---
path = {a->c}
frontier = {a->b}
5 s = c
frontier = {a->b, a->c->g, a->c->h}
---
path = {a->c->h}
frontier = {a->b, a->c->g}
6 s = h
frontier = {a->b, a->c->g, a->c->h->m}
---
path = {a->c->h->m}
frontier = {a->b, a->c->g}
7 s = m
return path
===
path = {a->c->h->m}
expanded = 7
Question 6
a
/ \
/ \
b c
/ \ / \
/ \ / \
d e f
/ \ / \ / \
/ \ / \ / \
g h i j
\ / \ / \ /
\ / \ / \ /
k l m
\ / \ /
\ / \ /
n o
\ /
\ /
p
initial = a
goal = j
========
BFS L->R
========
frontier = {a} = {initial}
explored = {}
---
path = {a}
frontier = {}
1 s = a
explored = {a}
frontier = {a->b, a->c}
---
path = {a->b}
frontier = {a->c}
2 s = b
explored = {a, b}
frontier = {a->c, a->b->d, a->b->e}
---
path = {a->c}
frontier = {a->b->d, a->b->e}
3 s = c
explored = {a, b, c}
frontier = {a->b->d, a->b->e, a->c->f}
---
path = {a->b->d}
frontier = {a->b->e, a->c->f}
4 s = d
explored = {a, b, c, d}
frontier = {a->b->e, a->c->f, a->b->d->g, a->b->d->h}
---
path = {a->b->e}
frontier = {a->c->f, a->b->d->g, a->b->d->h}
5 s = e
explored = {a, b, c, d, e}
frontier = {a->c->f, a->b->d->g, a->b->d->h, a->b->e->i}
---
path = {a->c->f}
frontier = {a->b->d->g, a->b->d->h, a->b->e->i}
6 s = f
explored = {a, b, c, d, e, f}
frontier = {a->b->d->g, a->b->d->h, a->b->e->i, a->c->f->j}
---
path = {a->b->d->g}
frontier = {a->b->d->h, a->b->e->i, a->c->f->j}
7 s = g
explored = {a, b, c, d, e, f, g}
frontier = {a->b->d->h, a->b->e->i, a->c->f->j, a->b->d->g->k}
---
path = {a->b->d->h}
frontier = {a->b->e->i, a->c->f->j, a->b->d->g->k}
8 s = h
explored = {a, b, c, d, e, f, g, h}
frontier = {a->b->e->i, a->c->f->j, a->b->d->g->k, a->b->d->h->l}
---
path = {a->b->e->i}
frontier = {a->c->f->j, a->b->d->g->k, a->b->d->h->l}
9 s = i
explored = {a, b, c, d, e, f, g, h, i}
frontier = {a->c->f->j, a->b->d->g->k, a->b->d->h->l, a->b->e->i->m}
---
path = {a->c->f->j}
frontier = {a->b->d->g->k, a->b->d->h->l, a->b->e->i->m}
10 s = j
explored = {a, b, c, d, e, f, g, h, i, j}
return path
===
path = {a->c->f->j}
expanded = 10
========
DFS L->R
========
frontier = {a} = {initial}
explored = {}
---
path = {a}
frontier = {}
1 s = a
explored = {a}
frontier = {a->b, a->c}
---
path = {a->b}
frontier = {a->c}
2 s = b
explored = {a, b}
frontier = {a->c, a->b->d, a->b->e}
---
path = {a->b->d}
frontier = {a->c, a->b->e}
3 s = d
explored = {a, b, d}
frontier = {a->c, a->b->e, a->b->d->g, a->b->d->h}
---
path = {a->b->d->g}
frontier = {a->c, a->b->e, a->b->d->h}
4 s = g
explored = {a, b, d, g}
frontier = {a->c, a->b->e, a->b->d->h, a->b->d->g->k}
---
path = {a->b->d->g->k}
frontier = {a->c, a->b->e, a->b->d->h}
5 s = k
explored = {a, b, d, g, k}
frontier = {a->c, a->b->e, a->b->d->h, a->b->d->g->k->n}
---
path = {a->b->d->g->k->n}
frontier = {a->c, a->b->e, a->b->d->h}
6 s = n
explored = {a, b, d, g, k, n}
frontier = {a->c, a->b->e, a->b->d->h, a->b->d->g->k->n->p}
---
path = {a->b->d->g->k->n->p}
frontier = {a->c, a->b->e, a->b->d->h}
7 s = p
explored = {a, b, d, g, k, n, p}
---
path = {a->b->d->h}
frontier = {a->c, a->b->e}
8 s = h
explored = {a, b, d, g, k, n, p, h}
frontier = {a->c, a->b->e, a->b->d->h->l}
---
path = {a->b->d->h->l}
frontier = {a->c, a->b->e}
9 s = l
explored = {a, b, d, g, k, n, p, h, l}
frontier = {a->c, a->b->e, a->b->d->h->l->o}
---
path = {a->b->d->h->l->o
frontier = {a->c, a->b->e}
10 s = o
explored = {a, b, d, g, k, n, p, h, l, o}
---
path = {a->b->e}
frontier = {a->c}
11 s = e
explored = {a, b, d, g, k, n, p, h, l, o, e}
frontier = {a->c, a->b->e->i}
---
path = {a->b->e->i}
frontier = {a->c}
12 s = i
explored = {a, b, d, g, k, n, p, h, l, o, e, i}
frontier = {a->c, a->b->e->i->m}
---
path = {a->b->e->i->m}
frontier = {a->c}
13 s = m
explored = {a, b, d, g, k, n, p, h, l, o, e, i, m}
---
path = {a->c}
frontier = {}
14 s = c
explored = {a, b, d, g, k, n, p, h, l, o, e, i, m, c}
frontier = {a->c->f}
---
path = {a->c->f}
frontier = {}
15 s = f
explored = {a, b, d, g, k, n, p, h, l, o, e, i, m, c, f}
frontier = {a->c->f->j}
---
path = {a->c->f->j}
frontier = {}
16 = s
explored = {a, b, d, g, k, n, p, h, l, o, e, i, m, c, f, j}
return path
===
path = {a->c->f->j}
expanded = 16
========
BFS R->L
========
frontier = {a} = {initial}
explored = {}
---
path = {a}
frontier = {}
1 s = a
explored = {a}
frontier = {a->b, a->c}
---
path = {a->c}
frontier = {a->b}
2 s = c
explored = {a, c}
frontier = {a->b, a->c->e, a->c->f}
---
path = {a->b}
frontier = {a->c->e, a->c->f}
3 s = b
explored = {a, c, b}
frontier = {a->c->e, a->c->f, a->b->d}
---
path = {a->c->f}
frontier = {a->c->e, a->b->d}
4 s = f
explored = {a, c, b, f}
frontier = {a->c->e, a->b->d, a->c->f->i, a->c->f->j}
---
path = {a->c->e}
frontier = {a->b->d, a->c->f->i, a->c->f->j}
5 s = e
explored = {a, c, b, f, e}
frontier = {a->b->d, a->c->f->i, a->c->f->j, a->c->e->h}
---
path = {a->b->d}
frontier = {a->c->f->i, a->c->f->j, a->c->e->h}
6 s = d
explored = {a, c, b, f, e, d}
frontier = {a->c->f->i, a->c->f->j, a->c->e->h, a->b->d->g}
---
path = {a->c->f->j}
frontier = {a->c->f->i, a->c->e->h, a->b->d->g}
7 s = j
explored = {a, c, b, f, e, d, j}
return path
===
path = {a->c->f->j}
expanded = 7
========
DFS R->L
========
frontier = {a} = {initial}
explored = {}
---
path = {a}
frontier = {}
1 s = a
explored = {a}
frontier = {a->b, a->c}
---
path = {a->c}
frontier = {a->b}
2 s = c
explored = {a, c}
frontier = {a->b, a->c->e, a->c->f}
---
path = {a->c->f}
frontier = {a->b, a->c->e}
3 s = f
explored = {a, c, f}
frontier = {a->b, a->c->e, a->c->f->i, a->c->f->j}
---
path = {a->c->f->j}
frontier = {a->b, a->c->e, a->c->f->i}
4 s = j
explored = {a, c, f, j}
return path
===
path = {a->c->f->j}
expanded = 4