Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Bentley sprial search). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Qiao, Wenbao. GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens.

Degree: Docteur es, Informatique, 2018, Bourgogne Franche-Comté

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe.

In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search…

Advisors/Committee Members: Créput, Jean-Charles (thesis director).

Subjects/Keywords: Recherche en spirale Bentley; Gpu; Problème du voyageur de commerce; Massifs 2-/3-Opt mouvements; Recherche K-D; Parallèles 2-Opt; Bentley sprial search; Gpu; GPU parallel 2-Opt; Multiple 2-Opt moves; Euclidean minimum spanning tree; K-D search; 006

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Qiao, W. (2018). GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens. (Doctoral Dissertation). Bourgogne Franche-Comté. Retrieved from http://www.theses.fr/2018UBFCA020

Chicago Manual of Style (16th Edition):

Qiao, Wenbao. “GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens.” 2018. Doctoral Dissertation, Bourgogne Franche-Comté. Accessed April 01, 2020. http://www.theses.fr/2018UBFCA020.

MLA Handbook (7th Edition):

Qiao, Wenbao. “GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens.” 2018. Web. 01 Apr 2020.

Vancouver:

Qiao W. GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens. [Internet] [Doctoral dissertation]. Bourgogne Franche-Comté; 2018. [cited 2020 Apr 01]. Available from: http://www.theses.fr/2018UBFCA020.

Council of Science Editors:

Qiao W. GPU component-based neighborhood search for Euclidean graph minimization problems : Méthodes GPU de recherche par voisinage pour les problèmes de minimisation de graphes Euclidiens. [Doctoral Dissertation]. Bourgogne Franche-Comté; 2018. Available from: http://www.theses.fr/2018UBFCA020

.