Alguem sabe onde posso achar o Problema do Caixeiro Viajante
Olá, algupem sabe onde posso achar o problema do caixeiro viajante pronto, usando somente Busca Local, em Delphi ou o algoritimo em pascal?
Desde já agradeço
Desde já agradeço
Titanius
Curtidas 0
Respostas
Massuda
17/10/2005
Desculpe se isso parecer rude, mas você já buscou no Google por ´delphi problema do caixeiro viajante´ ou ´delphi traveling salesman problem´? Certamente essa pesquisa deve resultar em vários links.
GOSTEI 0
Titanius
17/10/2005
Desculpe se isso parecer rude, mas você já buscou no Google por ´delphi problema do caixeiro viajante´ ou ´delphi traveling salesman problem´? Certamente essa pesquisa deve resultar em vários links.
Olá massuda, procurei sim, e achei alguns, porém nao sei se eles usam somente o Busca Local, na verdade eu queria mesmo, era so o algotimo da Busca Local do PCV...
GOSTEI 0
Massuda
17/10/2005
O que você chama de ´busca local´?
GOSTEI 0
Titanius
17/10/2005
Massuda, seguinte, seria um trabalho para a faculdade, porem não consigo terminar, segue o codigo que disponho...
Ou seja, ele deveria me retornar o melhor caminho, o problema é que sempre me retorna zero... tah faltando algo aí, e não sei o que é, por isso queria ver um pronto para ver o que esta faltando..
Obrigado desde Já
const
Max = 50;
var
Form1: TForm1;
Aux, cPtn: string;
k, Sort: integer;
Pontos: array[0..Max, 0..1] of integer;
Custos: array[0..Max, 0..Max] of Real;
Seq: array[0..Max] of integer;
Visitar: array[0..Max] of integer;
Reg: array[0..Max] of integer;
implementation
{$R *.DFM}
function TForm1.CalculaCusto: Real;
var
Soma: Real;
x: integer;
begin
Soma := 0;
for x := 0 to Max - 1 do
Soma := Soma + Custos[Visitar[x], Visitar[x + 1]];
Soma := Soma + Custos[Visitar[Max], Visitar[0]];
Result := Soma;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i, j, Valor: integer;
MenorCustoFinal: Real;
begin
Randomize;
// lendo as coordenadas
ListBox1.Items.Clear;
ListBox2.Items.Clear;
for i := 0 to Max - 1 do
begin
Aux := IntToStr(Random(200)); //InputBox(´Mensagem´,´coordenada x´,´´);
Pontos[i, 0] := StrToInt(Aux);
cPtn := Aux + ´,´;
Aux := IntToStr(Random(200)); //InputBox(´Mensagem´,´Coordenada y´,´´);
Pontos[i, 1] := StrToInt(Aux);
cPtn := cPtn + Aux;
ListBox1.Items.Add(cPtn);
end;
//calculando a matriz de custos
for i := 0 to Max - 1 do
begin
for j := 0 to Max - 1 do
begin
Custos[i, 1] := Sqrt(Sqr(Pontos[i, 0] - Pontos[j, 0]) + sqr(Pontos[i, 1] - Pontos[j, 1]));
end;
end;
Custos[0, 0] := i / 3;
// selecao aleatoria dos pontos a serem visitados
for i := 0 to Max - 1 do
Seq[i] := i;
k := MAx; // ponteiro
for i := 0 to Max - 1 do
begin
// Sort := Random(k); // sorteia uma cidade aleatoria
Sort := 0; // sorteia uma cidade aleatoria
Visitar[i] := Seq[Sort];
Seq[Sort] := Seq[k - 1];
k := k - 1;
end;
// matriz de custos
for i := 0 to Max - 1 do
begin
for j := 0 to Max - 1 do
begin
custos[i, j] := Sort;
end;
end;
for i := 0 to Max - 1 do reg[i] := i;
k := Max;
for i := 0 to MAx - 1 do
begin
sort := random(k);
visitar[i] := seq[sort];
// mostranado seq inicial.
ListBox2.Items.Add(IntToStr(visitar[1]));
Seq[sort] := seq[k - 1];
k := k - 1;
end;
// iniciando o proc. busca local.
MenorCustoFinal := calculacusto;
// mostrando o custo inicial na tela.
Label5.Caption := FloatToStr(menorcustofinal);
end;
Ou seja, ele deveria me retornar o melhor caminho, o problema é que sempre me retorna zero... tah faltando algo aí, e não sei o que é, por isso queria ver um pronto para ver o que esta faltando..
Obrigado desde Já
GOSTEI 0
Motta
17/10/2005
Dicionario de algoritmos : http://www.nist.gov/dads/
Obs :
O problema do caixeiro viajante tem uma solução baseada na emulação do comportamento das formigas , busque na web e deve encontrar.
Obs :
O problema do caixeiro viajante tem uma solução baseada na emulação do comportamento das formigas , busque na web e deve encontrar.
GOSTEI 0
Titanius
17/10/2005
Valeu mota, vou dar uma olhada
GOSTEI 0
Sandra
17/10/2005
Oi Fellipe! :D
Veja esta página que encontrei: [url=http://www.codigolivre.com.br/abrefontes.php?codid=771&catid=166&lingid=10]PCV - Problema do Caixeiro Viajante[/url].
Espero que ajude!
Veja esta página que encontrei: [url=http://www.codigolivre.com.br/abrefontes.php?codid=771&catid=166&lingid=10]PCV - Problema do Caixeiro Viajante[/url].
Ambiente Gráfico, que permite adição de novas cidades, arestas, etc... ótimo para professores dos cursos de Ciências da computação. que desejam exibir ao alunos, passo à passo e graficamente o funcionamento da Heurística: Têmpera Simulada para a solução do Problema do Caixeiro Viajante. Código escrito em Delphi 5.0
Espero que ajude!
GOSTEI 0
Titanius
17/10/2005
valeu sandra, esse exemplo eh bastante complexo e completo.. :D
Obrigado
Obrigado
GOSTEI 0