Publication

Euclidean Matching Problems and the Metropolis Algorithm

Thomas Liebling
1986
Journal Articles

Résumé

The Euclidean matching problem consist in partitionning a cloud of n points into n/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minmized, resp. maximized. In this paper the thermodynamically inspired approach of simulated annealing is applied to find good approximations to large scale problems of the above kind. Also the asymptotic behaviour of random euclidean matching problems is studied, in particular computational results on the rate of convergence towards the asymptote are given.

Source officielle

https://infoscience.epfl.ch/entities/publication/c1e2a20b-6b3b-4051-9f8b-e3b1dbd5fafb

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Thomas Liebling
1986
Journal Articles

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/c1e2a20b-6b3b-4051-9f8b-e3b1dbd5fafb

À propos de ce résultat

Concepts associés (21)

Problème du voyageur de commerce

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.

Computational anatomy

Computational anatomy is an interdisciplinary field of biology focused on quantitative investigation and modelling of anatomical shapes variability. It involves the development and application of mathematical, statistical and data-analytical methods for modelling and simulation of biological structures. The field is broadly defined and includes foundations in anatomy, applied mathematics and pure mathematics, machine learning, computational mechanics, computational science, biological imaging, neuroscience, physics, probability, and statistics; it also has strong connections with fluid mechanics and geometric mechanics.

Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance. These names come from the ancient Greek mathematicians Euclid and Pythagoras, although Euclid did not represent distances as numbers, and the connection from the Pythagorean theorem to distance calculation was not made until the 18th century.

Afficher plus

Publications associées (5)

Afficher plus

Euclidean Matching Problems and the Metropolis Algorithm

Chattez avec Graph Search

BioReason-Pro: Advancing Protein Function Prediction with Multimodal Biological Reasoning

First benchmark between the KINetic Deterministic NEutral Solver (KINDNES) and EIRENE

MATHICSE Technical Report: Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries