Property |
Value |
dbo:abstract
|
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. Une formalisation du problème est la suivante. Étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que la moyenne des distances des points de V au plus proche centre soit minimisée. Le problème est le plus souvent exprimé dans un espace métrique. Il s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. On peut aussi considérer que les sommets sont divisés en deux catégories : les sommets ouvrables, et les sommets à couvrir. Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser. (fr)
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. Une formalisation du problème est la suivante. Étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que la moyenne des distances des points de V au plus proche centre soit minimisée. Le problème est le plus souvent exprimé dans un espace métrique. Il s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. On peut aussi considérer que les sommets sont divisés en deux catégories : les sommets ouvrables, et les sommets à couvrir. Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser. (fr)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 4760 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:année
| |
prop-fr:auteur
| |
prop-fr:langue
| |
prop-fr:site
|
- A compendium of NP optimization problems (fr)
- Cours Advanced algorithms de Sanjeev Arora à l'université Stanford (fr)
- A compendium of NP optimization problems (fr)
- Cours Advanced algorithms de Sanjeev Arora à l'université Stanford (fr)
|
prop-fr:titre
|
- Minimum k-median (fr)
- Minimum k-median (fr)
|
prop-fr:url
| |
prop-fr:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. (fr)
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. (fr)
|
rdfs:label
|
- K-medians clustering (en)
- K-médiane (fr)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |