Tulio Faria

Olá pessoal,

essa semana apresentei na faculdade mais um trabalho interessante. Era sobre chegar a uma solução razoável para o problema do caixeiro viajante.

O problema do caixeiro viajante é um dos problemas chamados de NP-Completo, cujo a complexidade é dada como grande.

O problema consiste em um caixeiro viajante que tem N cidades a visitar, todas as cidades possuem ligação entre si e quer-se descobrir a melhor ordem de visita das cidades voltando ao ponto inicial, com a menor distância e sem passar mais de uma vez por cidade.

Achar a solução para esse problema com poucas cidades não é tão dificil, por exemplo, com 4 cidades, há a possibilidade de 4! soluções, ou seja, 24 soluções. A medida que aumentamos o número de cidades inviabilizamos o uso de força bruta (testar todas as possibilidades) pelo o fato do número de soluções aumentar.

O algoritmo genético se espelha na natureza para resolver um determinado problema. Assim sendo, no problema do caixeiro viajante, temos uma população composta por soluções aleatórias para o problema. Desta soluções, pegamos uma porcentagem das melhores e as usamos para gerar as demais. E podemos também fazer algumas mutações para evitar da população ser formada somente por clones .

Na solução do problema feita em Java por mim, eu tenho uma população de 10 soluções geradas aleatoriamente. A cada evolução eu ordeno essas soluções deixando os melhores primeiro. Eu determinei uma taxa de mortalidade de 50%, ou seja, vou pegar os 5 piores e substituir pelo cruzamento dos 5 melhores. Esse cruzamento também é aleatório, sendo que escolho duas soluções pai de forma aleatória, tento copiar seus “genes”, e ao final completo o que não foi possível ser copiado com “genes” aleatórios (mutação). Na implementação, as distâncias entre cidades é dada por uma matriz de adjacência de 8×8 (8 cidades).

O código completo do Algorítmo Genético implementado em Java.

A implementação não garante uma solução ótima, mas tende a ser uma solução razoável na maioria das vezes.

Bom é isso, até a próxima pessoal!

Olá pessoal,

estou meio sumido, mas não sei se todos sabem, último ano de faculdade, trabalhos a mil, projeto final de curso e muito serviço deixam qualquer um louco…rs…

Neste post vou falar sobre uma técnica que foi o tema proposto em um trabalho na faculdade: Esteganografia (Steganography), que é a arte de esconder uma mensagem em outra, ou no meio digital, esconder um arquivo em outro.

O primeiro trabalho que foi proposto foi esconder um texto em um texto (HIT - Hide in Text). Foi o que mais deu trabalho, pois não há nada na internet falando sobre isso nem mesmo no Google . A técnica que desenvolvi não deve ser tão inovadora, mas resolveu o problema, com a restrição do texto “cobaia”, que irá abrigar (esconder) a mensagem, tem que ser muito, mas muito grande!

O que fiz foi trocar todos os espaços do texto pelos caracteres 0, 32 e 160 (códigos ASCII). Simples né? Mais ou menos…

Tive que fazer uma conversão de cada caracter ASCII da mensagem a ser escondida nesses 3 caracteres. Ou seja, haja espaços para conseguir esconder uma mensagem nem tão grande.

A implementação foi feita em ANSI C. Os fontes dos arquivos podem ser baixados aqui:

• Esconder texto
• Ler texto oculto

A implementação do HIP - Hide in Picture me consumiu um pouco mais de tempo, já que eu teria que ler sobre como funciona o formato BMP. Desta vez a implementação foi em PHP , por falta de tempo mesmo…

Os fontes podem ser encontrados aqui:

• Esconder texto (PHP)
• Ler texto oculto (PHP)

O link para o demo online.

Bom pessoal, até a próxima!