Marcador de pisos

Objetos

◫, ◪ e ▩

Contexto

Matriz de objetos

Habilidade

Selecionar ◫ e ◪

Regras

Ao selecionar, apenas os ◫ letarais (horizontais e vertivais) imediatos são cobertos

Objetivo

Cobrir todos os ◫, selecionando o mínimo necessário

Utilizando os caracteres correspondentes aos tipos de pisos, insira na caixa de texto com borda pontilhada o formato do quarto, explicitando onde é possível que o usuário esteja (piso normal), onde é impossível (piso com mobília) e caso necessário onde existem buracos (impossíveis de serem selecionados).

Tipos:	"a" = ▩ = buraco | "b" = ◪ = mobília (com piso em baixo) | "c" = ◫ = piso normal
Estados:	padrão | coberto | selecionado | coberto e selecionado | piso isolado

Este é um algoritmo genético, ou seja, não possui um padrão de busca, portanto é possível que em uma determinada execução ele não encontre o melhor resultado rapidamente - inclusive ele não é capaz de detectar se existe uma solução melhor ou não. Dependendo da complexidade da entrada, vale a pena deixar o código rodando durante algum tempo.

Foram calculadas 0 gerações de 200 elementos através de reproduções com sobreposição cruzada simples dos genes de pares de elementos e taxa de mutação de 1% para cada gene dos descendentes. Os pares de elementos são escolhidos aleatóriamente com uma probabilidade de

$$p = \left({{\left({10 \over {s + 1}}\right)^4 + 10c^4} \over {a \space l}}\right)^4$$

, onde \(s\) é o número de objetos selecionados, \(c\) é o número de objetos cobertos, \(a\) é a altura da matriz e \(l\) é a largura da primeira linha matriz.