0
Existe-t-il un algorithme connu pour résoudre ce problème?Rayon de couverture minimum en n dimensions
A
Répondre
2
Il y a un problème connexe qui est résoluble avec un algorithme glouton: compte tenu des points et un rayon , trouver le nombre minimum de cercles. Cet algorithme place de façon répétée un cercle dont le bord gauche se trouve sur le point découvert le plus à gauche, s'exécutant dans le temps O (n) sur les points triés par x.
Pour obtenir un algorithme pour le problème demandé, triez les points une fois, puis utilisez la recherche binaire pour trouver le rayon le plus faible qui résultera de la plupart des cercles. En supposant que les coordonnées x peuvent être représentées par des mots machine, cela devrait être bon. (Si ce n'est pas le cas, il existe d'autres algorithmes.)
+0
@Blender Il vous suggère d'utiliser la recherche binaire sur la réponse et je suis d'accord avec lui. Similaire à cette question: [link] (http://stackoverflow.com/questions/40189551/arrange-n-items-in-k-nonempty-groups-such-that-the-difference-between-the-minimu/40205972 # 40205972) et [lien] (http://stackoverflow.com/questions/39673898/divide-array-into-k-contiguos-partitions-such-that-sum-of-maximum-partition-is-m/39675098# 39675098) – Tempux
Bien sûr, il existe une sorte d'algorithme que vous pourriez utiliser. Quel genre de complexité du temps essayez-vous d'atteindre? – ollpu
Cela demande un algorithme, pas d'aide avec le code brisé – thecoshman
Les centres sont-ils aussi des entiers, ou pourraient-ils être des moitiés? – m69