Encontrar o menor caminho

gieri
(usa Linux Mint)

Enviado em 06/09/2013 - 17:09h

Preciso desenvolver um algoritmo que encontre o menor caminho em uma tabela/matriz.
Em alguns caso ha necessidade de passar em vários pontos.
Em alguns caso ha bloqueio em alguns pontos, impedindo de passar nesse ponto.
O algoritmo deve calcular o menor caminho a parti de um determinado ponto.

Exemplo:
I= Ponto de Partida.
P= Pontos onde deverá passar.
B= Bloqueio que impede a passagem.
____ ___ ___ ___ ___ ____
|_P_|___|___|___|_P_|___|
|___|___|___|___|___|___|
|___|___|___|___|___|___|
|___|_P_|___|___|___|___|
|___|___|___|_I_|___|___|
|___|___|___|___|___|_P_|

____ ___ ___ ___ ___ ____
|_P_|___|_I_|___|_P_|___|
|___|___|___|___|___|___|
|___|___|_B_|___|___|___|
|___|_P_|_B_|___|___|___|
|___|___|_B_|___|___|___|
|___|___|_B_|___|___|_P_|

Existe a possibilidade de resolver usando grafos, no entanto não sei como implementar.

cassio88
(usa Ubuntu)

Enviado em 06/09/2013 - 17:26h

Olá,
Acho que o que você procura está em
http://php.dzone.com/articles/algorithm-week-shortest-path
Dá um toque depois se isto resolveu seu problema

gieri
(usa Linux Mint)

Enviado em 06/09/2013 - 18:21h

Confesso que fiquei na mesma, testei o código apresentado e o resultado:

Array ( [0] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 1 [color] => gray [distance] => 1 ) [1] => vertex Object ( [key] => 3 [color] => gray [distance] => 1 ) ) ) [1] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 0 [color] => gray [distance] => 0 ) [1] => vertex Object ( [key] => 2 [color] => gray [distance] => 2 ) ) ) [2] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 1 [color] => gray [distance] => 1 ) [1] => vertex Object ( [key] => 3 [color] => gray [distance] => 1 ) [2] => vertex Object ( [key] => 4 [color] => gray [distance] => 3 ) ) ) [3] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 1 [color] => gray [distance] => 1 ) [1] => vertex Object ( [key] => 2 [color] => gray [distance] => 2 ) ) ) [4] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 2 [color] => gray [distance] => 2 ) [1] => vertex Object ( [key] => 5 [color] => gray [distance] => 4 ) ) ) [5] => SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => vertex Object ( [key] => 4 [color] => gray [distance] => 3 ) ) ) )

cassio88
(usa Ubuntu)

Enviado em 07/09/2013 - 10:46h

Bom, vamos ser práticos.
Experimenta
https://github.com/kay/PHP-Dijkstra
Os arquivos que você precisa ter no seu micro são
Dijkstra.php
PriorityQueue.php
runTest.php
Acabei de testar no meu micro e o resultado foi
Array ( [0] => a [1] => b [2] => c [3] => j [4] => f [5] => i )

tome cuidado, pois todos os 3 precisam começar com <?php e acabar com ?>

Como não sei exatamente qual sua necessidade, espero ter apontado para o caminho certo
O caminho das pedras é pesquisar no google por
PHP SHORTEST PATH
dá um monte de possíveis soluções
depois, por favor dê um retorno se resolveu seu problema (e aí você fecha o tópico) ou se eu estou "viajando na maionese"
um abraço

gieri
(usa Linux Mint)

Enviado em 07/09/2013 - 12:35h

Amigo fiz aqui e funcionou entre um ponto e outro. Como faço para usar com vários pontos.

A configuração do meu ficou assim:

<?php

/*
* Author: doug@neverfear.org
*/

require("Dijkstra.php");

function runTest() {
$g = new Graph();
$g->addedge("1001", "1002", 1);
$g->addedge("1001", "1007", 1);

$g->addedge("1002", "1001", 1);
$g->addedge("1002", "1003", 1);
$g->addedge("1002", "1008", 1);

$g->addedge("1003", "1002", 1);
$g->addedge("1003", "1004", 1);
$g->addedge("1003", "1009", 1);

$g->addedge("1004", "1003", 1);
$g->addedge("1004", "1005", 1);
$g->addedge("1004", "1010", 1);

$g->addedge("1005", "1004", 1);
$g->addedge("1005", "1006", 1);
$g->addedge("1005", "1011", 1);

$g->addedge("1006", "1005", 1);
$g->addedge("1006", "1012", 1);

$g->addedge("1007", "1001", 1);
$g->addedge("1007", "1008", 1);
$g->addedge("1007", "1013", 1);

$g->addedge("1008", "1002", 1);
$g->addedge("1008", "1007", 1);
$g->addedge("1008", "1009", 1);
$g->addedge("1008", "1014", 1);

$g->addedge("1009", "1003", 1);
$g->addedge("1009", "1008", 1);
$g->addedge("1009", "1010", 1);
$g->addedge("1009", "1015", 1);

$g->addedge("1010", "1004", 1);
$g->addedge("1010", "1009", 1);
$g->addedge("1010", "1011", 1);
$g->addedge("1010", "1016", 1);

$g->addedge("1011", "1005", 1);
$g->addedge("1011", "1010", 1);
$g->addedge("1011", "1012", 1);
$g->addedge("1011", "1017", 1);

$g->addedge("1012", "1006", 1);
$g->addedge("1012", "1011", 1);
$g->addedge("1012", "1018", 1);

$g->addedge("1013", "1007", 1);
$g->addedge("1013", "1014", 1);
$g->addedge("1013", "1019", 1);

$g->addedge("1014", "1008", 1);
$g->addedge("1014", "1013", 1);
$g->addedge("1014", "1015", 1);
$g->addedge("1014", "1020", 1);

$g->addedge("1015", "1009", 1);
$g->addedge("1015", "1014", 1);
$g->addedge("1015", "1016", 1);
$g->addedge("1015", "1021", 1);

$g->addedge("1016", "1010", 1);
$g->addedge("1016", "1015", 1);
$g->addedge("1016", "1017", 1);
$g->addedge("1016", "1022", 1);

$g->addedge("1017", "1011", 1);
$g->addedge("1017", "1016", 1);
$g->addedge("1017", "1018", 1);
$g->addedge("1017", "1023", 1);

$g->addedge("1018", "1012", 1);
$g->addedge("1018", "1017", 1);
$g->addedge("1018", "1024", 1);

$g->addedge("1019", "1013", 1);
$g->addedge("1019", "1020", 1);
$g->addedge("1019", "1025", 1);

$g->addedge("1020", "1014", 1);
$g->addedge("1020", "1019", 1);
$g->addedge("1020", "1021", 1);
$g->addedge("1020", "1026", 1);

$g->addedge("1021", "1015", 1);
$g->addedge("1021", "1020", 1);
$g->addedge("1021", "1022", 1);
$g->addedge("1021", "1027", 1);

$g->addedge("1022", "1016", 1);
$g->addedge("1022", "1021", 1);
$g->addedge("1022", "1023", 1);
$g->addedge("1022", "1028", 1);

$g->addedge("1023", "1017", 1);
$g->addedge("1023", "1022", 1);
$g->addedge("1023", "1024", 1);
$g->addedge("1023", "1029", 1);

$g->addedge("1024", "1018", 1);
$g->addedge("1024", "1023", 1);
$g->addedge("1024", "1030", 1);

$g->addedge("1025", "1019", 1);
$g->addedge("1025", "1026", 1);
$g->addedge("1025", "1031", 1);

$g->addedge("1026", "1020", 1);
$g->addedge("1026", "1025", 1);
$g->addedge("1026", "1027", 1);
$g->addedge("1026", "1032", 1);

$g->addedge("1027", "1021", 1);
$g->addedge("1027", "1026", 1);
$g->addedge("1027", "1028", 1);
$g->addedge("1027", "1033", 1);

$g->addedge("1028", "1022", 1);
$g->addedge("1028", "1027", 1);
$g->addedge("1028", "1029", 1);
$g->addedge("1028", "1034", 1);

$g->addedge("1029", "1023", 1);
$g->addedge("1029", "1028", 1);
$g->addedge("1029", "1030", 1);
$g->addedge("1029", "1035", 1);

$g->addedge("1030", "1024", 1);
$g->addedge("1030", "1029", 1);
$g->addedge("1030", "1036", 1);

$g->addedge("1031", "1025", 1);
$g->addedge("1031", "1032", 1);

$g->addedge("1032", "1026", 1);
$g->addedge("1032", "1031", 1);
$g->addedge("1032", "1033", 1);

$g->addedge("1033", "1027", 1);
$g->addedge("1033", "1032", 1);
$g->addedge("1033", "1034", 1);

$g->addedge("1034", "1028", 1);
$g->addedge("1034", "1033", 1);
$g->addedge("1034", "1035", 1);

$g->addedge("1035", "1029", 1);
$g->addedge("1035", "1034", 1);
$g->addedge("1035", "1036", 1);

$g->addedge("1036", "1030", 1);
$g->addedge("1036", "1035", 1);




list($distances, $prev) = $g->paths_from("1001");

$path = $g->paths_to($prev, "1036");

print_r($path);

}


runTest();
?>

gieri
(usa Linux Mint)

Enviado em 07/09/2013 - 12:55h

O bloqueio consegui fazer, retirando a passagem na célula da tabela, falta apenas conseguir calcular o menor caminho passando por vários pontos.

Exemplo:
Sair do 1001 e calcular qual o menor caminho para passar pelos pontos 1016, 1025, 1035. Independente da ordem.




Tabela:
|1001|1002|1003|1004|1005|1006|
|1007|1008|1009|1010|1011|1012|
|1013|1014|1015|1016|1017|1018|
|1019|1020|1021|1022|1023|1024|
|1025|1026|1027|1028|1029|1030|
|1031|1032|1033|1034|1035|1036|

cassio88
(usa Ubuntu)

Enviado em 07/09/2013 - 18:53h

Ajustei runTest.php:
(...)
$g->addedge("1001", "1002", 1);
(...)
$g->addedge("1036", "1035", 1);
list($distances, $prev) = $g->paths_from("1001");
$path = $g->paths_to($prev, "1036");

Aí foi só rodar:
http://localhost/tcc/runTest.php

Resultou o menor caminho:
Array ( [0] => 1001 [1] => 1002 [2] => 1003 [3] => 1004 [4] => 1005 [5] => 1006 [6] => 1012 [7] => 1018 [8] => 1024 [9] => 1030 [10] => 1036 )

como todas as distâncias no seu caso são 1, o algoritmo não mostrou sua força.

Dá um feedback pelo site.
Um abraço

gieri
(usa Linux Mint)

Enviado em 07/09/2013 - 19:18h

A saída já está certa, no entanto preciso que ele passe em alguns pontos.
Eu usarei o algoritmo para calcular a rota do ponto inicial para outro.

Gostaria de saber com fazer para ele calcular a rota saindo de um ponto e passar em vários outros, assim achando o melhor caminho.

cassio88
(usa Ubuntu)

Enviado em 08/09/2013 - 06:23h

uma busca no google por
travelling salesman problem PHP
resolve seu problema. Dei uma olhada no link
http://rossscrivener.co.uk/blog/travelling-salesman-problem/
ele resolve a questão de ter de passar por vários lugares.
Dá um feedback depois se era isso mesmo que voce queria. Se for, por favor feche o tópico. Um abraço.

gieri
(usa Linux Mint)

Enviado em 08/09/2013 - 09:34h

Cassio88, obrigado pela ajuda.
Com esse sistema eu não consigo estipular a distância correta entre os pontos, não defini um ponto inicial e nem bloqueio de rotas.
Com o Dijkstra.php eu consigo fazer isso, só não consigo fazer o calculo entre vários pontos.


Exemplo:
Sair do 1001 e calcular qual o menor caminho para passar pelos pontos 1016, 1025, 1035. Independente da ordem.

Tabela:
|1001|1002|1003|1004|1005|1006|
|1007|1008|1009|1010|1011|1012|
|1013|1014|1015|1016|1017|1018|
|1019|1020|1021|1022|1023|1024|
|1025|1026|1027|1028|1029|1030|
|1031|1032|1033|1034|1035|1036|

Solução seria:
1001[0]=>1007[1]=>1013[2]=>1019[3]=>1025[4]=>1019[5]=>1013[6]=>1014[7]=>1015[8]=>1016[9]=>1022[10]=>1028[11]=>1034[12]=>1035[13]