Trouver le nombre minimum de rayons pour recouper tous les arcs

Question

Il y a une question dans Éléments de programmation Entrevues que j'ai essayé de résoudre mais qui a échoué. Supposons qu'on nous donne un tableau d'intervalles de la forme (d1, d2) où d1 et d2 sont des valeurs en degrés représentant les angles de début et de fin d'un arc, où 0 degrés est l'axe des ordonnées. Ces intervalles peuvent se chevaucher, et vous pouvez avoir un intervalle comme (350, 10). Quel est le nombre minimum de rayons que vous pouvez tirer pour croiser tous les intervalles? Un rayon peut être représenté sous la forme d'un angle en degrés par rapport à l'axe des ordonnées. J'ai essayé de trier par points de terminaison et de voir si chaque point de terminaison se croise avec l'intervalle suivant, mais je ne pouvais pas comprendre comment gérer les intervalles de chevauchement tels que (340, 350), (350, 20).

Answer 1

Pour optimiser le nombre d'arcs, vous NE POUVEZ PAS lancer un rayon de A vers B et un autre rayon de C vers D si A et C se croisent, par exemple. Le point clé est de trouver tous les points d'intersection entre les arcs (et de les trier par les points qui appartiennent à plusieurs arcs). Après le tri, obtenez l'angle qui appartient à plusieurs arcs et définissez un rayon à un autre point appartenant à un autre jeu d'arcs différent du premier. Le plus différent, le meilleur. Vous pouvez juste parcourir les angles et vérifier celui qui correspond le mieux.

Answer 2

1. créer la table tab de tous les angles utilisés (bords d'intervalle)

   ne doit contenir que des angles distincts

2. fixés tous les arcs comme utilisé

3. angle de trouver à partir de tab qui croise la plupart des arcs non utilisés
4. ajouter comme rayon
5. ne comprennent pas cet angle de tab
6. ensemble tous recoupé rayons utilisé
7. boucle # 2 jusqu'à ce qu'aucun arc utilisé ou de l'angle reste

Ceci diminuera significativement le nombre de rayons mais ne garantira pas une solution optimale !!! Pour une solution vraiment optimale, vous devrez utiliser l'approche genere & test à la place. Voici quelques code C++ pour cela:

#include <math.h> 
struct _arc 
    { 
    int d0,d1; // [deg] CW arc angular interval 
    int flag; // temp 
    }; 
const int N=8; // number of arcs 
_arc arc[N]; // arcs table 
int ray[N+N],rays=0; // rays table and number of rays 
//--------------------------------------------------------------------------- 
void generate() 
    { 
    int i; 
    _arc *a; 
    for (a=arc,i=0;i<N;i++,a++) 
     { 
     a->d0=Random(361); 
     a->d1=Random(361); 
     a->flag=0; 
     } 
    } 
//--------------------------------------------------------------------------- 
void solve() 
    { 
    int i,j,k,e,d0,d1,d,n0,n1; 
    _arc *a; 
    int tab[N+N],n; 
    rays=0; 
    // clear flag and make a asc sorted list of angles 
    for (i=0;i<N+N;i++) tab[i]=0; 
    for (a=arc,i=0,n=0;i<N;i++,a++) 
     { 
     a->flag=0; 
     // insert d0 
     for (d=a->d0,j=0;j<n;j++) 
      { 
      if (tab[j]==d) { j=-1; break; } 
      if (tab[j]> d) { for (k=n;k>j;k--) tab[k]=tab[k-1]; tab[j]=d; n++; j=-1; break; } 
      } if (j>=0) { tab[n]=d; n++; } 
     // insert d1 
     for (d=a->d0,j=0;j<n;j++) 
      { 
      if (tab[j]==d) { j=-1; break; } 
      if (tab[j]> d) { for (k=n;k>j;k--) tab[k]=tab[k-1]; tab[j]=d; n++; j=-1; break; } 
      } if (j>=0) { tab[n]=d; n++; } 
     } 
    // find ray with max number of overlaps 
    for (e=1;e;) // loop while not all arcs done 
     { 
     e=0; 
     for (n1=0,k=-1,j=0;j<n;j++) 
      { 
      // count intersections into d0 
      d=tab[j]; n0=0; if (d<0) continue; 
      for (a=arc,i=0;i<N;i++,a++) 
      if (a->flag==0) // skip already done arcs 
       { 
       d0=a->d0; 
       d1=a->d1; 
       if (d0>d1) { if ((d>=d0)||(d<=d1)) n0++; } 
       else  { if ((d>=d0)&&(d<=d1)) n0++; } 
       } 
      // remember max k-index, d1-intersections 
      if (n1<n0) { k=j; n1=n0; } 
      } 

     if (!n1) break; // stop if no angle left (error) 
     // add ray 
     ray[rays]=tab[k]; rays++; 
     // exclude arcs 
     d=tab[k]; 
     for (a=arc,i=0;i<N;i++,a++) 
     if (a->flag==0) // skip already done arcs 
      { 
      e=1; 
      d0=a->d0; 
      d1=a->d1; 
      if (d0>d1) { if ((d>=d0)||(d<=d1)) a->flag=1; } 
      else  { if ((d>=d0)&&(d<=d1)) a->flag=1; } 
      } 
     } 

    // debug: set flag=1 for ray intersected arces (for visual check) 
    for (a=arc,i=0;i<N;i++,a++) 
    for (a->flag=0,j=0;j<rays;j++) 
     { 
     d =ray[j]; 
     d0=a->d0; 
     d1=a->d1; 
     if (d0>d1) { if ((d>=d0)||(d<=d1)) a->flag=1; } 
     else  { if ((d>=d0)&&(d<=d1)) a->flag=1; } 
     } 
    } 

et aperçu:

Comme vous pouvez le voir jeter les rayons à travers les points de bord si vous avez besoin de rayons différents, vous devez modifier ce une bit (comme utiliser l'angle médian du chevauchement commun qui conduirait à plus de rayons de grossier). Le code est loin d'être optimisé Je l'ai codé juste pour m'amuser en ce moment ...

Pour améliorer cela, vous pouvez trier les listes et utiliser des recherches à distance au lieu (similaire à la fusion des listes triées) Dans l'état actuel code il n'y a pas profité du tri ...