 it 1  f  itk ,, it ,, itk 
Otimização de Rotas em Inquéritos Epidemiológicos e
Malacológicos de Esquistossomose em Pernambuco
Georgia C. B. Cordeiro, Danielle N. G. da Silva, Elaine C. de Assis, Silvana Bocanegra, Jones O. de Albuquerque
Universidade Federal Rural de Pernambuco - Departamento de Estatística e Informática
Rua Dom Manuel de Medeiros, s/n. Dois Irmãos. Recife - PE. CEP 52171-900
E-mail: [email protected], [email protected], [email protected], [email protected], [email protected].
Marco Antônio A. de Souza, Constança S. Barbosa
CPqAM, ENSP, FIOCRUZ - Fundação Oswaldo Cruz. Departamento de Parasitologia.
Avenida Moraes Rego, s/n, cx. Postal 7472, Cidade Universitária, CEP: 59670-420, Recife, PE.
[email protected]; [email protected]
A esquistossomose mansônica antes restrita a área rural, tornou-se um problema de
saúde pública no nordeste brasileiro. O estado de Pernambuco apresenta taxas
crescentes de infecção humana com perfil epidemiológico de prevalências crônicas
na região rural e de infecção aguda no litoral. A zona da mata pernambucana
(ilustração da Figura 1) é considerada área endêmica pelo hospedeiro Biomphalaria
straminea (ilustração da Figura 2) sendo o litoral, área foco do Biomphalaria
glabrata (ilustração da Figura 3).
FIGURA 2. Biomphalaria straminea
FIGURA 3. Biomphalaria glabrata
Modelagem
Determinar qual rota os agentes devem percorrer para coletar os caramujos nas
coleções hídricas de forma que a distância total percorrida seja a menor possível.
Este problema pode ser modelo usando o problema do caixeiro viajante.
Problema do Caixeiro Viajante
Um caixeiro viajante tem de visitar n pontos (vértices) e entre alguns pares de
pontos existem rotas (arcos), através das quais ele pode viajar de um ponto para
outro, iniciando e encerrando sua viagem no primeiro ponto. Não importa a ordem
com que os pontos são visitados e, de cada um deles pode-se ir diretamente a
qualquer outro.
Cada rota tem um valor associado que representa a distância (custo) necessário
para percorrê-la. Assim, o caixeiro viajante deseja encontrar um caminho que
tenha o menor custo possível; onde o custo do caminho é a soma dos custos das
rotas percorridas.
Onde,
V: conjunto de vértices
A: conjunto de arcos
Grafo:
Com:
FIGURA 1. Focos de esquistossomose no litoral de PE.
Área de Estudo: Pontal do Canoé:
Carne de Vaca localiza-se no Distrito de Ponta de Pedras, município de Goiana,
distante 60 km da Cidade do Recife. Com aproximadamente 1.200 habitantes,
freqüentada por veranistas e turistas em finais de semana.
FIGURA 4. Ponta de Canoé
FIGURA 5. Coleta de moluscos
O grafo G é completo, ou seja, um
ponto se liga a todos os outros
FIGURA 6. Pontos de Coleta
Algoritmo Ótimo
Técnica utilizada
Grafo do Problema
A técnica utilizada para a criação do algoritmo ótimo foi baseada no
algoritmo Depth First Search - DFS, porém fazendo uma modificação
para que sempre que uma busca termine, o último vértice visitado seja
marcado como inexplorado, permitindo que todas as combinações de
caminhos sejam experimentadas.
Análise de complexidade do algoritmo
O algoritmo realiza todas as permutações possíveis: (n-1)!
Para cada permutação o algoritmo invoca a função: custo ()
Que executa n operações de soma
Portanto, o número de operações de soma realizadas é: n!
Próximos Passos:
o trabalho dos agentes de saúde será
estendido para seis novas localidades, as quais possuem inúmeras
coleções hídricas e o algoritmo ótimo não poderá mais ser aplicado,
já que o problema do caixeiro viajante é sabido ser NP-completo.
Como trabalho futuro está sendo proposto o uso de algoritmos
genéticos como solução objetivando otimizar a utilização de
recursos no combate e prevenção da doença no estado de
Pernambuco.
www.xiscanoe.org
Este projeto é parcialmente financiado
pelo CNPq, Projeto Edital MCT/CNPq
02/2006 - Universal no. 477703/2006-2.