J'essaie de résoudre le problème de couverture suivant. Il y a émetteurs avec une zone de couverture de 1 km et récepteurs. Décidez en que tous les récepteurs sont couverts par n'importe quel émetteur. Tous les récepteurs et émetteurs sont représentés par leurs coordonnées et...
En raison de la nature de la question, je dois inclure beaucoup d'informations de base (parce que ma question est: comment puis-je restreindre cela?) Cela dit, cela peut être résumé (à ma connaissance) comme: Quelles méthodes existent pour trouver des optimums locaux sur des espaces de recherche...
Les exemples courants de problèmes NP-difficiles (clique, 3-SAT, vertex cover, etc.) sont du type où nous ne savons pas si la réponse est "oui" ou "non" au préalable. Supposons que nous ayons un problème dans lequel nous savons que la réponse est oui, en outre, nous pouvons vérifier un témoin en...
J'ai un ensemble de points qui sont définis dans un espace métrique - donc je peux mesurer une «distance» entre les points mais rien d'autre. Je veux trouver le point le plus central de cet ensemble, que je définis comme le point avec la somme minimale des distances à tous les autres points. Le...
On me donne n objets, et un ensemble de n permutations de ces n objets (sur n! Permutations totales). Il y a une vraie permutation sous-jacente, dont je sais qu'elle fait partie de l'ensemble des n permutations, mais je ne sais pas laquelle. Un oracle connaît cependant la véritable permutation....