2
Étant donné un ensemble de N segments de ligne horizontaux disjoints (parallèles à l'axe X) de longueur variable et de distances perpendiculaires variables, nous devons placer des nombres minimaux de disques d'unité qui recoupent au moins un segment de ligne ou un disque d'unité de sorte que l'union des segments de ligne et des disques soit connectée. Existe-t-il un algorithme existant ou tout ce que je peux utiliser pour résoudre ce problème?Couverture de N segments de ligne avec des disques unitaires
Eh bien, il s'agit d'un cas spécial de Hitting Set, donc vous pouvez le formuler et le résoudre comme ça, mais c'est un problème NP-difficile. Il est possible qu'un algorithme plus rapide (même poly-temps) existe qui exploite mieux les propriétés de votre problème (par exemple, si un disque rencontre une ligne à y1 de x11 à x12> x11 et une autre ligne à y2> y1 de x21 à x22> x21, alors il frappe nécessairement toutes les lignes contenant un point à l'intérieur du carré (max (x11, x21), y1, min (x12, x22), y2))). –
Pouvez-vous s'il vous plaît expliquer la solution plus? Il serait également utile d'obtenir une solution optimale ou (1+ e) approximative pour cela. – Coder404
Je crains qu'une telle garantie de qualité d'approximation ne soit en dehors de mon domaine d'expertise. La formulation de l'ensemble de frappe est évidente; Si vous souhaitez incorporer l'observation sur les lignes pouvant être touchées, il est facile de le faire dans un algorithme de branchement et de liaison. –