Implementação de problemas...

Delphi

19/11/2003

Olá amigos... preciso implementar os algoritmos (famosos) a seguir:

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

Newkidsontheblock

Curtidas 0

Respostas

Newkidsontheblock

Newkidsontheblock

19/11/2003

Ninguém sabe onde posso encontrar esses procedimentos...


GOSTEI 0
Beppe

Beppe

19/11/2003

A busca binária é simples:

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
Newkidsontheblock

Newkidsontheblock

19/11/2003

Já ajudou um pouco... muito obrigado... se alguém tiver mais alguma coisa... tb será bem vinda ...


GOSTEI 0
POSTAR