세그먼트 범위를 결합하는 알고리즘 - 생성에 도움 - 페이지 2

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

이 같은...

 
Dmitry Fedoseev :

이 같은...

고맙습니다! 주인의 손이 바로 보입니다! 내일 해보고 뭐가 나오는지 봐야겠다.

 
Dmitry Fedoseev :

이 같은...

코드 테스트 시작, 인공 예제 생성 - 배열 채우기

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 ;

나는 얻다:

 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 

저것들. 하나의 옵션을 받았지만 다른 옵션이 예상됩니다.

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

알고리즘을 가르치고 찾을 수 있습니까?

 
Aleksey Vyazmikin :

코드 테스트 시작, 인공 예제 생성 - 배열 채우기

나는 얻다:

저것들. 하나의 옵션을 받았지만 다른 옵션이 예상됩니다.

알고리즘을 가르치고 찾을 수 있습니까?

그리고 "0-1 3-6 7-9" 옵션은 "0 - 0-1 2-5 7-9" 옵션보다 낫지 않습니다. 둘 다 0에서 1이고 길이가 1인 간격이 2개 있습니다.

이 경우 두 가지 옵션이 제공됩니다.

1 - 세그먼트 세트의 끝에서 동일하게 수행하십시오.

2 - 가장 가까운 세그먼트가 아니라 허용 오차로 즉시 찾습니다. 그러나 이 경우 데이터가 많고 결합 시퀀스가 많으면 더 많을 것입니다.

그러나 옵션 1 이후에는 가능한 모든 초기 위치에서 체인 구축을 시작하려는 욕구가 있을 것입니다. 이것은 정확하지만 알고리즘의 작업량이 크게 증가합니다.

예! 원래 세트의 각 세그먼트에서 건물 옵션을 시작하고 처음과 끝까지 건물을 계속 지어야 합니다.

 
Dmitry Fedoseev :

그리고 "0-1 3-6 7-9" 옵션은 "0 - 0-1 2-5 7-9" 옵션보다 낫지 않습니다. 둘 다 0에서 1이고 길이가 1인 간격이 2개 있습니다.

이 경우 동등하지만 동의하지만 작업 조건에 따라 지표의 합계를 사용하여 결과를 전체적으로 평가해야하며 라인을 구축 할 때까지 우리는 모든 세그먼트의 통합 평가를 알 수 없습니다.

드미트리 페도세예프 :

그러나 옵션 1 이후에는 가능한 모든 초기 위치에서 체인 구축을 시작하려는 욕구가 있을 것입니다. 이것은 정확하지만 알고리즘의 작업량이 크게 증가합니다.

예! 원래 세트의 각 세그먼트에서 건물 옵션을 시작하고 처음과 끝까지 건물을 계속 지어야 합니다.

또한 이것이 더 올바른 전략인 것 같습니다! 그러나 중복 옵션이 있을 수 있다고 생각합니다.

코드 작성에 도움이 되셨나요?

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

Dubli는 어레이에서 선별하지 않고 표시만 했습니다. 이제 각 변형에서 세그먼트가 두 개의 배열에 저장되므로 더 편리하게 만들기 위해 Combine() 메서드를 사용하여 하나의 배열로 결합할 수 있습니다.

 
Dmitry Fedoseev :

Dubli는 어레이에서 선별하지 않고 표시만 했습니다. 이제 각 옵션에서 세그먼트가 두 개의 배열에 저장되므로 더 편리하게 만들기 위해 Combine() 메서드를 사용하여 하나의 배열로 결합할 수 있습니다.

Dmitry, 새로운 알고리즘에 감사드립니다!

예, 많은 사본이 있습니다.

 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 

내가 이해하는 한, 그들은 셀 수 없습니다. 1000개 요소의 조합을 기다릴 수 없었습니다 - 넷북에서 메모리가 부족해지기 시작했습니다 :(

세그먼트를 추가할 때 모든 조합을 사용하는 것이 아니라 현재 단계에서 가능한 특정 수의 조합만 사용할 수 있습니까? 예를 들어 베스트 10이라고 합시다.

 
Aleksey Vyazmikin :

Dmitry, 새로운 알고리즘에 감사드립니다!

예, 많은 사본이 있습니다.

내가 이해하는 한, 그들은 셀 수 없습니다. 1000개 요소의 조합을 기다릴 수 없었습니다 - 넷북에서 메모리가 부족해지기 시작했습니다 :(

세그먼트를 추가할 때 모든 조합을 사용하는 것이 아니라 현재 단계에서 가능한 특정 수의 조합만 사용할 수 있습니까? 예를 들어 베스트 10이라고 합시다.

그들이 최고임을 알아 내려면 다른 사람들과 비교해야합니다. 즉, 먼저 모든 것을 얻어야합니다. 알고리즘을 어떻게든 최적화하는 것은 또 다른 문제지만 이 알고리즘에 평생을 바칠 목표는 없다)

아마도 충분성의 기준을 결정하고 만족스러운 옵션이 나타날 때까지 단 하나의 세그먼트에서 시작하여 무작위로 선택하는 등 모든 옵션을 먼저 얻을 수 있습니다.

예, 두 번째 옵션을 가속화할 수 있습니다. 한 요소가 아니라 수십 개의 요소로 한 번에 옵션으로 배열을 확장하고 끝에서 트리밍합니다.

 
Dmitry Fedoseev :

그들이 최고임을 알아 내려면 다른 사람들과 비교해야합니다. 즉, 먼저 모든 것을 얻어야합니다. 어떻게든 알고리즘을 최적화하는 것은 또 다른 문제지만 이 알고리즘에 평생을 바칠 목표는 없다)

단일 세그먼트에 대해 이야기하고 있습니다. 품질을 평가하기 위한 계수가 있다고 가정해 보겠습니다. 그런 다음 각 반복 후에 예를 들어 이 10개의 최상의 계수에 의해서만 분기합니다.

드미트리 페도세예프 :

아마도 충분성의 기준을 결정하고 만족스러운 옵션이 나타날 때까지 단 하나의 세그먼트에서 시작하여 무작위로 선택하는 등 모든 옵션을 먼저 얻을 수 있습니다.

불행히도 "충분함"을 평가하는 것은 어렵습니다. 여기에서 표준을 알아야 합니다. 그러면 표준에서 허용 오차를 결정할 수 있지만 표준이 없습니다.

드미트리 페도세예프 :

예, 두 번째 옵션을 가속화할 수 있습니다. 한 요소가 아니라 수십 개의 요소로 한 번에 옵션으로 배열을 확장하고 끝에서 트리밍합니다.

OpenCL과의 병렬화가 암시되어 있는지 잘 이해하지 못했습니다.

 
Aleksey Vyazmikin :

1. 단일 세그먼트에 대해 이야기하고 있습니다. 품질을 평가하기 위한 계수가 있다고 가정해 보겠습니다. 그런 다음 각 반복 후에 예를 들어 이 10개의 최상의 계수에 의해서만 분기합니다.

2. 불행히도 "충분함"을 평가하는 것은 어렵습니다. 여기에서 표준을 알아야 합니다. 그러면 표준에서 허용 오차를 결정할 수 있지만 표준이 없습니다.

3. OpenCL과의 병렬화가 의미하는 것인지 잘 이해가 되지 않았습니다.

1. 이 계수는 어디에 있습니까?

2. 항목 1은 어떻습니까?

3. 아니요, 모든 것이 더 간단합니다. 알겠습니다. 내일은 속도를 내도록 하겠습니다.