ben.reser.org
rants

october


10.17.2011
january

current

 

photos
links
projects
vitals

AI Class Homework 1 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