Algorithme pour combiner les plages d'un segment - aide à la création - page 2

Nouveau commentaire
  
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;
   }   
}

D'une certaine façon...

 
Dmitry Fedoseev:

D'une certaine façon...

Merci ! On voit tout de suite la main du maître ! Je vais l'essayer demain pour voir ce qui en ressort.

 
Dmitry Fedoseev:

D'une certaine façon...

J'ai commencé à essayer le code, j'ai créé un exemple artificiel - j'ai rempli le tableau.

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;

Je l'ai :

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

C'est-à-dire que nous avons reçu une variante, mais nous en attendons une autre.

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

Est-il possible d'apprendre à l'algorithme à le trouver aussi ?

 
Aleksey Vyazmikin:

J'ai commencé à essayer le code, j'ai créé un exemple artificiel - j'ai rempli le tableau.

Je l'ai :

En d'autres termes, nous avons obtenu une variante, mais nous en attendons une autre.

L'algorithme peut-il apprendre à le trouver aussi ?

Et la variante "0-1 3-6 7-9" n'est pas meilleure que la variante "0 - 0-1 2-5 7-9" - les deux vont de 0 à 1 et ont 2 sauts de longueur 1 chacun.

Deux options apparaissent dans ce cas :

1 - faire la même chose, mais à partir de la fin de la série de sauts.

2 - cherchez tout de suite non pas le segment le plus proche, mais avec une tolérance. Mais dans ce cas, il y en aura encore plus s'il y a beaucoup de données et beaucoup de séquences d'amarrage.

Cependant, après la variante 1, vous voudrez commencer à construire des chaînes à partir de toutes les positions de départ possibles. C'est correct, mais la quantité de travail pour l'algorithme augmente considérablement.

Oui ! Il est nécessaire de commencer la construction des variantes à partir de chacun des segments de l'ensemble initial et de poursuivre la construction jusqu'au début et à la fin.

 
Dmitry Fedoseev:

Et l'option "0-1 3-6 7-9" n'est pas meilleure que l'option "0 - 0-1 2-5 7-9" - les deux vont de 0 à 1 et ont 2 sauts de longueur 1 chacun.

Dans ce cas, ils sont égaux, je suis d'accord, mais ils sont différents et selon les termes du problème, nous devrons estimer la somme de leurs scores, et jusqu'à ce que nous construisions une ligne, nous ne connaîtrons pas le score combiné de tous les segments.

Dmitry Fedoseev:

Cependant, après l'option 1, il y aura un désir de commencer à construire des chaînes de caractères à partir de toutes les positions de départ possibles. C'est correct, mais la quantité de travail pour l'algorithme augmente considérablement.

Oui ! Il est nécessaire de commencer la construction des variantes à partir de chacun des segments de l'ensemble initial et de poursuivre la construction jusqu'au début et à la fin.

Cela me semble également être la stratégie la plus correcte ! Cependant, je pense qu'il peut y avoir des variantes en double.

Pouvez-vous nous aider en écrivant du code ?

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

Puisque chaque variante stocke maintenant les segments dans deux tableaux, pour plus de commodité, ils peuvent être combinés en un seul tableau en utilisant la méthodeCombine().

 
Dmitry Fedoseev:

Je n'ai pas trié les doublons du tableau, je les ai seulement marqués. Puisque maintenant chaque variante stocke les segments dans deux tableaux, je peux les combiner en un seul tableau en utilisant la méthodeCombine() pour que ce soit plus pratique.

Dmitry, merci pour le nouvel algorithme !

Oui, il y a effectivement beaucoup de copies.

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

Si je comprends bien, ils ne peuvent pas être comptés. Je n'ai pas réussi à attendre la combinaison de 1000 éléments - mon netbook a commencé à manquer de mémoire :(

Et est-il possible de ne pas utiliser toutes les combinaisons lors de l'ajout d'un segment, mais seulement un certain nombre de possibles dans l'étape actuelle, disons les 10 meilleures ?

 
Aleksey Vyazmikin:

Dmitry, merci pour le nouvel algorithme !

Oui, il y a effectivement beaucoup de copies.

Si je comprends bien, vous ne pouvez pas les compter. Je n'ai pas pu attendre la combinaison de 1000 éléments - mon netbook a commencé à manquer de mémoire :(

Est-il possible de ne pas utiliser toutes les combinaisons lors de l'ajout d'un segment, mais seulement un certain nombre de combinaisons possibles dans l'étape actuelle, disons les 10 meilleures ?

Pour savoir qu'ils sont les meilleurs, vous devez les comparer aux autres, c'est-à-dire que vous devez d'abord les obtenir tous. Une autre chose est d'optimiser d'une manière ou d'une autre l'algorithme, mais je n'ai pas pour objectif de consacrer ma vie à cet algorithme).

On peut décider du critère de suffisance et obtenir d'abord toutes les options, en partant d'un seul segment, choisi au hasard, et ainsi de suite, jusqu'à ce qu'une option satisfaisante apparaisse.

Et la deuxième option peut être accélérée - pour mettre à l'échelle le tableau avec des variantes, non pas un élément à la fois, mais plusieurs dizaines d'éléments à la fois, et à la fin pour le découper.

 
Dmitry Fedoseev:

Pour savoir qu'ils sont les meilleurs, vous devez les comparer aux autres, c'est-à-dire que vous devez d'abord les obtenir tous. Une autre chose est d'optimiser l'algorithme d'une manière ou d'une autre, mais je n'ai pas l'objectif de consacrer ma vie à cet algorithme).

Je parle d'un seul segment, disons qu'il a un coefficient pour évaluer sa qualité, puis après chaque itération nous nous ramifions, par exemple, seulement sur les 10 premiers de ces coefficients.

Dmitry Fedoseev:

Peut-être décider du critère de suffisance et obtenir d'abord toutes les variantes, en partant d'un seul segment, choisi au hasard et ainsi de suite, jusqu'à ce qu'une variante satisfaisante apparaisse.

Malheureusement, la "suffisance" est difficile à estimer ici - il est nécessaire de connaître une norme, puis à partir de celle-ci il est possible de définir une tolérance, et je n'ai pas de norme.

Dmitry Fedoseev:

Et la deuxième option peut être accélérée - pour mettre à l'échelle le tableau avec des options non pas un élément à la fois, mais plusieurs dizaines d'éléments, et à la fin de celui-ci pour l'aligner.

Je ne suis pas tout à fait sûr de ce que vous voulez dire par parallélisme en utilisant OpenCL ?

 
Aleksey Vyazmikin:

1. Je parle d'un seul segment, disons qu'il a un coefficient pour évaluer sa qualité, puis après chaque itération nous passons, par exemple, uniquement aux 10 premiers de ces coefficients.

2. Malheureusement, la "suffisance" est difficile à estimer ici - il faut connaître le point de référence, puis déterminer la tolérance à partir de celui-ci, et je n'ai pas de point de référence.

3. je ne suis pas tout à fait sûr de ce que vous voulez dire par parallélisme en utilisant OpenCL ?

1. où se trouve ce coefficient ?

2. qu'en est-il du point 1 ?

3. Non, c'est plus simple. Ok, je vais essayer de l'accélérer demain.

12345678
Nouveau commentaire