Algoritmo para combinar faixas de um segmento - ajuda a criar - página 2

Novo comentário
  
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;
   }   
}

De alguma forma...

 
Dmitry Fedoseev:

De alguma forma...

Obrigado! Você pode ver a mão do mestre imediatamente! Amanhã estarei experimentando para ver o que vai sair.

 
Dmitry Fedoseev:

De alguma forma...

Começou a experimentar o código, criou um exemplo artificial - preenchido na matriz

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;

Entendi:

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

Ou seja, temos uma variante, mas também esperamos outra variante.

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

É possível ensinar o algoritmo para encontrá-lo também?

 
Aleksey Vyazmikin:

Começou a experimentar o código, criou um exemplo artificial - preenchido na matriz

Entendi:

Ou seja, temos uma variante, mas também esperamos outra variante.

O algoritmo pode aprender a encontrá-lo também?

E a variante "0-1 3-6 7-9" não é melhor do que a variante "0 - 0-1 2-5 7-9" - ambas são de 0 a 1 e têm 2 saltos de comprimento 1 cada.

Duas opções aparecem neste caso:

1 - fazer a mesma coisa, mas a partir do final do conjunto de saltos.

2 - olhar imediatamente não para o segmento mais próximo, mas com uma tolerância. Mas neste caso haverá ainda mais se houver muitos dados e muitas seqüências de ancoragem.

Entretanto, após a variante 1, você vai querer começar a construir cadeias a partir de todas as posições iniciais possíveis. Isto é correto, mas a quantidade de trabalho para o algoritmo aumenta consideravelmente.

Sim! É necessário iniciar a construção de variantes de cada um dos segmentos do conjunto inicial e continuar a construção até o início e o fim.

 
Dmitry Fedoseev:

E a opção "0-1 3-6 7-9" não é melhor que a opção "0 - 0-1 2-5 7-9" - ambas são de 0 a 1 e têm 2 pulos de comprimento 1 cada.

Neste caso, eles são iguais, concordo, mas são diferentes e pelos termos do problema precisaremos estimar a soma de suas pontuações, e até construirmos uma linha não saberemos a pontuação combinada de todos os segmentos.

Dmitry Fedoseev:

Entretanto, após a opção 1, haverá o desejo de começar a construir cordas a partir de todas as posições iniciais possíveis. Isto é correto, mas a quantidade de trabalho para o algoritmo aumenta consideravelmente.

Sim! É necessário iniciar a construção de variantes de cada um dos segmentos do conjunto inicial e continuar a construção até o início e o fim.

Esta também me parece ser a estratégia mais correta! No entanto, acho que pode haver variantes duplicadas.

Você pode ajudar escrevendo algum código?

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

As duplicatas não foram peneiradas da matriz, apenas marcadas. Como cada variante agora armazena os segmentos em duas matrizes, para torná-la mais conveniente, elas podem ser combinadas em uma matriz usando o métodoCombine().

 
Dmitry Fedoseev:

Como agora cada variante armazena os segmentos em duas matrizes, você pode combiná-los em uma matriz usando o métodoCombine() para torná-lo mais conveniente.

Dmitry, obrigado pelo novo algoritmo!

Sim, de fato, há muitas cópias.

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

Pelo que entendi, não podem ser contados. Eu não tinha conseguido esperar pela combinação de 1000 elementos - meu netbook começou a ficar sem memória :(

E é possível não usar todas as combinações ao adicionar um segmento, mas apenas um certo número de possíveis na etapa atual, digamos, os melhores 10?

 
Aleksey Vyazmikin:

Dmitry, obrigado pelo novo algoritmo!

Sim, de fato, há muitas cópias.

Pelo que entendi, você não pode contá-los. Eu mal podia esperar pela combinação de 1000 elementos - meu netbook começou a ficar sem memória :(

É possível não usar todas as combinações ao adicionar um segmento, mas apenas um certo número de possíveis na etapa atual, digamos, os melhores 10?

Para saber que eles são os melhores, você tem que compará-los com outros, ou seja, você tem que obtê-los todos primeiro. Outra coisa é otimizar de alguma forma o algoritmo, mas não tenho um objetivo de dedicar minha vida a este algoritmo).

Talvez decidir sobre o critério de suficiência e primeiro obter todas as opções, a partir de apenas um segmento, escolhido aleatoriamente, e assim por diante, até que uma opção satisfatória apareça.

E a segunda opção pode ser acelerada - para dimensionar a matriz com variantes não um elemento de cada vez, mas várias dezenas de elementos ao mesmo tempo, e no final para apará-la.

 
Dmitry Fedoseev:

Para saber que eles são os melhores, você tem que compará-los com outros, ou seja, você tem que obtê-los todos primeiro. Outra coisa é otimizar o algoritmo de alguma forma, mas eu não tenho o objetivo de dedicar minha vida a este algoritmo).

Estou falando de um único segmento, digamos que ele tem um coeficiente para avaliar sua qualidade, então, após cada iteração, ramificamos, por exemplo, apenas nos 10 primeiros desses coeficientes.

Dmitry Fedoseev:

Talvez decidir sobre o critério de suficiência e primeiro obter todas as variantes, a partir de apenas um segmento, escolhido aleatoriamente e assim por diante, até aparecer uma variante satisfatória.

Infelizmente, "suficiência" é difícil de estimar aqui - aqui é necessário conhecer um padrão, então a partir dele é possível definir uma tolerância, e eu não tenho um padrão.

Dmitry Fedoseev:

E a segunda opção pode ser acelerada - para escalar a matriz com opções não um elemento de cada vez, mas várias dezenas de elementos, e ao final dela para alinhar.

Não sei bem o que você quer dizer com paralelismo usando OpenCL?

 
Aleksey Vyazmikin:

1. Estou falando de um único segmento, digamos que ele tem um coeficiente para avaliar sua qualidade, então após cada iteração ramificamos, por exemplo, apenas para os 10 primeiros desses coeficientes.

2. Infelizmente, "suficiência" é difícil de estimar aqui - você precisa conhecer a referência, então você pode determinar a tolerância a partir dela, e eu não tenho uma referência.

3. não tenho bem a certeza do que você quer dizer com paralelismo usando OpenCL?

1. onde está esse coeficiente?

2. E o ponto 1?

3. não, é mais simples. Ok, vou tentar acelerar amanhã.

12345678
Novo comentário