Tulio Faria

Page 2 of 11

Metaheurística – Algorítmo Genético na resolução do problema do caixeiro viajante

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!

Esteganografia em texto e em imagem – escondendo informações

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:

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:

O link para o demo online.

Bom pessoal, até a próxima!

CakePHP 1.2 – generateList agora é find(“list”)

Olá pessoal,

esta é uma dica rápida. O antigo Model->generateList agora virou find(“list”), sendo que o seu uso foi simplificado ainda mais.

Agora basta adicionar o atributo $displayField no model com o nome do campo que será mostrado em uma lista desses valores. Se tivessemos um model Estado (id, nome e abrev) com todos os estados brasileiros e decidimos mostrar o campo nome, bastaria no model:

  1. class Estado extends AppModel{
  2.  
  3. var $name = "Estado";
  4.  
  5. var $displayField = "nome";
  6.  
  7. }

E no controller:

  1. $this->set("estados", $this->Estado->find("list"));

Simples não?

Até a próxima pessoal!

CakePHP 1.2 e a famosa tela branca (blank page)

Olá pessoal,

essa semana fui publicar um site no meu sharedhost e tive um erro de página em branco, sem erros, sem nada. Nada de saída mesmo.

Depois de fazer tudo que estava descrito no grupo oficial, como desligar o Zend Optimizer via htaccess e etc, resolvi entrar em contato com o suporte do host, claro, completamente desanimado e sem esperanças de uma solução.

Foi quando me responderam que eu deveria enviar o site novamente mas não escolher o ASCII (ou modo automático que escolhe de acordo com o arquivo entre binário e ASCII) e sim modo binário para transmissão de todos os arquivos. Imaginei logo que seria uma típica resposta sem nexo. Relutei, perguntando qual o sentido para isso, mas ele me disse (resumidamente) “apenas faça“.

Re-enviei os arquivos em modo binário e para minha surpresa, FUNCIONOU! Estou sem entender o motivo, mas pelo menos funcionou… Se alguém passar pelo mesmo problema, vale a pena tentar. :)
Abraços pessoal e até a próxima.

Comprar livros no Amazon.com pode ser bom, rápido e barato

Olá pessoal,

hoje me deparei com a Kombi dos Correios tocando a minha campainha, mas não lembrava de ter comprado nada cuja a previsão de chegada fosse hoje.

Havia chegado isso:

Saco azul

Na mesma hora fiquei me perguntando, que diabos vinha a ser aquilo (What the hell is this?), mas caiu a ficha que poderia ser os livros que comprei no Amazon.com chegando (pasmem) 10 dias antes do previsto.

E não é que era mesmo:

Amazon

Não se empolgue querendo importar notebooks, iPod’s e etc. Porque a Receita Federal não cobra impostos de importação apenas de livros! Se não estou enganado, para as outras coisas adicione uns 60% no valor do produto. Aliás, se for pelo Amazon eles nem entregam caso não seja livro.

No fim das contas compensou, entre os livros que comprei está um Dicionário Oxford Advanced Learners, que no Brasil custa aproximadamente R$ 115,00, paguei um pouco mais de R$ 60,00 com frete no Amazon.

Um fato curioso é que minha encomenda apesar de ter sido feita no site americano deles, foi enviada da Alemanha:

Da Alemanha?

Fica então a dica para quem não tem medo de inglês principalmente de livros.

Abraços e até a próxima!

Vídeo Tutorial: JavaScript Objeto Literal e jQuery – organizando seus JS’s

Olá pessoal,

este vídeo tutorial aborda de uma maneira rápida o uso de Objetos Literais em JavaScript, neste caso juntamente com jQuery.

Queria agradecer ao grande amigo Edy Segura pelos exemplos de Objetos Literais, que me ajudaram bastante.

Assistir agora!

Até a próxima pessoal, qualquer dúvida ou sugestão, comentem!

Yahoo esquece de trocar página de erro do Symfony

Olá pessoal,

essa mancada foi enviada por Dimiguel e é uma página de erro do Answers do Yahoo, que todos nós sabemos que foi desenvolvido usando o Symfony.

Erro no Yahoo!

Abraços pessoal e até a próxima!

CakePHP 1.2: Corrigindo erro estranho na Dreamhost

Olá pessoal,

a medida que passei a usar mais o CakePHP 1.2, passei a me deparar com mais problemas. (Não são muitos. Mas alguns são bem chatos.)

Estava instalando um novo site na Dreamhost, quando me deparei com o seguinte erro:

Missing Controller

Error: InternalError.htmlController could not be found.

Error: Create the class InternalError.htmlController below in file: app/controllers/internal_error.html_controller.php

<?php
class InternalError.htmlController extends AppController {

	var $name = 'InternalError.html';
}
?>

Notice: If you want to customize this error message, create app/views/errors/missing_controller.ctp

Percebam que nem mesmo o nome deste controlle solicitado é coerente. Depois de muito ajeitar o routes sem muito sucesso, acabei descobrindo na lista oficial que deveria trocar a conta para PHP 4. Não entendi o porquê do erro, mas felizmente a Dreamhost me permitiu fazer isso!

Abraços e espero que ninguém passe por isso em um servidor de hospedagem que não dá a mesma liberdade que a DH!

jQuery – image replacement com 4 linhas

Olá pessoal,

precisei usar image replacement em um projeto, mas um IR dinâmico. Resolvi então implementar um em jQuery.

  1. <h2 class="ir">Titulo</h2>
  2. <a href="http://www.tuliofaria.net" class="ir">Tulio</a>
javascript
< view plain text >
  1. $(function(){
  2. $(".ir").each(function(){
  3. t = $(this).text();
  4. $(this).text("");
  5. $(this).append('<img src="geradordaimagem.php?texto='+escape(t)+'" alt="'+t+'" border="0" />');
  6. });
  7. });

O script PHP para a geração dos títulos pode ser conseguido em: http://www.alistapart.com/articles/dynatext , aliás, no neste post no ALA tem também o JS (não jQuery, rs) de como se fazer o mesmo.

Prefiro o meu, que basta colocar a classe ir, ou qualquer outra (configurando o script) e mandar substituir.

Abraços pessoal e até a próxima!

CakePHP 1.2: carregando model, controller e component dinâmicamente

Olá pessoal,

continuando a série de posts sobre o CakePHP 1.2 e das mudanças que ele trouxe, neste post irei falar como carregar dinâmicamente model’, controller’s e component’s.

No Cake 1.1, era comum usármos:

  1. loadModel("nomeDoModel");
  2. loadComponent("nomeDoComponent");
  3. loadControllers("nomeDoController");

No Cake 1.2 todos os esses loads viraram App::import, que seria usado assim:

  1. App::import("Model", "nomeDoModel");
  2. App::import("Component", "nomeDoComponent");
  3. App::import("Controller", "nomeDoController");

O Cake 1.2 está se tornando OO de verdade.

Abraços pessoal e até a próxima!

« Older posts Newer posts »

Copyright © 2017 Tulio Faria

Theme by Anders NorenUp ↑