1.

a)

Espaço de Estados: Todos os estados possíveis exceto aqueles onde ficam só o lobo e o carneiro e o estado que fica só o carneiro e o cesto de alface.

 Estado Inicial: O rio tendo lado esquerdo e direito, e o lado direito o objetivo, o estado inicial seria aquele onde o homem, lobo, carneiro e cesto de alface estão todos no lado esquerdo do rio.

Teste de termino: testar se o homem, lobo, carneiro e cesto de alface estão no lado direito do rio.

Ações/Operadores: Se o homem esta no lado esquerdo do rio, ele pode ir para o lado direito levando com ele o lobo ou o carneiro ou o cesto de alface de forma que não deixe um estado onde o carneiro esta só com o lobo ou o cesto de alface esta só com o carneiro.

Custo:  O custo é 1 para cada travessia do homem.