Algoritmo per combinare gli intervalli di un segmento - aiuta a creare - pagina 2

Nuovo commento
  
struct SAllVariants{
   int m_cut[][2];
   int len;
   int li;
   void Init(int aLen){
      ArrayResize(m_cut,aLen);
      len=0;
   }
   void AddCut(int & a[][2],int i){
      m_cut[len][0]=a[i][0];
      m_cut[len][1]=a[i][1];
      len++;
      li=i;
   }
   void Set(SAllVariants & a){
      len=a.len;
      li=a.li;
      for(int i=0;i<len;i++){
         m_cut[i][0]=a.m_cut[i][0];
         m_cut[i][1]=a.m_cut[i][1];
      }
   }
};

SAllVariants av[];

int cut[][2];

void OnStart(){

   Print("=============================================================");
  
   // заполняем массив сотней каких-нибудь отрезков
   FillArray(cut,100);

   //=== алгоритм ====================
   
   // поправить все отрезки, чтобы первая координата была меньше второй   
   int itmp;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>cut[i][1]){
         itmp=cut[i][0];
         cut[i][0]=cut[i][1];
         cut[i][1]=itmp;
      }
   }
   
   // сортировка массива по первой координате
   ArraySort(cut);
   ArrayPrint(cut);
   // удалить отрезки нулевой длины и повтряющиеся отрезки
   bool ex;
   int ti=0;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]!=cut[i][1]){
         ex=false;
         for(int j=i-1;j>=0 && cut[j][0]==cut[i][0];j--){
            if(cut[j][0]==cut[i][0] && cut[j][1]==cut[i][1]){
               ex=true;
               break;
            }
         }
         if(!ex){
            cut[ti][0]=cut[i][0];
            cut[ti][1]=cut[i][1];
            ti++;
         }
      }
   }
   ArrayResize(cut,ti);
   
   // добавить первый отрезок в массив всех вариантов и еще отрезков с наименьшей координатой
   ArrayResize(av,1);
   av[0].Init(ArrayRange(cut,0)); // вдруг ряд получится из всех отрезков
   av[0].AddCut(cut,0);
   for(int i=1;i<ArrayRange(cut,0);i++){ 
      if(cut[0][0]==cut[i][0]){
         ArrayResize(av,ArraySize(av)+1);
         av[ArraySize(av)-1].Init(ArrayRange(cut,0));
         av[ArraySize(av)-1].AddCut(cut,i);
      }
   }

   // добавить в начало еще отрезков, начинающихся чуть позже, но не позднее конца самого длинного из начальных
   
   // на сначала найти диапазон
   int mn=av[0].m_cut[0][0];
   int mx=av[0].m_cut[0][1];
   for(int i=1;i<ArraySize(av);i++){
      mx=MathMax(mx,av[i].m_cut[0][1]);
   }
   
   // добавить
   for(int i=1;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>mn && cut[i][0]<mx){
         ArrayResize(av,ArraySize(av)+1);
         av[ArraySize(av)-1].Init(ArrayRange(cut,0));
         av[ArraySize(av)-1].AddCut(cut,i);
      }
   }   

   // а теперь самое интересное
   double r;
   bool n;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      //Comment(i," ",ArraySize(av));
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li+1;j<ArrayRange(cut,0);j++){
         if(cut[j][0]>=av[i].m_cut[av[i].len-1][1]){
            r=MathMin(r,cut[j][0]-av[i].m_cut[av[i].len-1][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li+1;j<ArrayRange(cut,0);j++){
            if(cut[j][0]-av[i].m_cut[av[i].len-1][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   }

   string str="";
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){
      str="";
      for(int j=0;j<av[i].len;j++){
         str=str+(string)av[i].m_cut[j][0]+"-"+(string)av[i].m_cut[j][1]+" ";
      }
      Print("Вариант ",i," - ",str);
   }

}
//+------------------------------------------------------------------+

void FillArray(int & a[][2],int cutCnt){
   ArrayResize(a,cutCnt);
   for(int i=0;i<cutCnt;i++){
      a[i][0]=MathRand()%30;
      a[i][1]=a[i][0]+MathRand()%15;
   }   
}

In qualche modo...

 
Dmitry Fedoseev:

In qualche modo...

Grazie! Si vede subito la mano del maestro! Lo proverò domani per vedere cosa viene fuori.

 
Dmitry Fedoseev:

In qualche modo...

Iniziato a provare il codice, creato un esempio artificiale - riempito l'array

FillArray(cut,4);
cut[0][0]=0;
cut[0][1]=1;
cut[1][0]=3;
cut[1][1]=6;
cut[2][0]=2;
cut[2][1]=5;
cut[3][0]=7;
cut[3][1]=9;

Capito:

2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)       [,0][,1]
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [0,]   0   1
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [1,]   2   5
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [2,]   3   6
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [3,]   7   9
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   Вариант 0 - 0-1 2-5 7-9

Cioè abbiamo una variante, ma ci aspettiamo anche un'altra variante.

Вариант 1 - 0-1 3-6 7-9

È possibile insegnare anche all'algoritmo a trovarlo?

 
Aleksey Vyazmikin:

Iniziato a provare il codice, creato un esempio artificiale - riempito l'array

Capito:

Cioè, abbiamo una variante, ma ci aspettiamo anche un'altra variante.

L'algoritmo può imparare anche a trovarlo?

E la variante "0-1 3-6 7-9" non è migliore della variante "0 - 0-1 2-5 7-9" - entrambe sono da 0 a 1 e hanno 2 salti di lunghezza 1 ciascuno.

In questo caso appaiono due opzioni:

1 - fare la stessa cosa, ma dalla fine della serie di salti.

2 - cercare subito non il segmento più vicino, ma con una tolleranza. Ma in questo caso ce ne saranno ancora di più se ci sono molti dati e molte sequenze di aggancio.

Tuttavia, dopo la variante 1, vorrete iniziare a costruire catene da tutte le possibili posizioni di partenza. Questo è corretto, ma la quantità di lavoro per l'algoritmo aumenta considerevolmente.

Sì, è necessario iniziare la costruzione delle varianti da ciascuno dei segmenti dell'insieme iniziale e continuare la costruzione fino all'inizio e alla fine.

 
Dmitry Fedoseev:

E l'opzione "0-1 3-6 7-9" non è migliore dell'opzione "0 - 0-1 2-5 7-9" - entrambe sono da 0 a 1 e hanno 2 salti di lunghezza 1 ciascuno.

In questo caso sono uguali, sono d'accordo, ma sono diversi e per i termini del problema dovremo stimare la somma dei loro punteggi, e finché non costruiremo una linea non sapremo il punteggio combinato di tutti i segmenti.

Dmitry Fedoseev:

Tuttavia, dopo l'opzione 1, ci sarà il desiderio di iniziare a costruire stringhe da tutte le possibili posizioni di partenza. Questo è corretto, ma la quantità di lavoro per l'algoritmo aumenta considerevolmente.

Sì, è necessario iniziare la costruzione delle varianti da ciascuno dei segmenti dell'insieme iniziale e continuare la costruzione fino all'inizio e alla fine.

Questa mi sembra anche la strategia più corretta! Tuttavia, penso che ci possano essere delle varianti duplicate.

Puoi aiutare scrivendo un po' di codice?

  
struct SAllVariants{
   
   int m_cut[][2];
   int len;

   int m_cut1[][2]; // к концу
   int len1;
   int li1;
   
   int m_cut2[][2]; // с началу
   int len2;
   int li2;   
   
   bool isDopel;
   
   void Init(int aLen){
      ArrayResize(m_cut1,aLen);
      len1=0;
      ArrayResize(m_cut2,aLen);
      len2=0;      
   }
   void AddCut1(int & a[][2],int i){
      m_cut1[len1][0]=a[i][0];
      m_cut1[len1][1]=a[i][1];
      len1++;
      li1=i;
   }
   void AddCut2(int & a[][2],int i){
      m_cut2[len2][0]=a[i][0];
      m_cut2[len2][1]=a[i][1];
      len2++;
      li2=i;
   }   
   void Set(SAllVariants & a){
      len1=a.len1;
      li1=a.li1;
      for(int i=0;i<len1;i++){
         m_cut1[i][0]=a.m_cut1[i][0];
         m_cut1[i][1]=a.m_cut1[i][1];
      }
      len2=a.len2;
      li2=a.li2;
      for(int i=0;i<len2;i++){
         m_cut2[i][0]=a.m_cut2[i][0];
         m_cut2[i][1]=a.m_cut2[i][1];
      }      
   }
   
   bool Eq(SAllVariants & a){
      if(len1!=a.len1 || len2!=a.len2){
         return(false);
      }
      for(int i=0;i<len1;i++){
         if(m_cut1[i][0]!= a.m_cut1[i][0] || m_cut1[i][1]!= a.m_cut1[i][1]){
            return(false);
         }
      }
      for(int i=0;i<len2;i++){
         if(m_cut2[i][0]!= a.m_cut2[i][0] || m_cut2[i][1]!= a.m_cut2[i][1]){
            return(false);
         }      
      }      
      return(true);
   }
   
   void Combine(){
      len=len1+len2-1;
      ArrayResize(m_cut,len);
      int j=0;
      for(int i=len2-1;i>0;i--){
         m_cut[j][0]=m_cut2[i][0];
         m_cut[j][1]=m_cut2[i][1];         
         j++;
      }
      for(int i=0;i<len1;i++){
         m_cut[j][0]=m_cut1[i][0];
         m_cut[j][1]=m_cut1[i][1]; 
         j++;
      }      
   }
};

SAllVariants av[];

int cut[][2];

void OnStart(){

   Print("=============================================================");
  
   // заполняем массив сотней каких-нибудь отрезков
   FillArray(cut,100);

   //=== алгоритм ====================
   
   // поправить все отрезки, чтобы первая координата была меньше второй   
   int itmp;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>cut[i][1]){
         itmp=cut[i][0];
         cut[i][0]=cut[i][1];
         cut[i][1]=itmp;
      }
   }
   
   // сортировка массива по первой координате
   ArraySort(cut);
   ArrayPrint(cut);
   // удалить отрезки нулевой длины и повтряющиеся отрезки
   bool ex;
   int ti=0;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]!=cut[i][1]){
         ex=false;
         for(int j=i-1;j>=0 && cut[j][0]==cut[i][0];j--){
            if(cut[j][0]==cut[i][0] && cut[j][1]==cut[i][1]){
               ex=true;
               break;
            }
         }
         if(!ex){
            cut[ti][0]=cut[i][0];
            cut[ti][1]=cut[i][1];
            ti++;
         }
      }
   }
   ArrayResize(cut,ti);
   
   // добавить каждый отрезок в массив всех вариантов
   ArrayResize(av,ArrayRange(cut,0));
   for(int i=0;i<ArrayRange(cut,0);i++){
      av[i].Init(ArrayRange(cut,0));
      av[i].AddCut1(cut,i); // в массив, идущий к концу
      av[i].AddCut2(cut,i); // в массив, идущий к началу
   }


   // а теперь самое интересное
   
   // к концу
   
   double r;
   bool n;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li1+1;j<ArrayRange(cut,0);j++){
         if(cut[j][0]>=av[i].m_cut1[av[i].len1-1][1]){
            r=MathMin(r,cut[j][0]-av[i].m_cut1[av[i].len1-1][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li1+1;j<ArrayRange(cut,0);j++){
            if(cut[j][0]-av[i].m_cut1[av[i].len1-1][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut1(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut1(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   }
   
   // к началу
   
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li2-1;j>=0;j--){
         if(cut[j][1]<=av[i].m_cut2[av[i].len2-1][0]){
            r=MathMin(r,av[i].m_cut2[av[i].len2-1][0]-cut[j][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li2-1;j>=0;j--){
            if(av[i].m_cut2[av[i].len2-1][0]-cut[j][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut2(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut2(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   } 
   
   // пометить дубли
   
   for(int i=0;i<ArraySize(av);i++){   
      av[i].isDopel=false;
      for(int j=0;j<i;j++){   
         if(av[i].Eq(av[j])){
            av[i].isDopel=true;
            break;
         }
      }
   }
   
   // соединить два массива в 1
   
   for(int i=0;i<ArraySize(av);i++){
      if(!av[i].isDopel){
         av[i].Combine();
      }
   }
   
   // вывод
   
   int h=FileOpen("Выстраивание отрезков.txt",FILE_TXT|FILE_WRITE);
   
   for(int i=0;i<ArrayRange(cut,0);i++){
      FileWrite(h,(string)cut[i][0]+"-"+(string)cut[i][1]);
   }   
   
   FileWrite(h,"");
   
   string str="";
   int vn=0;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){
      if(!av[i].isDopel){
         str="";
         for(int j=0;j<av[i].len;j++){
            str=str+(string)av[i].m_cut[j][0]+"-"+(string)av[i].m_cut[j][1]+" ";
         }
         Print("Вариант ",vn," - ",str);
         FileWrite(h,"Вариант ",vn," - ",str);
         vn++;
      }
   }
   
   FileClose(h);

}
//+------------------------------------------------------------------+

void FillArray(int & a[][2],int cutCnt){
   ArrayResize(a,cutCnt);
   for(int i=0;i<cutCnt;i++){
      a[i][0]=MathRand()%30;
      a[i][1]=a[i][0]+MathRand()%15;
   }   
}

I duplicati non sono stati setacciati dall'array, ma solo marcati. Poiché ogni variante ora memorizza i segmenti in due array, per renderlo più conveniente, essi possono essere combinati in un unico array usando il metodoCombine().

 
Dmitry Fedoseev:

Non ho setacciato i duplicati dall'array, li ho solo marcati. Poiché ora ogni variante memorizza i segmenti in due array, posso combinarli in un unico array usando il metodoCombine() per renderlo più conveniente.

Dmitry, grazie per il nuovo algoritmo!

Sì, ci sono davvero molte copie.

2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 0 - 0-1 2-5 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 1 - 0-1 2-5 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 2 - 0-1 3-6 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 3 - 0-1 3-6 7-9

Da quanto ho capito, non possono essere contati. Non ero riuscito ad aspettare la combinazione di 1000 elementi - il mio netbook ha iniziato ad esaurire la memoria :(

Ed è possibile non usare tutte le combinazioni quando si aggiunge un segmento, ma solo un certo numero di possibili nel passo corrente, diciamo le migliori 10?

 
Aleksey Vyazmikin:

Dmitry, grazie per il nuovo algoritmo!

Sì, ci sono davvero molte copie.

Da quanto ho capito, non si possono contare. Non potevo aspettare la combinazione di 1000 elementi - il mio netbook ha iniziato ad esaurire la memoria :(

È possibile non usare tutte le combinazioni quando si aggiunge un segmento, ma solo un certo numero di possibili nel passo corrente, diciamo le migliori 10?

Per sapere che sono i migliori, bisogna confrontarli con gli altri, cioè bisogna prima prenderli tutti. Un'altra cosa è ottimizzare in qualche modo l'algoritmo, ma non ho l'obiettivo di dedicare la mia vita a questo algoritmo).

Magari decidere il criterio della sufficienza e ottenere prima tutte le opzioni, partendo da un solo segmento, scelto a caso, e così via, fino a quando non appare un'opzione soddisfacente.

E la seconda opzione può essere accelerata - per scalare l'array con varianti non un elemento alla volta, ma diverse decine di elementi alla volta, e alla fine per tagliarlo.

 
Dmitry Fedoseev:

Per sapere che sono i migliori, bisogna confrontarli con gli altri, cioè bisogna prima prenderli tutti. Un'altra cosa è ottimizzare in qualche modo l'algoritmo, ma non ho l'obiettivo di dedicare la mia vita a questo algoritmo).

Sto parlando di un singolo segmento, diciamo che ha un coefficiente per valutare la sua qualità, poi dopo ogni iterazione si dirama, per esempio, solo sui primi 10 di questi coefficienti.

Dmitry Fedoseev:

Magari decidere un criterio di sufficienza e ottenere prima tutte le varianti, partendo da un solo segmento, scelto a caso e così via, fino a quando non appare una variante soddisfacente.

Purtroppo, la "sufficienza" è difficile da valutare qui - qui è necessario conoscere uno standard, poi da esso è possibile definire una tolleranza, e io non ho uno standard.

Dmitry Fedoseev:

E la seconda opzione può essere accelerata - per scalare array con opzioni non un elemento alla volta, ma diverse decine di elementi, e alla fine di esso per allineare.

Non sono sicuro di cosa intendi per parallelismo usando OpenCL?

 
Aleksey Vyazmikin:

1. Sto parlando di un singolo segmento, diciamo che ha un coefficiente per valutare la sua qualità, poi dopo ogni iterazione si dirama, per esempio, solo i primi 10 di questi coefficienti.

2. Sfortunatamente, la "sufficienza" è difficile da stimare qui - è necessario conoscere il benchmark, poi si può determinare la tolleranza da esso, e io non ho un benchmark.

3. Non sono del tutto sicuro di cosa intendi per parallelismo usando OpenCL?

1. Dove si trova questo coefficiente?

2. e il punto 1?

3. no, è più semplice. Ok, cercherò di accelerare domani.

12345678
Nuovo commento