Fórum Implementação de problemas... #195927
19/11/2003
0
Busca binária (divisão e conquista)
Problema da mochila
Problema do caxeiro viajante
Não consegui achar nada que me auxiliasse nesse procedimento... espero que vcs possa me dar uma ajuda para localizar algo sobre o assunto.
Grato pela atenção...
New Kids...
Newkidsontheblock
Curtir tópico
+ 0Posts
20/11/2003
Newkidsontheblock
Gostei + 0
20/11/2003
Beppe
function BuscaBinaria(const A: array of Integer; Valor: Integer): Integer;
var
L, R, M: Integer;
begin
Result := -1;
L := 0;
R := High(A);
while L < R do
begin
M := A[(L + R) div 2];
if Valor < M then
R := M - 1
else if Valor > M then
L := M + 1
else
begin
Result := M;
Exit;
end;
end;
end;Para o problema da mochila, existem dois subproblemas:
- Fracionário: Coloca na mochila parte do objeto
para cada objeto, armazena o quociente de capacidade/qt(objeto) ordena a tabela em ordem decrescente adicione os primeiros itens enquanto a capacidade suportar
- 1/2: Ou coloca o objeto inteiro ou não coloca
O fracionário é resolvido com um guloso(greedy); o 1/2 com programação dinâmica(dynamic programming)
O caixeiro viajante é impossível de resolver eficientemente(NP), mas existem implementações, usando grafos.
Em material sobre design de algoritmos tu acha implementações destes.
Você pode achar alguma coisa com o Google:
Busca binária (divisão e conquista) : Binary Search
Problema da mochila :
Problema do caxeiro viajante : Traveling Salesman Problem(TSP)
Gostei + 0
20/11/2003
Newkidsontheblock
Gostei + 0
Clique aqui para fazer login e interagir na Comunidade :)