Determinação do caminho mínimo em sistemas de grande porte : um método exato e duas heurísticas

Abstract

Resumo: Neste trabalho é proposto e resolvido o problema de determinação de mínimas distâncias entre todas as localidades do Estado do Paraná através de um método exato e de duas heurísticas. Para a realização desta tarefa, o trabalho utilizou o mapa digitalizado do estado e um banco de dados contendo as informações geográficas de todas as rodovias e localidades. O presente trabalho foi motivado não somente pela resolução do problema de mínimas distâncias mas também pela utilização de um método que apresentasse uma menor utilização de espaço de armazenamento. Fez-se a determinação das menores distâncias entre as localidades de três diferentes formas: uma considerando todas as rodovias pavimentadas e não pavimentadas; outra considerando somente as rodovias pavimentadas e por último todas as rodovias porém com uma penalização daquelas que apresentam um mau estado de conservação. Na resolução exata para os três casos utilizou essencialmente o algoritmo de Floyd. As resoluções heurísticas apresentam formas de se fazer a divisão da área total, a primeira para que exista a possibilidade de comunicação entre as duas áreas obtidas, (com uma única linha de separação) e na outra utiliza-se uma faixa de área comum entre as duas áreas. Tais divisões têm como objetivo principal a diminuição do tempo computacional envolvido no método de determinação de mínima distância. Testes foram realizados para apresentar a validade das heurísticas

Abstract: In this work it is proposed and resolved the problem of determination of minimum distances among ali the places of the State of Paraná through an exact method and of two heuristics. For the accomplishment of this task, the work used the map digitalized of the State and a database contends the geographical information of ali the highways and places. The present work was motivated not only for the resolution of the problem of minimum distances but also for the use of a method that presented a smaller use of storage space. He made himself the determination of the smallest distances among the places in three different ways: one considering ali the paved highways and not paved; another considering only the paved highways and last ali the highways even so with a penalizing of those that present a bad conservation State. In the exact resolution for the three cases used the algorithm of Floyd essentially. The resolutions heuristics presents forms of doing the division of the total area, the first so that the communication possibility exists among the two obtained areas, (with an only separation line) and in the another a strip of common area is used among the two areas. Such divisions have as main objective the decrease of the time computational involved in the method of determination of minimum distance. Tests were accomplished to present the validity of the heuristics