Ir para conteúdo

POWERED BY:

Arquivado

Este tópico foi arquivado e está fechado para novas respostas.

Victor Ferreira

Copiar array de objetos

Recommended Posts

Bom, amigos, pra quem conhece a teoria dos grafos ficará mais fácil entender a modelagem do problema.

 

Tenho uma classe chamada Grafo. Outra classe chamada Vértice. Uma outra classe chama-se CaixeiroViajante e uma outra ainda chama-se VizinhoMaisProximo. Estou estudando heurísticas do CaixeiroViajante.

 

Bom, eu leio um arquivo texto e crio para cada linha neste arquivo um objeto vértice Vértice com nome (chave associativa para a posição do vértice 1, 2, 3...), coordenadas X e Y, e um Booleano dizendo se este vértice foi visitado ou não. uma e armazeno cada um dos vértices numa estrutura de dados chamado ArrayVertices que fica na classe Grafo.

 

Então o Grafo possui as referências para estes objetos vértices num array. Ai eu passo o objeto Grafo pra classe CaixeiroViajante que vai realizando as operações. O problema é que, se eu tentar fazer mais de uma operação seguida (exemplo, se eu quiser calcular o caminho pelo Vizinho Mais Proximo mais de uma vez ou N vezes dentro de um LOOP), eu tenho um problema com o array de Vértices (alias, com os objetos dentro dele). O problema é que eu só faço os cálculos se os vértices não tiverem sido visitados. Porém, quando eu faço a primeira operação sobre os vértices, eu mudo a variável booleana de false pra true. Portanto, a partir da 2º vez ele acha que tudo já foi visitado e pára de calcular.

 

Para resolver isso, eu poderia criar cópias deste array de vértices. Mas se eu clonar o objeto Grafo, não dá certo pois o array de vértices dentro dele é um array de referencias, portanto ele mantém os ponteiros para aqueles objetos Vértices (que estarão todos visitados depois da primeira passagem por eles).

 

Algum de vocês sabe como resolver este problema? Conseguir copiar pelo menos uma vez esse Array de objetos? Pois se eu fizer isto, eu consigo guardar tudo numa variável aleatória e ficar sobrescrevendo sempre que eu tiver que calcular novamente.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Em PHP, objetos são passador SEMPRE por referência.

Para evitar isso, use a palavra chave clone, que cria uma cópia de um dado objeto.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Victor Ferreira,

 

A solução para o seu problema chama-se Memento, mas poste o código seu código todo aqui, é sempre divertido brincar com Grafo.

 

:D

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá, amigos, desculpem a demora para responder

 

Bom, o código é um pouco grande, mas está assim:

 

index.php, o que eu acesso quando quero calcular as heurísticas

<?php
require_once 'Vertice.class';
require_once 'Grafo.class';

$grafo = new Grafo();

$arquivo = fopen('grafo.txt' ,'r');

while(($linha = fgets($arquivo)) !== false){
   $partesVertice = explode(' ', $linha);
   $vertice = new Vertice($partesVertice[0], $partesVertice[1], $partesVertice[2]);
   $grafo->adicionarVertice(clone $vertice);
}

fclose($arquivo);
error_reporting(E_ALL);
ini_set('display_errors','On');
require_once 'CaixeiroViajante.class';
$caixeiroViajante = new CaixeiroViajante($grafo);

//$caixeiroViajante->calcularVizinhoMaisProximo();
$caixeiroViajante->TodosVizinhoMaisProximo();

?>

 

Vertice.class, aqui está o 'problema'.

<?php 
class Vertice{
   public $x;
   public $y;
   public $nome;
   public $visitado;

   public function __construct($nome, $x, $y) {
       $this->nome = $nome;
       $this->x = $x;
       $this->y = $y;
       $this->visitado = false;
   }
}
?>

 

Grafo.class, que armazena o arrayVertices e tem uns métodos de debugg

<?php
require_once 'Vertice.class';

class Grafo {
   public $arrayVertices;
   public $arrayVerticesCopia;
   public $arrayVerticesNaoVisitados;

   public function __construct() {
       $this->arrayVertices = array();
       $this->tabelaAdjacencias = array();
       $this->caminho = array();
   }

   public function adicionarVertice($vertice){
       $this->arrayVerticesNaoVisitados[$vertice->nome] = true;
       $this->arrayVertices[$vertice->nome] = $vertice;
   }

   public function printarNomeVertices(){
       foreach($this->arrayVertices as $chave => $valor) echo $chave.'<BR/>';
   }

   public function retornarQuantidadeVertices(){
       return count($this->arrayVertices);
   }

   public function printarPosXY($pos){
       echo $this->arrayVertices[$pos]->x.'<BR/>';
       echo $this->arrayVertices[$pos]->y.'<BR/>';
   }

   public function calcularDistancia($vertice1, $vertice2){
       return sqrt( pow($vertice2->x - $vertice1->x, 2) + pow($vertice2->y - $vertice1->y, 2) );
   }
}
?>

 

CaixeiroViajante.class que é a classe que chama as heuristicas, calcula tempo, printa na tela o resultado.

<?php
require_once 'Grafo.class';

class CaixeiroViajante {

   public $grafo;
   public $caminho;
   public $distanciaCaminho;
   public $verticeOrigem;
   public $tempo;

   public function __construct($grafo) {
       $this->grafo = $grafo;
       $this->caminho = array();
       $this->distanciaCaminho = 0;
   }


   public function TodosVizinhoMaisProximo(){
       $ultimoqtdVertices = $this->grafo->retornarQuantidadeVertices() +1;

       $menorTodasDistancias = INF;
       $menorTodosCaminhos = array();
       $grafo = $this->grafo;

       $tempoInicial = $this->retornarTempoSegundos();
       require_once 'VizinhoMaisProximo.class';
       for($i = 1; $i<$ultimoqtdVertices; $i++){
           $caminho = array();

           $vizinhoMaisProximo = new VizinhoMaisProximo(clone $this->grafo, $i);
           $vizinhoMaisProximo->calcular();

           if($vizinhoMaisProximo->distanciaCaminho < $menorTodasDistancias){
               $menorTodasDistancias = $vizinhoMaisProximo->distanciaCaminho;// armazena sempre a menor distancia já calculada
               $menorTodosCaminhos = $vizinhoMaisProximo->caminho;
           }
       }

       $tempoFinal = $this->retornarTempoSegundos();
       $this->tempo = $tempoFinal - $tempoInicial;

       $objeto = new stdClass();
       $objeto->caminho = $menorTodosCaminhos;
       $objeto->distanciaCaminho = $menorTodasDistancias;
       $this->imprimirResultado($objeto);
   }

   private function retornarTempoSegundos(){
       list($usec, $sec) = explode(" ", microtime());
       return ((float)$usec + (float)$sec);
   }


   public function calcularVizinhoMaisProximo(){
       require_once 'VizinhoMaisProximo.class';

       $grafo = $this->grafo;
       $tempoInicial = $this->retornarTempoSegundos();

       $vizinhoMaisProximo = new VizinhoMaisProximo($grafo, rand(1, $this->grafo->retornarQuantidadeVertices()));
       $vizinhoMaisProximo->calcular();
       $tempoFinal = $this->retornarTempoSegundos();
       $this->tempo = $tempoFinal - $tempoInicial;
       $this->imprimirResultado($vizinhoMaisProximo);
   }

   public function imprimirResultado($objeto){
       echo 'Começando pelo vértice '.$this->verticeOrigem.'..\n\n';
       echo 'O caminho é: '.implode('-',$objeto->caminho).'\n\n';
       echo 'E a distância percorrida é de: '.$objeto->distanciaCaminho.'\n\n';
       echo 'O tempo foi: '.$this->tempo.' segundos\n\n\n';
   }
}
?>

 

VizinhoMaisProximo.class, que é a classe da Heurística do Vizinho Mais Próximo. É ela quem calcula os caminhos. Funciona bem se eu chamá-la uma vez só. Mas se eu chamar num loop sem destruir os outros objetos, tudo terá sido visitado a partir da segunda vez.

<?php
class VizinhoMaisProximo {
   public $grafo;
   public $caminho;
   public $distanciaCaminho;
   public $verticeAtual;
   public $verticeOrigem;

   public function __construct($grafo, $verticeOrigem) {
       $this->grafo = $grafo;
       $this->caminho = array();
       $this->distanciaCaminho = 0;

       $this->verticeOrigem = $verticeOrigem;
   }

   public function calcular(){
       $qtdVerticesAux = $this->grafo->retornarQuantidadeVertices();
       $qtdVertices = $qtdVerticesAux + 1;
       $grafo = $this->grafo;
       $caminho = array();
       $verticeAtual = $this->verticeOrigem;
       $distanciaCaminho = 0;

       while($qtdVerticesAux != 0){

           $menorDistancia = INF;

           $grafo->arrayVertices[$verticeAtual]->visitado = true; //visitou
           $caminho[] = $verticeAtual;//adiciona ao caminho
           $verticeRetido = $verticeAtual;

           for($posVizinho = 1; $posVizinho < $qtdVertices; $posVizinho++){
               if($grafo->arrayVertices[$posVizinho]->visitado == false){//só se não tiver sido visitado
                   $distancia = $grafo->calcularDistancia($grafo->arrayVertices[$verticeAtual], $grafo->arrayVertices[$posVizinho]);

                   if($distancia < $menorDistancia){
                       $menorDistancia = $distancia;
                       $verticeRetido = $posVizinho;
                   }
               }

           }
           $verticeAtual = $verticeRetido;
           if(!is_infinite($menorDistancia)) $distanciaCaminho += $menorDistancia;
           $qtdVerticesAux--;
       }
       //volta à origem
       $caminho[] = $this->verticeOrigem;
       $distanciaCaminho += $grafo->calcularDistancia($grafo->arrayVertices[$verticeAtual], $grafo->arrayVertices[$this->verticeOrigem]);

       //torna global
       $this->caminho = $caminho;
       $this->distanciaCaminho = $distanciaCaminho;
   }
}
?>

 

Como eu poderia usar Memento para solucionar o meu problema?

 

Abraços!

Compartilhar este post


Link para o post
Compartilhar em outros sites

Victor,

 

Analisando seu código, vi que não é um caso de uso de Memento. Na verdade, existe um erro de implementação que causou o problema.

 

Vou ilustrar Memento aqui apenas para não ficar a citação no vazio, mas em seguida vou postar o algorítimo do vizinho mais próximo sem a necessidade de Memento.

 

Memento

 

O design pattern Memento permite, sem violar o encapsulamento, manter o estado interno de um objeto e restaurá-lo posteriormente.

 

Algumas vezes é necessário armazenar o estado de um objeto para restaurá-lo depois, por isso achei que seria adequado ao seu problema, pois você poderia ter um ponto de verificação (estado original não visitado), visitá-lo e, quando for necessário, voltar ao estado original (não visitado).

 

gallery_94216_34_5445.png

 

Os participantes do Memento são:

 

Memento:

Armazena o estado interno do Originator. O Memento pode armazenar muito, pouco ou o quanto for necessário do estado interno do Originator.

 

Originator:

O Originator cria um Memento contendo um ponto de verificação de seu estado interno e usa esse Memento para restaurar seu estado posteriormente.

 

Caretaker:

É o responsável por cuidar com segurança do Memento, ele apenas cuida, jamais faz qualquer operação ou analisa o conteúdo do Memento.

As consequências de uso do Memento são óbvias, como o Memento preserva o encapsulamento, informações que apenas o Originator deve conhecer não são expostas o que, consequentemente, não dá detalhes sobre a implementação. Porém, se o Originator possuir um volume de dados muito grande, a implementação pode causar problemas.

 

A implementação, no caso do PHP, é um tanto problemática. O ideal seria se PHP oferecesse artifícios como as classes amigas do C++, dessa forma a interface do Memento seria acessível apenas para o Originator.

 

<?php
class State {
}

class Memento {
private $state;

public function setState( State $state ) {
	$this->state = $state;
}

public function getState() {
	return $this->state;
}
}

class Originator {
private $visited;

public function createMemento() {
	$state = new State();
	$state->visited = $this->visited;

	$memento = new Memento();
	$memento->setState( $state );

	return $memento;
}

public function isVisited() {
	return !!$this->visited;
}

public function makeVisited( $visited = true ) {
	$this->visited = !!$visited;
}

public function setMemento( Memento $memento ) {
	$state = $memento->getState();

	$this->visited = $state->visited;
}
}

 

Claro que essa é uma implementação muito simplista. O uso seria:

 

<?php
$o = new Originator();
$memento = $o->createMemento(); //cria o ponto de verificação

var_dump( $o->isVisited() ); //bool(false)

$o->makeVisited(); //Muda o estado do objeto

var_dump( $o->isVisited() ); //bool(true)

$o->setMemento( $memento ); //restaura o ponto de verificação

var_dump( $o->isVisited() ); //bool(false)

 

Você encontra uma outra implementação de Memento aqui :seta: http://forum.imasters.com.br/topic/426661-log-em-phpmysql/page__gopid__1686430#entry1686430

 

Travelling Salesman Problem

 

O problema do caixeiro viajante é bem interessante, principalmente quando aplicado à logística ou genética. Já o algorítimo nearest neighbour algorithm, dependendo da situação, pode não ser a melhor escolha. Ele consegue gerar um caminho curto rapidamente, mas não necessariamente o caminho ótimo.

 

Claro que TSP é um problema NP-completo com complexidade exponencial, mas o algorítimo do vizinho mais próximo pode não ser eficiente se o comprimento dos últimos passos forem muito maiores que dos primeiros passos.

 

De qualquer forma, você definitivamente não precisa de um participante VizinhoMaisProximo como você tem na sua implementação, principalmente pelo fato do VizinhoMaisProximo ser, por definição, um Vertice e seu participante VizinhoMaisProximo sequer é derivado de Vertice.

 

Outro detalhe da sua implementação é que um Grafo é composto por um conjunto V, não vazio, de vértices e um conjunto de arestas (pares de V). Sua implementação de grafo não leva em consideração as ligações, apenas os pontos, por isso não é, matematicamente, um Grafo.

 

A definição de Grafo seria: Graph<Point,Link<Point,Point>>

 

Sua implementação também dá um excesso de responsabilidade ao participante Grafo: Além de cuidar dos pontos, ele também é responsável pela exibição e isso viola o princípio da responsabilidade única. Escrevi um post sobre isso, veja para compreender o que quero dizer :seta: http://thegodclass.tumblr.com/post/9749358418/refatoracao-s-r-p-contactsdisplay

 

Como estamos falando de caixeiro viajante, vou fazer a implementação do grafo usando os aspectos geográficos, ou seja, não vou abstrair a definição dos pontos nem dos links.

 

com/imasters/tsp/GeoGraph.php

 

  Mostrar conteúdo oculto

 

 

O GeoGraph, como já foi dito antes, possui um conjunto de pontos e um conjunto de links (pares de pontos):

 

com/imasters/tsp/GeographicPoint.php

 

  Mostrar conteúdo oculto

 

 

com/imasters/tsp/GeographicLink.php

 

  Mostrar conteúdo oculto

 

 

Como uma cidade é um ponto no mapa que possui um nome, vamos derivar o GeographicPoint para que ele possua um nome:

 

com/imasters/tsp/City.php

 

  Mostrar conteúdo oculto

 

 

E, por fim, o caixeiro viajante, que usará o algorítimo do vizinho mais próximo para percorrer uma lista de cidades:

 

com/imasters/tsp/TravellingSalesmanProblem.php

 

  Mostrar conteúdo oculto

 

 

A implementação é bem simples, o caixeiro viajante recebe uma lista de cidades por onde ele deverá passar. Com essa lista, pegamos um ponto qualquer e definimos como ponto de partida e, então, localizamos a cidade mais próxima de onde estamos.

 

Esse processo de estar em uma cidade e localizar a cidade mais próxima é feito até que não haja mais cidade para ser visitada.

 

Para deixar a implementação mais divertida, vamos utilizar as localizações reais (latitude e longitude) de algumas cidades e, para isso, vamos fazer a consulta no GoogleMaps pelo nome de cada cidade.

 

A implementação do GoogleMaps ficou bastante simplista por ser meramente ilustrativa:

 

com/imasters/google/maps/GoogleMaps.php

 

  Mostrar conteúdo oculto

 

 

Essa implementação do GoogleMaps utiliza o pacote HTTP que segue abaixo:

 

com/imasters/http/*

 

  Mostrar conteúdo oculto

 

 

Agora misturamos tudo isso ai e preparamos um exemplo de uso:

 

<?php
require_once 'com/imasters/google/maps/GoogleMaps.php';
require_once 'com/imasters/tsp/City.php';
require_once 'com/imasters/tsp/TravellingSalesmanProblem.php';

/**
* Objeto que representa o problema do caixeiro viajante
* @var	TravellingSalesmanProblem
*/
$tsp = new TravellingSalesmanProblem();

/**
* Cidades por onde o caixeiro viajante deverá passar
* @var	array
*/
$cities = array(
'Franca - SP, Brasil',
'São Paulo - SP, Brasil',
'Vitória - ES, Brasil',
'Ribeirão Preto - SP, Brasil',
'Guararema - SP, Brasil',
'Batatais - SP, Brasil'
);

/**
* Vamos utilizar o Google Maps para recuperar as coordenadas geográficas
* (latitude e longitude) de cada uma das cidades.
* @var	GoogleMaps
*/
$maps = new GoogleMaps();

/**
* Percorremos a matriz de cidades e buscamos no Google Maps a latitude e
* longitude para criar os objetos City.
*/
foreach ( $cities as $city ) {
/**
 * Faz a busca pelo nome da cidade
 * @var	stdClass
 */
$json = $maps->search( $city );

/**
 * Se houver resultados, adicionamos a cidade na lista de cidades que o
 * caixeiro deverá visitar.
 */
if ( count( $json->results ) == 1 ) {
	$result = array_shift( $json->results );

	$tsp->addCity( new City(
		$result->formatted_address,
		$result->geometry->location->lat,
		$result->geometry->location->lng
	) );
} else {
	throw new RuntimeException(
		'Não foi possível localizar cidade ' . $city
	);
}
}

/**
* Nesse instante já fizemos a busca pela localização geográfica de cada uma
* das cidades e vamos marcar o tempo que o algorítimo levará para resolver
* o problema.
* @var	float
*/
$start = microtime( true );

/**
* Utilizamos o algorítimo do vizinho mais próximo para identificar a rota que
* o caixeiro deverá percorrer.
*/
foreach ( $g = $tsp->nearestNeighbourAlgorithm() as $l ) {
$a = $l->getPointA();
$b = $l->getPointB();
$d = $l->distance();

printf( "%.02fKm de '%s' até '%s'\n" , $d , $a->getName() , $b->getName() );
}

printf(
"\nExistem %d pontos e %d arestas no grafo\n",
$g->countPoints() , $g->count()
);

printf( "Levamos %fs para resolver o problema.\n",
microtime( true ) - $start
);

 

A saída deverá ser alguma coisa parecida com:

 

  Citar

42,56Km de 'Franca - São Paulo, Brasil' até 'Batatais - São Paulo, Brasil'

40,00Km de 'Batatais - São Paulo, Brasil' até 'Ribeirão Preto - São Paulo, Brasil'

290,43Km de 'Ribeirão Preto - São Paulo, Brasil' até 'São Paulo, Brasil'

62,84Km de 'São Paulo, Brasil' até 'Guararema - São Paulo, Brasil'

684,98Km de 'Guararema - São Paulo, Brasil' até 'Vitória - ES, Brasil'

 

Existem 6 pontos e 5 arestas no grafo

Levamos 0,007021ms para resolver o problema.

 

;)

 

PS: Se quiser continuar brincando disso, podemos implementar outros algorítimos.

Compartilhar este post


Link para o post
Compartilhar em outros sites

E mais uma vez o João dá uma aula ajudando a galera do fórum! Valeu João! Parabéns cara! #orgulho

Compartilhar este post


Link para o post
Compartilhar em outros sites
  Em 14/10/2011 at 15:32, admin disse:

E mais uma vez o João dá uma aula ajudando a galera do fórum! Valeu João! Parabéns cara! #orgulho

 

Concordo em tudo

 

#orgulho³

Compartilhar este post


Link para o post
Compartilhar em outros sites
  Em 14/10/2011 at 15:32, admin disse:

E mais uma vez o João dá uma aula ajudando a galera do fórum! Valeu João! Parabéns cara! #orgulho

 

 

  Em 14/10/2011 at 19:20, Mário Monteiro disse:

Concordo em tudo

 

#orgulho³

 

kkkkkkkkk

 

Valeu pessoal.

 

:lol:

Compartilhar este post


Link para o post
Compartilhar em outros sites

×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.