Поиск минимального количества лучей для пересечения всех дуг

Question

В «Элементах программирования» есть вопрос, который я пытался решить, но не увенчался успехом. Предположим, нам задан массив интервалов вида (d1, d2), где d1 и d2 - значения в градусах, представляющих начальный и конечный углы дуги, где 0 градусов - ось y. Эти интервалы могут перекрываться, и вы можете иметь такой интервал, как (350, 10). Какое минимальное количество лучей вы можете снимать, чтобы пересечь все интервалы? Луч может быть представлен как угол в градусах от оси y.

Я пробовал сортировку по конечным точкам и видел, пересекается ли каждый конечный пункт с последующим интервалом, но я не мог понять, как бороться с перекрывающимися интервалами, такими как (340, 350), (350, 20).

Answer 1

Чтобы оптимизировать количество дуг, вы НЕ МОЖЕТЕ выбрасывать луч от А до В и другой луч от С до D, если, например, пересекаются А и С.

ключевой точкой является найти все точки пересечения между дугами (и отсортировать их по точкам, принадлежащим большему количеству дуг).

После того, как вы их отсортируете, получите угол, который относится к большему количеству дуг, и установите луч от него к другой точке, принадлежащей другому набору дуг, отличных от первого. Самое разное, тем лучше. Вы можете просто перемещать углы и проверять тот, который подходит лучше всего.

Answer 2

1. создать таблицу tab всех используемые углов (интервал ребер)

   должен содержать только отчетливые углы

2. установку всех дуги как неиспользуемый

3. угла находки из tab который пересекает большинство неиспользуемых дуг
4. добавить его в качестве луча
5. исключить этот угол от tab
6. установить все пересекались лучи, как не используется
7. цикла # 2, пока не неиспользованного дуги или угол остается

Это значительно уменьшит количество лучей, но не обеспечит оптимальное решение !!! Для действительно оптимального решения вам нужно будет использовать genere & test. Вот некоторые C++ код для этого:

#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; } 
     } 
    } 

И обзор:

Как вы можете видеть, что отбрасывать лучи через края очков, если вам нужны различные лучи вам нужно настроить это бит (например, использовать средний угол общего перекрытия, что приведет к большему количеству лучей грубого). Код далеко не оптимизирован. Я закодировал его просто для удовольствия прямо сейчас ...

Для улучшения этого вы можете сортировать списки и использовать варьировался поиски вместо (аналогичен слияния отсортированных списков) В текущем состоянии коды не существует какие-либо преимуществ берутся из сортировки ...