Tópicos em Úteis

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

7 de Junho de 2008 às 15:27 · Categorias: Blog, Java, Úteis

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!

Comentário (1)

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

17 de Março de 2008 às 17:03 · Categorias: Blog, Úteis

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!

Comentários (2)

JAX - jQuery Ajax Helper for CakePHP

28 de Setembro de 2007 às 15:28 · Categorias: CakePHP, JQuery, JavaScript, Úteis

Olá pessoal,

intediado com o helper do cake que trabalha com prototype? Eu também...

Então resolvi criar (inicialmente para uso próprio) o JAX - jQuery Ajax Helper. Que funciona de forma bem semelhante ao helper nativo do cake, mas com algumas melhorias...

O código pode ser visto abaixo: (e baixado aqui)

TEXTO PURO
PHP:
  1. /*
  3. JAXHelper - CakePHP Helper for Ajax with jQuery
  4. Author: Tulio Faria (www.tuliofaria.net)
  6. Requeriments:
  7. - jquery: http://docs.jquery.com/Downloading_jQuery
  8. - jform (for some features like observeForm): http://jquery.com/plugins/project/form
  10. Using:
  11. - include jquery.js and jquery.form.js in your view (yes, using plain html or html helper :) )
  13. - include the helper Jax in your controller
  14. - call any of methods available: link, observeField and observeForm
  16. */
  17.  
  18. class JaxHelper extends Helper {
  19.  
  20. var $helpers = array("Html");
  21.  
  22. function link($text, $url, $target, $options = null, $loading = null){
  23. $aId = 'link' . intval(rand());
  24. $url = $this->Html->url($url);
  25. $att = " ";
  26.  
  27. if (is_array($options)){
  28.  
  29. foreach($options as $k=>$v){
  30. $att.=$k.'="'.$v.'" ';
  31. }
  32.  
  33. }
  34.  
  35. echo "<a id="\" href="http://www.tuliofaria.net/%5C%22$url%5C%22">$text</a>";
  36. echo $this->_jsBlock("\$(\"#$aId\").click( function(){  \$.post(\"$url\", function(data){
  38. \$(\"$target\").html(data); }); return false; }); ");
  39. }
  40. function observeField($element, $options){
  41. $event = $options["event"];
  42. $update = $options["update"];
  43. $url = $this->Html->url($options["url"]);
  44.  
  45. $code = $options["loading"].'
  46. $.ajax({
  47. type: "POST",
  48. url: "'.$url.'",
  49. data: $("'.$element.'").serialize(),
  50. success: function(data){
  51. $("'.$update.'").html(data);
  52. '.$options["complete"].'
  53. }
  54. });
  55. ';
  56.  
  57. return $this->_jsBlock($this->_addReady("\$(\"$element\").$event(function(){ $code })"));
  58. }
  59.  
  60. function observeForm($element, $options){
  61. $event = $options["event"];
  62. $update = $options["update"];
  63. $url = $this->Html->url($options["url"]);
  64.  
  65. $code = '$("'.$element.'").ajaxSubmit({
  66. target:        \''.$update.'\',
  67. beforeSubmit:  function(){'.$options["loading"].'},
  68. success:       function(){'.$options["complete"].'}
  69. }
  70. );';
  71.  
  72. return $this->_jsBlock($this->_addReady("\$(\"$element\").$event(function(){ $code return false; })"));
  73. }
  74.  
  75. function _jsBlock($content){
  76. return "<script type="\">$content</script>";
  77. }
  78. function _addReady($content){
  79. return "\$(function(){ $content } );";
  80. }
  81.  
  82. function test(){
  83. echo $this->_jsBlock($this->_addReady("alert(\"Jax Helper has been installed and ready to use!\");"));
  84. }
  85. }
  86. ?>

Exemplos:

Link:

TEXTO PURO
PHP:
  1. link("Click Here!", "/contatos/info/1/", "teste", "teste"); ?>

Observe field:

TEXTO PURO
PHP:
  1. $options["event"] = "change";
  2. $options["update"] = "#teste";
  3. $options["url"] = "/contatos/info/1/";
  4. $options["loading"] = "$('#loading').fadeIn('slow');$('#teste').hide();";
  5. $options["complete"] = "$('#teste').fadeIn('slow');$('#loading').fadeOut();";
  6. echo $jax->observeField("#texto", $options); ?>

ObserveForm:

TEXTO PURO
PHP:
  1. $options["event"] = "submit";
  2. $options["update"] = "#teste";
  3. $options["url"] = "/contatos/info/1/";
  4. $options["loading"] = "$('#loading').fadeIn('slow');$('#teste').hide();";
  5. $options["complete"] = "$('#teste').fadeIn('slow');$('#loading').fadeOut();";
  6.  
  7. echo $jax->observeForm("#testando", $options); ?>

Em breve publicarei exemplos mais decentes de uso.

Qualquer sugestão ou dúvida, comente!

Abraços,

Comentários (14)

CakePHP: HtmlExt helper - helper para ajudar na construção de checkboxes

19 de Julho de 2007 às 12:04 · Categorias: CakePHP, Código Fonte, Úteis

Olá pessoal,

no último vídeo tutorial, vimos como fazer para salvar relacionamentos hasAndBelongsToMany usando a tag select multiple.

Este helper faz a mesma coisa, mas gerando uma lista de checkboxes.

Baixe o código fonte.

USO:

Supondo o nosso caso do blog:

TEXTO PURO
PHP:
  1. <? echo $htmlExt->checkboxes("Categoria/Categoria", $categorias, "
  2. <ul>", "</ul>
  3. ", "
  4.     <li>", "</li>
  5. "); ?>

Lembrando que deve-se adicionar o HtmlExt no atributo $helpers do controller e salvar o arquivo html_ext.php (sem o s no final) em /app/views/helpers/

Qualquer dúvida ou melhoria, comentem!

Abraços e até a próxima.

Comentários (6)

O Zen e a arte cavalheiresca da programação orientada a objeto

1 de Novembro de 2006 às 19:54 · Categorias: OO, Úteis

Para quem está começando a programar Orientado a Objetos, sabe que não é fácil passar por essa mudança de paradigma.

Bom, o Danilo Medeiros está escrevendo uma série de posts muito interessantes sobre o assunto, que explica de uma forma um tanto quanto diferente OO.

http://www.digitalminds.com.br/tags/zenoop 

Até a próxima...

Comentário (1)

PortableApps - seus programas em qualquer lugar

25 de Agosto de 2006 às 15:36 · Categorias: Firefox, Úteis

Navegando pelo SourceForge.net, descobri um projeto bastante interessante, o PortableApps.com. Um site com vários softwares que não precisam ser instalados.

Assim você pode ter o seu browser favorito (leia-se Firefox) mesmo onde ele não está instalado, bastanto você levá-lo em sua pendrive (memory key) com todos os seus favoritos e afins.

Há muitos aplicativos, como IM's (instant messangers), browser, multimedia entre outros. Bastando descompactar e jogar na sua pendrive e se divertir.

Até a próxima...

Comentário (1)