Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Algorithm of Dijkstra.
Thèses sur le sujet « Algorithm of Dijkstra »
Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres
Consultez les 46 meilleures thèses pour votre recherche sur le sujet « Algorithm of Dijkstra ».
À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.
Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.
Parcourez les thèses sur diverses disciplines et organisez correctement votre bibliographie.
1
Oliveira, Erneson Alves de. « Geração de fraturas autossimilares em meios desordenados : técnicas do caminho crítico e do caminho mínimo ». reponame:Repositório Institucional da UFC, 2008. http://www.repositorio.ufc.br/handle/riufc/9657.
Texte intégralRésumé :
OLIVEIRA, Erneson Alves de. Geração de fraturas autossimilares em meios desordenados: técnicas do caminho crítico e do caminho mínimo. 2008. 54 f. Dissertação (Mestrado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2008.Submitted by Edvander Pires (edvanderpires@gmail.com) on 2014-11-03T20:05:53Z No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5)
Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2014-11-03T20:12:15Z (GMT) No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5)
Made available in DSpace on 2014-11-03T20:12:15Z (GMT). No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5) Previous issue date: 2008
In this work we propose two models for fracture generation in regular substrates. In the first model, we iteratively apply the concept of critical path to systematically determine the lower “conductivity” element in the connected spanning network. At each iteration, once these elements are identified as local “cracks ́ ́, they are permanently removed from the structure up to the point in which a macroscopic fracture can destroy the global network connectivity. This fracture is then topologically characterized as self-similar with fractal dimension Dp ≈ 1.21. In the second model, we employ the algorithm of Dijkstra to determine the minimal path in a random energy landscape and remove its highest energy element. As in the previous model, these elements are considered to be local “cracks ́ ́ till a subset of them can be identified as a macroscopic fracture. The average over many samples of fractures calculated for different system sizes reveals the presence of a self-similar structure with fractal dimension Df ≈ 1.21. The resemblance between the two exponents Dp e Df suggests that the two models belong to the same universality class.
Neste trabalho propomos dois modelos para a geração de fraturas em substratos regulares. No primeiro modelo, empregamos iterativamente o conceito de caminho crítico para determinar sistematicamente o elemento de menor “condutividade” da rede. Estes elementos são então identificados como “falhas” e removidos permanentemente da estrutura até que uma fratura macroscópica destrua a conectividade global da rede. Uma vez detectada, esta fratura é caracterizada topologicamente como uma estrutura auto-similar de dimensão fractal Dp ≈ 1.21. No segundo modelo, empregamos iterativamente o algoritmo de Dijkstra para determinar o caminho mínimo em uma paisagem aleatória, retirando sistematicamente desta estrutura o elemento de maior energia. Como no modelo anterior, estes elementos são identificados como “falhas” até que um conjunto conecto deles resulte em uma fratura macroscópica. A média realizada sobre várias amostras de fraturas em diferentes tamanhos de substratos revela a presença de uma estrutura auto-similar de dimensão fractal Df ≈ 1.21. A semelhança numérica entre os expoentes Dp e Df sugere que os dois modelos pertencem à mesma classe de universalidade.
2
Oliveira, Erneson Alves de. « GeraÃÃo de fraturas auto-similares em meios desordenados : tÃcnicas do caminho crÃtico e do caminho mÃnimo ». Universidade Federal do CearÃ, 2008. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1938.
Texte intégralRésumé :
FundaÃÃo de Amparo à Pesquisa do Estado do CearÃCoordenaÃÃo de AperfeiÃoamento de NÃvel Superior
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico
Neste trabalho propomos dois modelos para a geraÃÃo de fraturas em substratos regulares. No primeiro modelo, empregamos iterativamente o conceito de caminho crÃtico para determinar sistematicamente o elemento de menor âcondutividadeâ da rede. Estes elementos sÃo entÃo identificados como âfalhasâ e removidos permanentemente da estrutura atà que uma fratura macroscÃpica destrua a conectividade global da rede. Uma vez detectada, esta fratura à caracterizada topologicamente como uma estrutura auto-similar de dimensÃo fractal Dp ≈ 1.21. No segundo modelo, empregamos iterativamente o algoritmo de Dijkstra para determinar o caminho mÃnimo em uma paisagem aleatÃria, retirando sistematicamente desta estrutura o elemento de maior energia. Como no modelo anterior, estes elementos sÃo identificados como âfalhasâ atà que um conjunto conecto deles resulte em uma fratura macroscÃpica. A mÃdia realizada sobre vÃrias amostras de fraturas em diferentes tamanhos de substratos revela a presenÃa de uma estrutura auto-similar de dimensÃo fractal Df ≈ 1.21. A semelhanÃa numÃrica entre os expoentes Dp e Df sugere que os dois modelos pertencem à mesma classe de universalidade.
In this work we propose two models for fracture generation in regular substrates. In the first model, we iteratively apply the concept of critical path to systematically determine the lower âconductivityâ element in the connected spanning network. At each iteration, once these elements are identified as local âcracks ́ ́, they are permanently removed from the structure up to the point in which a macroscopic fracture can destroy the global network connectivity. This fracture is then topologically characterized as self-similar with fractal dimension Dp ≈ 1.21. In the second model, we employ the algorithm of Dijkstra to determine the minimal path in a random energy landscape and remove its highest energy element. As in the previous model, these elements are considered to be local âcracks ́ ́ till a subset of them can be identified as a macroscopic fracture. The average over many samples of fractures calculated for different system sizes reveals the presence of a self-similar structure with fractal dimension Df ≈ 1.21. The resemblance between the two exponents Dp e Df suggests that the two models belong to the same universality class.
3
Rajnoha, Martin. « Modelování skladů pomocí grafického rozhraní ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2016. http://www.nusl.cz/ntk/nusl-242015.
Texte intégralRésumé :
Master’s thesis proposes a new algorithm which enables efficient conversion of graphical representation of warehouse into graph theory representation and consequently accelerates estimation for route costs. The proposed algorithm computes route distances between any places in warehouse based on Breadth first search, image processing „skeletonization“ and Dijkstra algorithm. Using the proposed algorithm it is possible to search routes in a warehouse effectively and fast using precomputed routing table. Searching time is less then milisecond using routing table and even size of warehouse doesn’t affect it significantly instead of using Dijkstra algorithm.
4
Johansson, David. « An Evaluation of Shortest Path Algorithms on Real Metropolitan Area Networks ». Thesis, Linköping University, Department of Computer and Information Science, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-17491.
Texte intégralRésumé :
This thesis examines some of the best known algorithms for solving the shortest point-to-point path problem, and evaluates their performance on real metropolitan area networks. The focus has mainly been on Dijkstra‟s algorithm and different variations of it, and the algorithms have been implemented in C# for the practical tests. The size of the networks used in this study varied between 358 and 2464 nodes, and both running time and representative operation counts were measured.
The results show that many different factors besides the network size affect the running time of an algorithm, such as arc-to-node ratio, path length and network structure. The queue implementation of Dijkstra‟s algorithm showed the worst performance and suffered heavily when the problem size increased. Two techniques for increasing the performance were examined: optimizing the management of labelled nodes and reducing the search space. A bidirectional Dijkstra‟s algorithm using a binary heap to store temporarily labelled nodes combines both of these techniques, and it was the algorithm that performed best of all the tested algorithms in the practical tests.
This project was initiated by Netadmin Systems i Sverige AB who needed a new path finding module for their network management system NETadmin. While this study is primarily of interest for researchers dealing with path finding problems in computer networks, it may also be useful in evaluations of path finding algorithms for road networks since the two networks share some common characteristics.
5
Silva, Inara Soldera Romano da [UNESP]. « Utilização de um algoritmo de caminho mínimo no processo de recolhimento do palhiço da cana-de-açúcar ». Universidade Estadual Paulista (UNESP), 2009. http://hdl.handle.net/11449/90600.
Texte intégralRésumé :
Made available in DSpace on 2014-06-11T19:24:42Z (GMT). No. of bitstreams: 0
Previous issue date: 2009-12-16Bitstream added on 2014-06-13T19:52:21Z : No. of bitstreams: 1
silva_isr_me_botfca.pdf: 1100428 bytes, checksum: 826dc0fb9625c7e450be2699f43ec0bd (MD5)A atual preocupação com o meio ambiente tem feito com que empresas produtoras de cana-de-açúcar invistam na mudança do sistema de colheita. Essa mudança consiste na redução da queima do canavial na pré-colheita e na utilização do corte mecanizado com cana crua. Porém, a colheita com corte mecanizado torna disponível a biomassa residual e sem as queimadas e com o maior acúmulo do palhiço sobre o solo, criamse condições favoráveis para o aparecimento de parasitas e atraso da brota da cana, comprometendo a próxima safra. Vários autores mostram a viabilidade do uso do palhiço na produção de energia. Pois, além do potencial energético desta biomassa, têm-se como vantagens as questões ambientais, a manutenção de empregos e a substituição dos recursos energéticos de fontes naturais. Mas, as grandes dificuldades ainda encontradas para aproveitamento desse resíduo para geração de energia são o grande número de maquinário envolvido no sistema de coleta deste resíduo e o alto custo que este processo demanda, principalmente o custo com transporte. O presente trabalho tem como objetivo propor aplicações de técnicas matemáticas de otimização para auxiliar o planejamento do recolhimento do palhiço da cana-de-açúcar para aproveitamento na geração de energia, estudando a melhor forma de carregamento dos fardos de palhiço, facilitando o transporte, diminuindo custos e desgastes de maquinários. Para isto, é sugerido o uso de técnicas de agricultura de precisão para mapear o palhiço enfardado, desta forma pode-se definir uma rota para recolher os fardos no campo e transportá-los para o centro de processamento. Para determinação da rota, propõe-se o uso do algoritmo de menor caminho da teoria de grafos, utilizando uma variação do algoritmo de Dijkstra.
The current concern with the environment has made sugar cane growers invest in changing their harvesting system. This change consists of the reduced burning of cane fields before harvesting and the use of mechanized cutting for raw canes. However, mechanized harvesting makes residual biomass available and, without the burning, the major accumulation of crop residue on the ground, creating favorable conditions for the emergence of parasites and delay of new shoots, affecting the next crop. Several authors show the feasibility of using crop residue for energy production. Besides the energy potential of the biomass, there are advantages for the environmental issues, preservation of jobs and the replacement of energy resources from natural sources. But the great difficulties still found in using this residue for power generation are the large number of machinery involved in the collection system of the waste and the high costs of this process, mainly transport costs. This paper aims to propose applications of mathematical optimization techniques to help plan the collection of sugar cane crop residue to be used for power generation, by studying the best way of loading bales of crop residue, making it easy to transport them, therefore reducing costs and wear on machinery. For this, we suggested the use of techniques of Precision Agriculture to map the baled crop residue, which allows you to define a route to pick up the bales in the field and transport them to the processing center. To determine the route, it is proposed to use the shortest path algorithm from graph theory, using a variation of Dijkstra's algorithm.
6
Stráník, František. « Teorie grafů - implementace vybraných problémů ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-218082.
Texte intégralRésumé :
This work is intended on identification with basic problems from the graphs theory area. There are the basic conceptions as well more complicated problems described. The one part of this work is specialized in working of individual types of graphs. It starts with single linked list through double linked list after as much as trees which represented the simplest graphs textures. The other part of this work devotes to the whole graph and describes more complicated problems and their resolution from the theory graphs area. Among these problems belongs to searching in graphs help by Depth First Search and Breadth First Search methods. Then searching the shortest way help by the specific algorithms as are: Dijkstra´s algorithm, Floyd-Warshall´s algorithm and Bellman-Ford´s algorithm. The last part is devoted to problems with searching minimal frames of graphs with usage Kruskal´s algorithm, Jarnik´s algorithm and Boruvka´s algorithm methods.
7
Yarmolskyy, Oleksandr. « Využití distribuovaných a stochastických algoritmů v síti ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2018. http://www.nusl.cz/ntk/nusl-370918.
Texte intégralRésumé :
This thesis deals with the distributed and stochastic algorithms including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Furthermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in Matlab.
8
Jágr, Petr. « Využití prostředků umělé inteligence pro podporu rozhodování v podniku ». Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2012. http://www.nusl.cz/ntk/nusl-223632.
Texte intégralRésumé :
The master’s thesis deals with the use of artificial intelligence as support for managerial decision making in the company. This thesis contains the application which utilize genetic and graph algorithms to optimize the location of production facilities and logistic warehouses according to transport cost aspects.
9
Carli, Daniel Michelon de. « GERAÇÃO PROCEDURAL DE CENÁRIOS 3D DE CÂNIONS COM FOCO EM JOGOS DIGITAIS ». Universidade Federal de Santa Maria, 2012. http://repositorio.ufsm.br/handle/1/5394.
Texte intégralRésumé :
This Master s thesis proposes a non-assisted procedural method for 3D canyons scenes
generation based on techniques of computer graphics, computer vision and graph search
algorithm. In order to define all the features to be reproduced in our scenes, we have
analyzed several images of real canyons and have categorized them in two canyon features
models: a recursive and an ordinary one. The proposed approach manipulates a
heightmap, created using Perlin noise, in order to imitate the geological features formation
previously analyzed. Several parametrizations are used to guide and constraint the
generation of terrains, canyons features, course of river, plain areas, soft slope regions,
cliffs and plateaus. This work also uses the Mean Shift algorithm as mechanism of segmentation
to define regions of interest. A binary mask, with plain areas, is defined based
on a threshold operation by a given data set provided by the Mean Shift algorithm. Thereafter
a connected-component labeling algorithm is executed using the previously binary
mask. This algorithm finds all plains centroids. Right after that, the Dijkstra s algorithm
is performed in order to connect all plain areas, creating a valid path between the centroids.
The Dijkstra s algorithm is executed again to define the river s course. Finally, a
Gaussian smoothing operation is applied to interpolate the soft slope regions. The combination
of all those techniques produces as a result automatically generated feature-rich
canyons.Esta dissertação propõe um método procedural não assistido, baseado em técnicas de computação gráfica, visão computacional e busca em grafos, para a geração de cenários 3D de cânions com foco em jogos digitais. Para definir as características a serem reproduzidas, foram analisadas diversas imagens de cânions reais chegando-se em dois modelos, um comum e outro recursivo. A abordagem proposta manipula um reticulado gerado com ruído de Perlin, moldando assim as características inerentes a essa formação geológica. São levadas em conta as diversas parametrizações necessárias para permitir que o algoritmo construa cânions com curso de rio, áreas de planícies, regiões de encosta suave, estruturas de penhascos e, por fim, planaltos nas regiões mais altas. Para atingir o resultado final, o trabalho utiliza o algoritmo Mean Shift como mecanismo de segmentação, definindo dados e regiões de interesse. Munido dos dados do algoritmo de clusterizacao, é definido um limiar para a criação de uma máscara binária com a definição das planícies. Em um segundo momento, um algoritmo de rotulação de componentes conectados é executado, extraindo-se os centróides de cada planície. Por sua vez, o algoritmo de Dijkstra encaixa-se na definição de rotas que conectam estas planícies. O algoritmo de Dijkstra é, então, executado novamente, tendo por base uma função de custo de inclinação, para definir o curso do rio. Por fim, uma filtragem espacial baseada em um filtro Gaussiano é aplicada para interpolar as regiões de encostas de declive suave. A combinação dessas técnicas gera terrenos com grande variabilidade e com as características inerentes à formação geológica de cânions.
10
Mináč, Ján. « Systém navigace pomocí GPS pro účely cementárenské technologie ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-217779.
Texte intégralRésumé :
This diploma work deals with proposal and implementation GPS navigation system. Work includes described basic types of cement quarry and proposal to create mathematical and software model of quarry. Then work is devoted to possibilities of basic described algorithms for searching the shortest way in graph and two algorithms are described. They are Floyd-Warshall and Dikjstra algorithms. The work describe implementation of Dijkstra algorithm to model of quarry and description of the programs Autec RouteEditor and AQL Control Library. MINÁČ, J. GPS navifgation system for cement for cement technology. Brno: Brno university of technology, Faculty of electrical engineering and communication, 2009. 90 p. Supervisor prof. Ing. František Zezulka, CSc.
11
Barreto, Maurício Beraldin. « Estratégias para Planejamento e Recomposição em Redes de Telecomunicações ». Universidade do Vale do Rio dos Sinos, 2011. http://www.repositorio.jesuita.org.br/handle/UNISINOS/4567.
Texte intégralRésumé :
Submitted by William Justo Figueiro (williamjf) on 2015-07-18T13:23:58Z
No. of bitstreams: 1
51c.pdf: 3316384 bytes, checksum: 9eb62dc3d062f0ca82674a6d3feb7fdc (MD5)Made available in DSpace on 2015-07-18T13:23:58Z (GMT). No. of bitstreams: 1 51c.pdf: 3316384 bytes, checksum: 9eb62dc3d062f0ca82674a6d3feb7fdc (MD5) Previous issue date: 2011-03-29
Nenhuma
O crescimento do tráfego nas redes de telecomunicações por serviços de banda larga, telefonia fixa e móvel tem demandado esforços no planejamento e estudo da recomposição da rede, em especial redes de transporte, tornando elevado o nível de complexidade na elaboração de projetos que envolvem redes. A complexidade de interligação aumenta de acordo com as restrições impostas pela capacidade de investimentos e custos operacionais na obtenção da solução ótima para a melhor topologia de rede. Para resolver problemas de planejamento e recomposição da rede de telecomunicações é necessária a utilização de recurso computacional, pois problemas que envolvem redes desta natureza possuem a característica do conjunto de problemas de otimização combinatória, considerados difíceis. Com o objetivo de planejar e realizar estudos na recomposição da rede de telecomunicações, neste trabalho é apresentada a estratégia que visa o uso de recursos heurísticos como algoritmo genético e Dijkstra, bem como o conceito de rede fictícia na modelagem e solução computacional na obtenção da solução ótima referente à topologia de rede, possibilitando a análise prévia do tráfego na topologia proposta caso houver a incidência de falhas.
The growth of traffic on telecommunications networks for broadband services, fixed and mobile telephony has demanded efforts in planning and study the restoration of the network, especially transport networks, making the high level of complexity in developing projects that involve networks. The interconnection complexity increases with the restrictions imposed by the capacity of investment and operating costs in obtaining the optimal solution for the best network topology. To resolve issues of planning and rebuilding of the telecommunication networks is necessary to use computational resources, since problems involving networks of this nature have the feature set of combinatorial optimization problems, considered difficult. With the objective to plan and carry out studies on the recomposition of the telecommunications network, in this work the strategy for use as heuristic genetic algorithm and Dijkstra, as well as the concept of fictitious network modeling and computational solution to obtain the solution great on the network topology, enabling preliminary analysis of traffic on the proposed topology where there incidence of failures.
12
Menco, Carlos Andres Lazaro. « Nova metodologia para a estimação da seção em falta em sistemas elétricos de potência com foco nos alarmes dos relés de distância e busca de seções isoladas ». Universidade Federal de Santa Maria, 2014. http://repositorio.ufsm.br/handle/1/8548.
Texte intégralRésumé :
This works proposes a novel methodology for Fault Section Estimation in Power Systems. This document describes a computational tool to assist operators of electrical system in decision-making, thus ensuring the reliability of the energy supply and the reduction of reestablishment time after of fault occurrence. The proposed methodology is based on the interpretation of alarms provided by the Supervisory and Data Acquisition System (SCADA) and the electrical characteristics of the system, as well as impedance of transmission lines and transformers, circuit breakers states and settings of distance protective relays. The methodology is deterministic and uses the interception between zones of distance protective relays as base for the section estimation and the circuit breaker states to associate physically isolated sections in the system after of fault occurrence, making use of a shortest path search algorithm. Possible fault scenarios were simulated on the IEEE-30 Bus System in order to validate the methodology. The results show that the approach can provide satisfactory solutions, even in cases of multiple faults or failure of protections devices.Este trabalho propõe uma nova metodologia para a estimação da seção de falta em sistemas elétricos de potência. O presente documento descreve uma ferramenta computacional capaz de auxiliar os operadores do sistema elétrico na tomada de decisão, favorecendo a confiabilidade do fornecimento da energia e a redução do tempo de reestabelecimento quando da ocorrência de falta. A metodologia proposta esta baseada na interpretação dos alarmes fornecidos pelo Sistema de Supervisão e Aquisição de dados (SCADA) e nas características elétricas do sistema, assim como impedâncias de linhas de transmissão e transformadores; nos estados dos disjuntores e nos sinais e ajustes dos relés de proteção de distância. A metodologia é determinística e utiliza a intercepção entre as zonas de proteção dos relés de distância como base para a estimação da seção e os estados dos disjuntores para associar as seções fisicamente isoladas no sistema ante a ocorrência de falta, fazendo uso de um algoritmo de busca do caminho mais curto. Possíveis cenários de falta foram simulados no sistema IEEE-30 barras a fim de validar a metodologia. Os resultados mostram que a abordagem consegue fornecer soluções satisfatórias, mesmo em casos de faltas múltiplas ou em caso de falha de dispositivos de proteção.
13
Neves, Patricia Takaki. « Variações e aplicações do algoritmo de Dijkstra ». [s.n.], 2007. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276210.
Texte intégralRésumé :
Orientador: Orlando LeeDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-09T17:25:07Z (GMT). No. of bitstreams: 1 Neves_PatriciaTakaki_M.pdf: 4451114 bytes, checksum: c4fcf2f5d76f36075020307255c1470c (MD5) Previous issue date: 2007
Resumo: O problema de encontrar caminhos mínimos em um grafo com pesos nas arestas é considerado fundamental em otimização combinatória. Diversos problemas do mundo real podem ser modelados dessa forma: percurso mais curto/rápido entre duas cidades, transmissão de dados em uma rede de computadores, reconhecimento de voz, segmentação de imagens entre outros. O algoritmo proposto por Dijkstra em 1959 resolve o problema de caminhos mínimos em grafos sem arestas de peso negativo, o que não chega a ser restritivo na maior parte das aplicações. Desde então, o algoritmo tem sido refinado com o uso de estruturas de dados cada vez mais sofisticadas, reduzindo seu tempo de execução de pior caso (ao menos, do ponto de vista teórico). Recentemente, problemas de caminhos mínimos têm aparecido no contexto de Sistemas de Informação Geográfica (SIG). Neste modelo, o usuário faz consultas ao sistema para encontrar o trajeto mais curto (ou rápido) entre dois pontos especificados (problema ponto-a-ponto ou problema P2P). Além disso, pode haver várias consultas. Instâncias neste tipo de modelo são relativamente grandes: o mapa rodoviário dos Estados Unidos tem mais de 20 milhões de vértices (cada vértice representa intersecções de vias). Mesmo as implementações mais sofisticadas do algoritmo de Dijkstra não apresentam um desempenho prático capaz de atender às demandas que esse tipo de modelo requer. A pesquisa recente tem tentado reduzir este gap entre a teoria e a prática. Várias técnicas de aceleração de algoritmos têm sido propostas e implementadas: busca bidirecional, algoritmo A*, alcance (reach), landmarks e muitos outros. Algumas dessas técnicas têm restrições de domínio e outras podem ser usadas em qualquer contexto. Neste trabalho, estudamos algumas variações da versão original do algoritmo de Dijkstra, caracterizadas pelas diferentes estruturas de dados. Implementamos quatro dessas variações e realizamos testes experimentais utilizando os mapas do mundo real. Nosso objetivo foi analisar o desempenho prático dessas. Dedicamos também uma atenção especial ao problema P2P, apresentando algumas das principais técnicas de aceleração
Abstract: The problem of finding shortest paths in a weighted graph is a fundamental one in combinatorial optimization. Several real world problems can be modeled in this way: shortest or fastest tour between two cities, data transmission on a computer network, voice recognition, image segmentation among others. The algorithm proposed by Dijkstra in 1959 solves this problem when the graph has no edge with negative weight, which is not a serious restriction in most applications. Since then, the algorithm has been improved with the use of sophisticated data structures, reducing the worst case running time (at least, from a theoretical viewpoint). Recently shortest path problems has appeared in the context of Geographic Information System (GIS). In this model, the user asks the system to find out the shortest path between two given points (point-to-point problem or P2P problem). Moreover, there can be several queries. Instances in this model are relatively large: the road network map of the United States has more than 20 million vertices (each vertex represents an intersection of two roads). Even the fastest implementations of Dijkstra's algorithm do not have a performance in practice which is satisfactory to meet the requirements of this model. Recent research has tried to reduce this gap between theory and practice. Several speed-up techniques for these algorithms have been proposed and implemented: bidirectional search, algorithm A*, reach, landmarks and many others. Some of them are domain-restricted and others are applicable in any context. In this work, we studied some variants of Dijkstra's algorithm characterized by its different data structures. We have implemented four of those variants and performed experimental tests using real-world maps. Our goal was to analyze their practical performance. We also paid special attention to the P2P problem, and presented some of the main speed-up techniques
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
14
Goldmann, Tomáš. « Navigace mobilního robota ». Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2015. http://www.nusl.cz/ntk/nusl-234892.
Texte intégralRésumé :
When we look at the eld of robotics we nd that exist a lot of types of robots. Some of tham use location navigation and global navigation for their work. This work aims to map options of location navigation and description of basic technique which used. Especially, we will deal with algorithms which work with optical sensors, for example camera, stereocamera or laser which scan medium. Practise section this work is focused on the proposal and implementacion algorithm which working with local navigation for robot's return to the starting position. All this work is connecting with tracked robot which formed in the framework one of project realization at Faculty of information technology.
15
Negri, Marco Antônio Silva. « Caminhos em um grafo e o algoritmo de Dijkstra ». reponame:Repositório Institucional da UFSC, 2017. https://repositorio.ufsc.br/xmlui/handle/123456789/183409.
Texte intégralRésumé :
Dissertação (mestrado profissional) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática, Florianópolis, 2017.Made available in DSpace on 2018-02-13T03:09:45Z (GMT). No. of bitstreams: 1 349816.pdf: 1651899 bytes, checksum: 9dc7a5c2aff28a0457dfc5d52fe8e2af (MD5) Previous issue date: 2017
Este trabalho tem por objetivo apresentar um pouco da Teoria de Grafos para, com isto, termos uma fundamentação teórica que mostrará a viabilidade da aplicação no Ensino Médio, em destaque o Algoritmo de Dijkstra, onde o educando poderá modelar situações problemas num grafo, para obtenção do caminho mais curto. Este algoritmo tem uma vasta aplicação em diversas áreas do conhecimento, em especial na área de tecnologia, como por exemplo, em redes de comunicação. Proporcionando assim, uma oportunidade única de aplicações em problemas reais, atuais e do interesse do educando. Não só estudamos a questão do caminho mais curto, mas também consideramos o problema da conexidade em grafos e a existência de caminhos disjuntos, demonstrando o famoso teorema de Menger. Por exemplo, no caso de uma rede de comunicação é interessante saber qual é o ponto vulnerável do sistema e verificar a existência de um caminho alternativo, caso um destes pontos venha a falhar, uma aplicação imediata do Teorema de Menger.
Abstract : We give a brief presentation of Graph Theory in a way that a student without any knowledge in graphs can learn the basic definitions, examples and properties and can apply these in a real life situation. In particular, we study the Dijkstra algorithm, where the student can apply this algorithm to find the shortest path between nodes in a graph. This algorithm has a lot of real life applications, especially in technology such as paths in a network communication. This gives a unique opportunity of solving current real problems. Not only we study the problem of finding the shortest path, we also consider the problem of connectedness in a graph and the existence of different paths which do not intersect, proving the famous Menger's Theorem. For instance, in the case of a network communication, it is interesting to know the problem points where the system is vulnerable and of one these points fail, one can try to verify the existence of an alternative path, an immediate application of Menger's Theorem.
16
Bergdorf, Johan, et Jesper Norman. « Compressing sparse graphs to speed up Dijkstra’s shortest path algorithm ». Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166730.
Texte intégralRésumé :
One of the problems that arises from the continuously growing amount of data is that it slows down and limits the uses of large graphs in real world situations. Because of this, studies are being done to investigate the possibility of compressing data in large graphs. This report presents an investigation on the usefulness of compressing sparse graphs and then applying Dijkstra’s shortest path algorithm. A minimal spanning tree algorithm was used to compress a graph and compared with a self-implemented compression algorithm. The minimal distances and how long time it takes for Dijkstra's algorithm to find the shortest path between nodes are investigated. The results show that it is not worth compressing the type of sparse graphs used in this study. It is hard to compress the graph without losing too much of the edges that preserve the shortest paths. The time gained when running Dijkstra's algorithm on the compressed graphs is not enough to compensate for the lack of getting a good shortest path solution.
17
Saracchini, Tommaso. « Analisi delle performance degli algoritmi A* e Dijkstra bidirezionali nel problema del Route Planning ». Master's thesis, Alma Mater Studiorum - Università di Bologna, 2020. http://amslaurea.unibo.it/20702/.
Texte intégralRésumé :
Questa tesi ha l'obiettivo di confrontare le performance degli algoritmi A star e bidirezionali per il problema del calcolo del cammino più breve attraverso una rete stradale. In particolare, l'analisi verte ad analizzare il numero di nodi visitati e il tempo di esecuzione degli algoritmi, su alcune mappe stradali europee morfologicamente diverse andando ad evidenziare pregi e difetti dei diversi approcci. I dati stradali sono stati ottenuti dal sito web OpenStreetMap.com, gli algoritmi presentati sono stati scritti in linguaggio Python.
18
Edström, Viktoria. « Alternativa rutter med tidsbegränsning via en dubbelriktad modifiering av Dijkstra's algoritm ». Thesis, Högskolan i Gävle, Datavetenskap, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:hig:diva-26055.
Texte intégralRésumé :
De flesta algoritmer som används för ruttplanering finner en ruttmellan en start- och slutposition. Ofta handlar det om att hitta denkortaste eller snabbaste rutten mellan positionerna. Denna studie hartill syfte att ta fram en metod som hittar flera lämpliga rutter mellantvå positioner med användning av Dijkstra ́s algoritm [2] ochdubbelriktad sökning. Med flera rutter får användaren möjlighet attvälja den rutt som passar bäst utifrån personliga preferenser. Tillexempel antalet stopp längs med rutten eller tidsåtgång för rutten.Den resulterande metoden tar fram ett antal rutter som är under ettvillkor gällande maximal tillåten tidsåtgång.
19
SILVA, Gisele Tatiane de Lima e. « Aplicação do algoritmo de DIJKSTRA na otimização multiobjetivo de rotas de evacuação em cenários de nuvem tóxica ». Universidade Federal de Pernambuco, 2017. https://repositorio.ufpe.br/handle/123456789/25589.
Texte intégralRésumé :
Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-08-09T20:37:27Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Gisele Tatiane de Lima e Silva.pdf: 1903426 bytes, checksum: ffaaab6b067c16e8c26927fc1d7dd08f (MD5)Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-15T22:05:10Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Gisele Tatiane de Lima e Silva.pdf: 1903426 bytes, checksum: ffaaab6b067c16e8c26927fc1d7dd08f (MD5)
Made available in DSpace on 2018-08-15T22:05:10Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Gisele Tatiane de Lima e Silva.pdf: 1903426 bytes, checksum: ffaaab6b067c16e8c26927fc1d7dd08f (MD5) Previous issue date: 2017-04-27
CAPES
A otimização das rotas de evacuação pode ser considerada como uma das ferramentas que auxiliam o desenvolvimento do planejamento de segurança. O estudo das consequências de nuvens tóxicas é bastante importante devido a sua severidade em relação aos outros tipos de acidentes. Apesar disso, a liberação de nuvens tóxicas ainda ocorre, como no Porto de Santos (2016). Por isso, na elaboração deste trabalho foi calculada a melhor rota de fuga em cenários em que ocorre formação de nuvem tóxica em uma refinaria de petróleo hipotética. Isso foi executado através do algoritmo de Dijkstra considerando dois objetivos a serem minimizados: tempo de evacuação e risco individual durante o trajeto. A dissertação foi desenvolvida em algumas etapas. A primeira consistiu em compreender os processos, identificar e avaliar os riscos que envolvem as unidades de destilação atmosférica, coqueamento retardado e hidrotratamento de uma refinaria hipotética. Então, o software ALOHA foi usado para a análise quantitativa de cada hipótese levantada e também para obtenção do perfil de concentrações tóxicas para cada nó pertencente a uma rota de evacuação. O resultado da etapa anterior foi aplicado em um programa desenvolvido em C++, em que o algoritmo de Dijkstra foi utilizado para a otimização multiobjetivo e, com isso, foram encontrados os nós que compõem as melhores rotas de evacuação em relação aos objetivos de interesse. Para cada uma das quatro situações simuladas foi observada a melhor rota de evacuação em relação aos objetivos separadamente, foram vistas as influências que o tempo e o risco individual exercem no processo de escolha dos nós componentes das rotas ótimas e, logo depois, foram obtidas as rotas ótimas. Três cenários simulados foram referentes ao vazamento do sulfeto de hidrogênio em unidades básicas de processamento do petróleo (unidade de destilação atmosférica, coqueamento retardado e hidrotratamento), o último cenário busca rotas de evacuação em caso de acidente na refinaria hipotética, sem identificação da origem do vazamento do H2S. Além disso, também foi realizada uma análise de sensibilidade a fim de comprovar o modo de obtenção de alguns parâmetros relacionados ao tempo de evacuação.
The optimization of evacuation routes is considered an important asput on the development of security planning. The study of the consequences of toxic clouds is very important due to its severity in relation to other types of accidents. Despite this, a release of toxic clouds still occurs, such as Porto de Santos (2016). Therefore, in the elaboration of this work an optimum escape routes were calculated in scenarios where the formation of toxic cloud occurs in a hypothetical petroleum refinery. The optimum routes were obtained via a Dijkstra algorithm that considers minimization of two objectives: evacuation time and individual risk during the escape. The dissertation was developed in some phases. The fisrt one was to understand the process, identify and assess the risks involved in the atmospheric distillation unit, delayed coking unit and hydrotreating unit within a refinery. The ALOHA software was used to obtain the quantitative analysis of each simulated hypothesis and reveals concentration profiles, that is, the concentration of each node that belongs to an evacuation route. The result of the previous step was applied in a program developed in C ++, where the Dijkstra algorithm was used for multi-objective optimization and with this, it showed the nodes that compose the best evacuation routes in relation to the shortest evacuation time and the shortest individual risk of that journey. In every simulated situation, we can be observe the optimal evacuation route for each objective separately and also the influence of evacuation time and individual risk on the selection of nodes for the routes and then we obtain the optimum routes. Three simulated scenarios were related to the leakage of hydrogen sulphide in basic petroleum processing units (atmospheric distillation unit, delayed coking unit and hydrotreatment unit), the last scenario search for evacuation routes in case of an accident in the hypothetical refinery, without identification of the origin of the H2S leakage. In addition, a sensitivity analysis was also performed to prove the way of obtaining some parameters related to evacuation time.
20
Ward, Paul. « A Scalable Partial-Order Data Structure for Distributed-System Observation ». Thesis, University of Waterloo, 2001. http://hdl.handle.net/10012/1161.
Texte intégralRésumé :
Distributed-system observation is foundational to understanding and controlling distributed computations. Existing tools for distributed-system observation are constrained in the size of computation that they can observe by three fundamental problems. They lack scalable information collection, scalable data-structures for storing and querying the information collected, and scalable information-abstraction schemes. This dissertation addresses the second of these problems. Two core problems were identified in providing a scalable data structure. First, in spite of the existence of several distributed-system-observation tools, the requirements of such a structure were not well-defined. Rather, current tools appear to be built on the basis of events as the core data structure. Events were assigned logical timestamps, typically Fidge/Mattern, as needed to capture causality. Algorithms then took advantage of additional properties of these timestamps that are not explicit in the formal semantics. This dissertation defines the data-structure interface precisely, and goes some way toward reworking algorithms in terms of that interface. The second problem is providing an efficient, scalable implementation for the defined data structure. The key issue in solving this is to provide a scalable precedence-test operation. Current tools use the Fidge/Mattern timestamp for this. While this provides a constant-time test, it requires space per event equal to the number of processes. As the number of processes increases, the space consumption becomes sufficient to affect the precedence-test time because of caching effects. It also becomes problematic when the timestamps need to be copied between processes or written to a file. Worse, existing theory suggested that the space-consumption requirement of Fidge/Mattern timestamps was optimal. In this dissertation we present two alternate timestamp algorithms that require substantially less space than does the Fidge/Mattern algorithm.
21
Zhang, Ning. « Shortest Path Queries in Very Large Spatial Databases ». Thesis, University of Waterloo, 2001. http://hdl.handle.net/10012/1156.
Texte intégralRésumé :
Finding the shortest paths in a graph has been studied for a long time, and there are many main memory based algorithms dealing with this problem. Among these, Dijkstra's shortest path algorithm is one of the most commonly used efficient algorithms to the non-negative graphs. Even more efficient algorithms have been developed recently for graphs with particular properties such as the weights of edges fall into a range of integer. All of the mentioned algorithms require the graph totally reside in the main memory. Howevery, for very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), the requirement cannot be satisfied in most cases, so the algorithms mentioned above are not appropriate. My objective in this thesis is to design and evaluate the performance of external memory (disk-based) shortest path algorithms and data structures to solve the shortest path problem in very large digital maps. In particular the following questions are studied:What have other researchers done on the shortest path queries in very large digital maps?What could be improved on the previous works? How efficient are our new shortest paths algorithms on the digital maps, and what factors affect the efficiency? What can be done based on the algorithm? In this thesis, we give a disk-based Dijkstra's-like algorithm to answer shortest path queries based on pre-processing information. Experiments based on our Java implementation are given to show what factors affect the running time of our algorithms.
22
Krauter, Michal. « Nejkratší cesty v grafu ». Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236740.
Texte intégralRésumé :
This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.
23
Bonezzi, Mirko. « GEO PHOTO ROUTING : Progettazione ed implementazione di una applicazione per routing pedonale ». Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/14427/.
Texte intégralRésumé :
La maggior parte dei servizi di routing, sia web che mobile, quando fornisce un percorso per arrivare ad una determinata destinazione, suggerisce spesso il percorso più breve. L’obbiettivo di questo progetto di tesi è dimostrare che è possibile creare un servizio di routing che non indichi solamente il percorso più breve tra 2 punti, ma anche quello più emotivamente piacevole, rilassante, che aumenti il benessere di chi lo percorre.
Per rendere ciò possibile, ci si è basati sull’utilizzo di foto geotaggate presenti su un sistema di archiviazione e condivisione foto online: Flickr. Si ipotizza che un luogo geografico in cui sono state scattate molte fotografie, sia allora un luogo piacevole da visitare o da cui transitare. Questa ipotesi fondamentale guida quindi alla creazione di un percorso secondario, più piacevole, che passi da determinati punti di interesse.
In questo elaborato viene descritta l’implementazione e la progettazione di una piattaforma che abbia l’obbiettivo di mettere a disposizione degli utenti il servizio di routing appena descritto. È stato utilizzato un server Apache sul quale alcuni script PHP si occupano di gestire le richieste del Client e calcolare, tramite un opportuno algoritmo, il percorso adatto alle loro richieste. Inoltre è stata sviluppata un’applicazione Android, Client-side, su cui l’utente può effettuare richieste e visualizzare percorsi.
24
Kubínová, Zuzana. « Analýza datového toku ve Fly-by-Wire systému ». Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2010. http://www.nusl.cz/ntk/nusl-228973.
Texte intégralRésumé :
Software implementovaný v rámci Fly-by-Wire systému firmy Honeywell je složen z mnoha modelů implementovaných v systému Simulink. Tato práce se zabývá hledáním přímých a nepřímých spojitostí mezi jednotlivými signály v systému těchto modelů. Jako vhodný aparát je zvolena teorie grafů. Na základě modelů jsou vygenerovány grafy a úloha nalézt spojitost mezi signály je převedena na úlohu nalézt cestu mezi dvěma vrcholy grafu. Známé algoritmy k vyhledávání cest v grafech určují délku nebo váhu nalezené cesty. Pro tuto aplikaci je ale potřeba rozlišovat cesty primární a sekundární bez ohledu na jejich délku. Proto jsou tyto známé algoritmy upraveny.
25
Unzeitig, Lubomír. « Model pokrytí území buňkové sítě ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2008. http://www.nusl.cz/ntk/nusl-217688.
Texte intégralRésumé :
This work deals with a mobile signal propagation in electromagnetic wave form in a real environment of city microcell. The electromagnetic wave passing through the city environment is affected by many kinds of mechanism. It includes especially diffraction along vertical edges of buildings, diffraction across building roofs and buildings or ground refraction. These mechanisms are time variable. If we want to predicate them, we have to use sort of approached model. For an experimental part of this work, the Berg’s recursive model with a possibility of path loses or signal level prediction in a selected microcellular system is chosen. The software for a cellular network coverage is created on the basis of this fact. Its advantage is a possibility of up to five base stations placing and many kinds of settings, e.g. operating frequency, base station transmitting power, base and mobile station antennas height etc. There is a possibility of system GSM 900, GSM 1800 or UMTS choice. The Berg’s recursive model features are checked by simulations on experimental and real maps of build-up area.
26
Horák, Filip. « Optimální plánování trasy pro elektromobily ». Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2021. http://www.nusl.cz/ntk/nusl-442827.
Texte intégralRésumé :
This master’s thesis is about optimal route planning for electric vehicles. The first, theoretical part of this work introduces the issue and describes several heuristic methods that have been used to address optimization tasks. A practical part of the thesis is based around software implementation of the methods described earlier. Finally, several experiments and comparisons of obtained results are carried out.
27
Vaidya, Rohan. « Optimum Support Structure Generation for Additive Manufacturing using Unit Cell Structures and Support Removal Constraint ». University of Cincinnati / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1490354059543447.
Texte intégral
28
Dupuis, Damien. « Knik : Routeur global pour la plate-forme CORIOLIS ». Paris 6, 2009. http://www.theses.fr/2009PA066166.
Texte intégralRésumé :
L’évolution récente des technologies nanométriques et la taille des problèmes à traiter ont entraîné un regain d’intérêt pour l’étude et le développement d’outils de placement / routage dans le milieu académique. Le but de cette thèse est l’étude et la mise en oeuvre d’un outil de routage global. L’objectif principal de la phase de routage global est d’effectuer la répartition globale des interconnexions à partir d’une modélisation simplifiée des ressources de routage. La solution produite est définie par un ensemble d’arbres de Steiner dont chacun relie les connecteurs du net auquel il est associé. Dans cette thèse, nous présentons KNIK l’outil de routage global intégré à la plate-forme CORIOLIS. Nous modélisons les ressources à l’aide d’une structure mémoire compacte et légère qui nous permet de mettre en oeuvre une approche séquentielle basée sur l’algorithme de Dijkstra et une méthode originale pour résoudre les problèmes de sur-congestion. Nous avons développé un outil d’analyse et de visualisation nous permettant de valider et d’évaluer notre outil. Les performances obtenues sont comparables à celles des meilleurs routeurs globaux académiques actuels
29
Östholm, Eric, et Anton Karlsson. « Pathfinding in the forest ». Thesis, Linköpings universitet, Interaktiva och kognitiva system, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-166563.
Texte intégralRésumé :
Dijkstra’s algorithm used for pathfinding in a grid type setting consisting of forest geodata with multiple attributes. A cost analysis was performed regarding the memory required to run the application. This cost analysis yielded in a space complexity of O(n), and a class structure with focus on low memory usage while still maintaining desired functionality. The test shows a reduction of about 17,9% in memory usage compared to without memory saving measures. The algorithm and class structure are used in a web-based application implemented with JavaScript.
30
Echeverría, Solís Álvaro Ricardo. « Evaluación de tiempos de respuesta para el Cuerpo de Bomberos de Santiago :|nuevo modelo de ruteo, validación y métricas de desempeño del sistema actual ». Tesis, Universidad de Chile, 2013. http://www.repositorio.uchile.cl/handle/2250/114102.
Texte intégralRésumé :
Magíster en Gestión de OperacionesIngeniero Civil Industrial
Encontrar el camino mínimo en un grafo dirigido es un problema clásico pero de tremenda repercusión e importancia para un sistema de emergencia, donde cada segundo es vital para poder minimizar las pérdidas humanas. De esta forma, este trabajo de tesis se enfoca en el desarrollo de un algoritmo de caminos mínimos para el Cuerpo de Bomberos de Santiago basado en un Dijkstra inverso implementado con Binary Heaps. Además, se construye un grafo dirigido de la Región Metropolitana de Chile donde, con información de las velocidades de buses del sistema público chileno, se puede recrear la velocidad en cada uno de los arcos a distintas horas del día. Esto permite obtener por primera vez un orden de despacho para cada emergencia que enfrenta el Cuerpo de Bomberos de Santiago, considerando aspectos de congestión. Además, y debido a la diferente naturaleza de los tiempos de traslado entre Transantiago y CBS, se comparan los tiempos obtenidos por el algoritmo con los datos históricos del Cuerpo para calibrar dichas velocidades. Así, estos análisis llevan a la construcción del "Factor Bomberos'', una función de corrección que depende del horario de la emergencia, la zona de Bomberos que se está atendiendo y la distancia total recorrida por el carro elegido para asistir. Por otra parte, se estudia el sistema de zonas que utiliza el Cuerpo de Bomberos de Santiago para sus despachos y se logra comprobar que esto le resta eficiencia y flexibilidad a su despacho. El sistema vigente no considera variaciones a través del día, lo que se comprobó es un factor importante al momento de definir el orden de despacho. Además, la gran mayoría de las zonas presentan diferentes "sub-zonas'' de atención, lo que es muy alto en los sectores de alta concentración de compañías. Adicionalmente, se estudia cómo se comportan los sistemas (actual y el propuesto) ante estándares internacionales (90% de los despachos por debajo de 5 minutos). El primero de ellos tiene sólo un cumplimiento del 56.6 % y el segundo eleva este cumplimiento hasta el 68.45%. Factores como la reubicación de ciertas compañías permitirían elevar dicho estándar hasta un nivel mayor.
31
Williams, Vincent Troy. « An Experimental Study of Distance Sensitivity Oracles ». Scholar Commons, 2010. http://scholarcommons.usf.edu/etd/3697.
Texte intégralRésumé :
The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by
Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the
shortest distances and paths between vertices with any given single failure in constant
time without reconstructing the oracle. Using their paper as a guideline, we have
implemented their algorithm in C++ and recorded each step in this thesis. Each step
has its own pseudo-code and its own analysis to prove that the entire oracle construction
stays within the stated running time and total space bounds, from the authors. The
effciency of the algorithm is compared against that of the brute-force methods total
running time and total space needed. Using multiple test cases with an increasing
number of vertices and edges, we have experimentally validated that their algorithm
holds true to their statements of space, running time, and query time.
32
SIMÃO, Alessandro da Silva. « Modelagem e simulação do transporte de minério de ferro no norte do Brasil em situações de contingência ». Universidade Federal de Pernambuco, 2017. https://repositorio.ufpe.br/handle/123456789/25319.
Texte intégralRésumé :
Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-07-31T19:58:00Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Alessandro da Silva Simão.pdf: 1748249 bytes, checksum: 26a81e46a0366089ca679e925e21388d (MD5)Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-01T21:48:43Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Alessandro da Silva Simão.pdf: 1748249 bytes, checksum: 26a81e46a0366089ca679e925e21388d (MD5)
Made available in DSpace on 2018-08-01T21:48:43Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Alessandro da Silva Simão.pdf: 1748249 bytes, checksum: 26a81e46a0366089ca679e925e21388d (MD5) Previous issue date: 2017-03-09
Esta pesquisa investiga a possibilidade de transporte do minério de ferro na região Norte, com utilização de modais alternativos (ex. rodoviário e aquaviário), devido a contingências na Estrada de Ferro Carajás geralmente causadas por grupos étnicos e sociais. Inicialmente é entendido o cenário atual em questão, que mostra de um lado as jazidas da Província Mineral de Carajás, considerada como origem da matéria-prima e o porto Ponta da Madeira como o destino do minério de ferro. Em seguida, faz-se um levantamento das ligações alternativas entre esses pontos envolvendo rodovias, ferrovias e vias aquáticas levando-se em conta infraestrutura existente, porém não necessariamente utilizada, bem como planejada para entrar em operação nos próximos anos. A modelagem da rede de transporte tanto com infraestrutura atual como planejada é realizada por meio do problema do caminho mínimo. São utilizadas métricas de distância, tempo e custo para caracterizar a rede e diversos cenários de contingência são analisados. O algoritmo de Dijkstra é empregado como método de resolução em cada cenário e os caminhos ótimos são obtidos em termos de distância, tempo ou custo.
This research investigates the possibility of transportation of iron ore in the North region, using alternative modes (eg road and waterway), due to contingencies on the Carajás Railroad generally caused by ethnic and social groups. Initially the present scenario is understood, which shows, on the one hand, the deposits of the Carajás Mineral Province, considered as the source of the raw material and the port of Ponta da Madeira as the destination of the iron ore. Next, a survey is made of the alternative connections between these points involving highways, railways and waterways taking into account existing infrastructure, but not necessarily used, as well as planned to start operating in the coming years. The modeling of the transport network with both current and planned infrastructure is performed through the minimum path problem. Distance, time and cost metrics are used to characterize the network and several contingency scenarios are analyzed. The Dijkstra algorithm is used as the resolution method in each scenario and optimal paths are obtained in terms of distance, time or cost.
33
Silva, Inara Soldera Romano da 1982. « Utilização de um algoritmo de caminho mínimo no processo de recolhimento do palhiço da cana-de-açúcar / ». Botucatu : [s.n.], 2009. http://hdl.handle.net/11449/90600.
Texte intégralRésumé :
Orientador: Helenice de Oliveira Florentino SilvaBanca: Adriana Cristina Cherri Nicola
Banca: Odivaldo José Seraphim
Resumo: A atual preocupação com o meio ambiente tem feito com que empresas produtoras de cana-de-açúcar invistam na mudança do sistema de colheita. Essa mudança consiste na redução da queima do canavial na pré-colheita e na utilização do corte mecanizado com cana crua. Porém, a colheita com corte mecanizado torna disponível a biomassa residual e sem as queimadas e com o maior acúmulo do palhiço sobre o solo, criamse condições favoráveis para o aparecimento de parasitas e atraso da brota da cana, comprometendo a próxima safra. Vários autores mostram a viabilidade do uso do palhiço na produção de energia. Pois, além do potencial energético desta biomassa, têm-se como vantagens as questões ambientais, a manutenção de empregos e a substituição dos recursos energéticos de fontes naturais. Mas, as grandes dificuldades ainda encontradas para aproveitamento desse resíduo para geração de energia são o grande número de maquinário envolvido no sistema de coleta deste resíduo e o alto custo que este processo demanda, principalmente o custo com transporte. O presente trabalho tem como objetivo propor aplicações de técnicas matemáticas de otimização para auxiliar o planejamento do recolhimento do palhiço da cana-de-açúcar para aproveitamento na geração de energia, estudando a melhor forma de carregamento dos fardos de palhiço, facilitando o transporte, diminuindo custos e desgastes de maquinários. Para isto, é sugerido o uso de técnicas de agricultura de precisão para mapear o palhiço enfardado, desta forma pode-se definir uma rota para recolher os fardos no campo e transportá-los para o centro de processamento. Para determinação da rota, propõe-se o uso do algoritmo de menor caminho da teoria de grafos, utilizando uma variação do algoritmo de Dijkstra.
Abstract: The current concern with the environment has made sugar cane growers invest in changing their harvesting system. This change consists of the reduced burning of cane fields before harvesting and the use of mechanized cutting for raw canes. However, mechanized harvesting makes residual biomass available and, without the burning, the major accumulation of crop residue on the ground, creating favorable conditions for the emergence of parasites and delay of new shoots, affecting the next crop. Several authors show the feasibility of using crop residue for energy production. Besides the energy potential of the biomass, there are advantages for the environmental issues, preservation of jobs and the replacement of energy resources from natural sources. But the great difficulties still found in using this residue for power generation are the large number of machinery involved in the collection system of the waste and the high costs of this process, mainly transport costs. This paper aims to propose applications of mathematical optimization techniques to help plan the collection of sugar cane crop residue to be used for power generation, by studying the best way of loading bales of crop residue, making it easy to transport them, therefore reducing costs and wear on machinery. For this, we suggested the use of techniques of Precision Agriculture to map the baled crop residue, which allows you to define a route to pick up the bales in the field and transport them to the processing center. To determine the route, it is proposed to use the shortest path algorithm from graph theory, using a variation of Dijkstra's algorithm.
Mestre
34
Hudec, Lukáš. « Systémy dálkového měření v energetice ». Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2011. http://www.nusl.cz/ntk/nusl-218880.
Texte intégralRésumé :
The work deals with the measurement and management in power. Provides an introduction to the problems of remote meter reading, management, and describes the current situation in the field of modern technologies Smart metering and Smart grids. It also analyzed the issue of collection of networks and data collection from a large number of meters over a wide area. For the purpose of data transmission are described GPRS, PLC, DSL, ... Further, there are given options to streamline communication. This area is used hierarchical aggregation. Using k-means algorithm is a program designed to calculate the number of concentrators and their location in the group of meters. The finished program is written in Java. It has a graphical interface and shows how the calculation is conducted. To verify the results of the optimization program is given simulation model in OPNET Modeler tool. Audited results are described in the conclusion and can deduce that using the optimization program is to streamline communications.
35
« An adaptive distributed Dijkstra shortest path algorithm ». Massachusetts Institute of Technology, Laboratory for Information and Decision Systems], 1988. http://hdl.handle.net/1721.1/3061.
Texte intégral
36
Freitas, Hugo Miguel Gonçalves. « Sistemas de apoio à decisão ». Master's thesis, 2013. http://hdl.handle.net/10400.26/12571.
Texte intégralRésumé :
Esta dissertação surge da necessidade da Marinha Portuguesa no emprego das
unidades navais no cumprimento da sua missão aumentar a eficiência. Dada a atual
conjuntura económica do país existe a necessidade de otimizar a utilização dos recursos
gastos a bordo dos navios da Armada, nomeadamente o consumo de combustível durante o
trânsito no cumprimento das missões atribuídas aos navios. O cálculo das derrotas a serem
percorridas pelos navios deverá, considerar as previsões das condições meteooceanográficas.
O problema consiste na resolução de dois desafios, o primeiro prende-se
com a modelação do perfil hidrodinâmico do navio e a sua integração no cálculo, o segundo
consiste na criação de um algoritmo para determinar a melhor derrota a ser percorrida pelo
navio de modo a que este tenha um consumo estimado mais baixo, sendo que no caso desta
dissertação, foi escolhido o algoritmo de Dijkstra. Para a executar este trabalho foi necessário
dividi-lo em três fases, uma primeira onde os navios foram expeditamente modelados de
modo a obter a ordem de grandeza da reação perante os fatores meteo-oceanográficas s,
sendo esta reação traduzida numa perda de velocidade; de seguida desenvolveu-se uma
metodologia para obtenção de dados meteo-oceanográficos de forma a permitir o cálculo,
uma vez que estes devem de ser obtidos de forma rápida e acessível no mar; por último foi
criada uma aplicação que permite o cálculo da derrota ótima com recurso às capacidades
computacionais existentes a bordo sendo este validado através da análise e comparação de
várias derrotas praticadas por navios.This dissertation had its origin in the necessity of Portuguese Navy in the employment of the naval units to fulfil its mission. Given the current county´s economic state there is the necessity of optimization of the usage of spent resources on-board ships, more precisely the fuel used during the transits practiced in the fulfilment of missions. Calculation of the routes to be practiced by ships should take in account meteooceanographic weather forecasts. The solution to the problem at hand can be divided in two main challenges, the first consists in the modeling of the hydrodynamic characteristics of the ship in weather influence and the integration of that model onto the calculations, the second consists in the creation of an algorithm that determines the optimum route and allows the lowering of the estimated fuel consumption, with that in mind the algorithm chosen was Dijkstra´s algorithm. In order to reach a solution it´s necessary to divide the problem in three main phases, the first where the ship is modeled in an expedite way allowing the determination of the influence of weather factors in ship speed loss followed by the necessity of weather data that allows not only the calculation but the reception of that data at sea, lastly it is created an application that calculates the optimum route using the computer resources on board the ship, these routes are then validated by the analysis of several routes practiced.
37
Ahmed, Kawser. « 4D Fuel Optimal Trajectory Generation from Waypoint Networks ». Master's thesis, 2016. http://hdl.handle.net/10400.6/6531.
Texte intégralRésumé :
The purpose of this thesis is to develop a trajectory optimization algorithm that finds a fuel optimal
trajectory from 4D waypoint networks, where the arrival time is specified for each waypoint in the
network. Generating optimal aircraft trajectory that minimizes fuel burn and associated
environmental emissions helps the aviation industry cope with increasing fuel costs and reduce
aviation induced climate change, as CO2 is directly related to the amount of fuel burned, therefore
reduction in fuel burn implies a reduction in CO2 emissions as well.
A single source shortest path algorithm is presented to generate the optimal aircraft
trajectory that minimizes the total fuel burn between the initial and final waypoint in pre-defined
4D waypoint networks. In this work the 4D waypoint networks only consist of waypoints for climb,
cruise and descent phases of the flight without the takeoff and landing approach. The fuel optimal
trajectory is generated for three different lengths of flights (short, medium and long haul flight) for
two different commercial aircraft considering no wind.
The Results about the presented applications show that by flying a fuel optimal trajectory,
which was found by implying a single source shortest path algorithm (Dijkstra’s algorithm) can lead
to reduction of average fuel burn of international flights by 2.8% of the total trip fuel. By using the
same algorithm in 4D waypoints networks it is also possible to generate an optimal trajectory that
minimizes the flight time. By flying this trajectory average of 2.6% of total travel time can be saved,
depends on the trip length and aircraft types.Esta tese tem como objetivo desenvolver um algoritmo de otimização de trajetória que permita encontrar uma trajetória de combustível ótima em uma redes de waypoint em 4D, onde o tempo de chegada é específico para cada waypoint da rede. Ao criar uma trajetória ótima que minimize o consumo de combustível da aeronare e as suas respetivas emissões poluentes, ajuda a indústria da aviação não só a lidar com o aumento nos custos dos combustíveis, bem como a reduzir a sua contribuição nas alterações climáticas, pois o CO2 está diretamente relacionado com a quantidade de combustível queimado, logo uma redução no seu consumo implica que haja também uma redução nas emissões de CO2. O algoritmo “single source shortest path” é utilizado de forma a gerar uma trajetória ótima, que minimize o consumo de combustível entre o waypoint inicial e final de redes pré-definida de waypoint em 4D. Neste trabalho, esta redes consiste num conjunto de waypoints inseridos apenas nas fases de voo de subida, cruzeiro e descida, ignorando assim as fases de descolagem e aterragem. A trajetória de combustível ótima é criada para dois aviões comerciais diferentes em três distâncias de voo também diferentes (voo curto, médio e longo), sem considerar o vento. Os resultados deste trabalho mostram que ao voar numa trajetória de combustível ótima, obtida através do algoritmo “single source shortest path” (Dijkstra’s algorithm), é possível reduzir o consumo total de combustível numa média de 2.8%, em voos internacionais. Utilizando o mesmo algoritmo numa rede de waypoints em 4D é também possível encontrar uma trajetória ótima que minimize o tempo de voo numa media de 2.6% do tempo total, consoante a distância da viagem e do tipo de aeronave.
38
Wu, Sheng-Yi, et 吳昇益. « Using modified Dijkstra’s algorithm to improve the movement efficiency of robocar ». Thesis, 2013. http://ndltd.ncl.edu.tw/handle/97337776645458917800.
Texte intégralRésumé :
碩士國立陽明大學
醫學工程研究所
101
Abstract In recent years, the telehealthcare is very popular. Because the tele-healthcare can keep a watchful eye on information of patients or elderly people, and handle in anytime, in anywhere and by any device, If becomes an on going nursing behavior. Based on its concept, we builded a indoor positioning system by RFID Cartesian grids, which can guide the robocar move to the designated location , then to realize the circumstances with the patient. In this field, many factors will determine whether it can be access or not, such as location-awareness, path finding and path conditions. In this study, we first introduce passive RFID tags to act as landmarks for solving location-awareness. These landmarks can not only read by robocar to determine present localization but reduce computing time for path finding searching process. For the part of path –planning, we proposed an improved graph-based algorithm for archiving obstacles avoidance and less veers into consideration, to generate an efficient path for navigation. We tested the efficiency of different path finding algorithms with the designated map, included Dijkstra’s algorithm, the collision–free algorithm (CFA) on basis of Dijkstra and our proposed method. In comparison of Dijkstra’s algorithm and CFA approach, Dijkstra’s algorithm could find the shortest path. but easily occur collision; and although CFA approach increase 3% distances, it could ensure keeping up a collision-free condition. Another aspect, in comparison of our proposed approach and CFA approach, our method increase cruising distance then CFA, due to it isn’t a shortest path . However, the aim we adopted veering angles is to emend weighting manner to condition of mobile robocar cruising. And our result proved the ideal shortest path is not minimum time to access destinations in practical environment.
39
Petrášová, Tereza. « Dijkstrův algoritmus v problému proudění chodců ». Master's thesis, 2018. http://www.nusl.cz/ntk/nusl-387371.
Texte intégralRésumé :
Title: On the Dijkstra's algorithm in the Pedestrian Flow Problem Author: Tereza Petrášová Department: Department of Numerical Mathematics Supervisor: doc. RNDr. Jiří Felcman, CSc., Department of Numerical Mathe- matics Abstract: The pedestrian flow problem is described by a coupled system of the first order hyperbolic partial differential equations with the source term and by the functional minimization problem for the desired direction of motion. The functional minimization is based on the modified Dijkstra's algorithm used to find the minimal path to the exit. The original modification of the Dijkstra's algorithm is proposed to increase its efficiency in the pedestrian flow problem. This approach is compared with the algorithm of Bornemann and Rasch for determination of the desired direction of motion based on the solution of the so- called Eikonal equation. Both approaches are numerically tested in the framework of two splitting algorithms for solution of the coupled problem. The former splitting algorithm is based on the finite volume method yielding for the given time instant the piecewise constant approximation of the solution. The latter one uses the implicit discretization by a space-time discontinuous Galerkin method based on the discontinuous piecewise polynomial approximation. The numerical examples...
40
Chen, Szu-Yuan, et 陳思源. « Building Steiner Tree with Extended Dijkstra's Algorithm for Software-Defined Networking Multicast ». Thesis, 2015. http://ndltd.ncl.edu.tw/handle/59609745107487089452.
Texte intégralRésumé :
碩士國立中央大學
資訊工程學系
103
We propose a method to build multicast tree for live video streaming with Extended Dijkstra’s Shortest Path algorithm and Modified Selective Closest Terminal First Steiner Tree algorithm. It can decrease the delay time, the volume of package transmission, and the usage of Internet bandwidth. We can allocate network resources more efficiently to reduce the heavy congestion in the rush hour. Extended Dijkstra’s Shortest Path algorithm considers not only the edge weights but also the node weights for building package transmission path with the shortest delay. In Modified SCTF Steiner Tree algorithm, we let the node near to source have higher priority to add in priority queue. In this way, we can decrease the number of internal node in Steiner tree for using less bandwidth. We take our experiment in EstiNet simulator with different network topology, different number of servers, different number of multicasting groups, and different number of multicasting subscribers. We simulate our method with constant bit rate and modified Ryu controller. We compare the average end-to-end delay and total bandwidth consumption between our algorithm and other six kinds of related algorithms. The results show that the proposed algorithm seconds only to the exhaustive optimal Steiner tree algorithm in total bandwidth consumption, and has the least average end-to-end delay after Extended Dijkstra’s Shortest Path algorithm.
41
HUANG, I.-CHENG, et 黃一誠. « Combining Segmental NURBS Curve and Modified Dijkstra’s Algorithm for Trajectory Planning and Application ». Thesis, 2008. http://ndltd.ncl.edu.tw/handle/67686633680227153971.
Texte intégralRésumé :
碩士國立臺灣大學
電機工程學研究所
96
This paper proposed a solution for the problem of path planning for a flying vehicle (airplane) moving in complex areas. The purpose is to generate a smooth segmental NURBS trajectory connecting the initial point (for taking off) and the final point (for landing) so that no collisions with obstacle areas (such as forbidden regions, or mountain, etc.) under various constraints conditions. The modified Dijkstra’s algorithm will be used to search for the shortest path. Obstacle areas are modeled by polygonal sets with the appropriate safety margins. To find a smooth trajectory which meets the capability of the flying vehicle, the method of segmental NURBS curves is adopted. The curvature restrictions and kinematic constraints are introduced into the constrained optimization problems. The control points are generated to characterize the curve forms. The syntheses of the above concepts lead to successful approaches for path planning, which are demonstrated by simulation results based on a software package using MATLAB GUI toolbox. It’s also good for related flying trajectory planning and application on Air Traffic Control by using the above methods.
42
Ming-Yi, Chiu. « The Correctness and Stabilization Time of Dijkstra's 4-state Mutual Exclusion Self-stabilizing Algorithm ». 2001. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0009-0112200611295685.
Texte intégral
43
Chiu, Ming-Yi, et 邱明義. « The Correctness and Stabilization Time of Dijkstra's 4-state Mutual Exclusion Self-stabilizing Algorithm ». Thesis, 2001. http://ndltd.ncl.edu.tw/handle/92544742831797384570.
Texte intégralRésumé :
碩士元智大學
資訊工程學系
89
E. W. Dijkstra first introduced the concept of self-stabilization in a distributed system in 1974. In his classic paper in 1974, he proposed three elegant self-stabilizing algorithms for the mutual exclusion problem in a ring system. In this paper, a concise proof is provided for the correctness of the second algorithm, which requires 4 states. The time complexity of the algorithm is also computed to be O(n*n).
44
LIU, TZU-JUNG, et 劉子榮. « Design and Implementation of an Electric Energy Saving System by Using Dijkstra's Algorithm for Appliance Scheduling ». Thesis, 2018. http://ndltd.ncl.edu.tw/handle/9m8ec5.
Texte intégralRésumé :
碩士國立高雄應用科技大學
電機工程系博碩士班
106
In this thesis, a smart home electric energy management system is implemented by combining smart plug, smart meter, smart mobile devices, database, and computing server. Both of the smart meter and the smart plug consists of a control and monitoring unit and a meter reading communicating interface unit. By connecting to the internet via Wi-Fi media, user can use smart phone to remotely monitor and control the operation of appliance, send instruction to the computing server, and obtain real-time electric power information. Besides, the study also develops appropriate algorithm for performing effective electric power saving and reducing electric energy cost based on the Dijkstra algorithm including the billing policy with the time of use price. Finally, in order to verify the performance of the proposed electricity-saving electrical scheduling system, the system prototype was built and tested in the laboratory, and the test results illustrate the advantages of the appliance scheduling algorithm, and the feasibility of the proposed smart home electric energy management system is also validated.
45
Sung, Pen-Hsiang, et 宋本祥. « An Analysis Model to Nosocomial Communicable Diseases Based on RFID and Dijkstra's Algorithm : Novel Influenza as an Example ». Thesis, 2010. http://ndltd.ncl.edu.tw/handle/03092183234384796217.
Texte intégralRésumé :
碩士國立屏東科技大學
工業管理系所
98
The threats resulted from the communicable diseases to the health and life of the human beings are very important issues always. People who in need of medical treatment were quite increasing during the pandemic of H1N1 influenza in domestic. Due to the short incubation period and high infection rate of influenza virus, neither collection of patient specimens nor quarantine, the epidemic of novel influenza will result in patient to contact the source to be a reservoir to occur a phenomenon of cross infection in the hospital under some certain conditions. Consequently, based on RFID to track the location of patients within the control area for comparing each other with reference to the general transmission characteristics of novel influenza virus, this study is to build an analysis model to nosocomial communicable diseases by means of Dijkstra’s algorithm analysing the shortest time and the velocity of diseases to be infected, and the results were found that it apparently shows the serious level of cross infection situation from the transmitted relationship of all the patients, thus the advisories can be made concretely to take measures for the reference of hospitals to achieve the goal of safety in healthcare.
46
Alagarsamy, K. « Some Theoretical Contributions To The Mutual Exclusion Problem ». Thesis, 1997. http://etd.iisc.ernet.in/handle/2005/1833.
Texte intégral