Segment aralıklarını birleştirmek için algoritma - oluşturmaya yardımcı olun - sayfa 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 ;
   }   
}

Bunun gibi bir şey...

 
Dmitry Fedoseev :

Bunun gibi bir şey...

Teşekkür ederim! Ustanın eli hemen görünür! Yarın deneyeceğim bakalım ne çıkacak.

 
Dmitry Fedoseev :

Bunun gibi bir şey...

Kodu test etmeye başladı, yapay bir örnek oluşturdu - diziyi doldurdu

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 ;

Alırım:

 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 

Onlar. bir seçenek aldı, ancak başka bir seçenek bekleniyor

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

Bir algoritma öğretilebilir ve bulunabilir mi?

 
Aleksey Vyazmikin :

Kodu test etmeye başladı, yapay bir örnek yarattı - diziyi doldurdu

Alırım:

Onlar. bir seçenek aldı, ancak başka bir seçenek bekleniyor

Bir algoritma öğretilebilir ve bulunabilir mi?

Ve "0-1 3-6 7-9" seçeneği, "0 - 0-1 2-5 7-9" seçeneğinden daha iyi değildir - hem 0'dan 1'e hem de her biri 1 uzunluğunda 2 boşluk vardır.

Bu durumda iki seçenek sunulur:

1 - aynısını yapın, ancak segment kümesinin sonundan.

2 - hemen en yakın segmenti değil, toleransla arayın. Ancak bu durumda, çok fazla veri ve çok sayıda birleştirme dizisi varsa, o zaman daha da fazlası olacaktır.

Bununla birlikte, 1. seçenekten sonra, olası tüm başlangıç konumlarından zincir oluşturmaya başlama arzusu olacaktır. Bu doğrudur, ancak algoritmanın çalışma miktarı önemli ölçüde artar.

Evet! Orijinal setin her bir bölümünden inşa seçeneklerine başlamak ve baştan sona inşa etmeye devam etmek gerekir.

 
Dmitry Fedoseev :

Ve "0-1 3-6 7-9" seçeneği, "0 - 0-1 2-5 7-9" seçeneğinden daha iyi değildir - hem 0'dan 1'e hem de her biri 1 uzunluğunda 2 boşluk vardır.

Bu durumda eşdeğerler, katılıyorum, ancak farklılar ve görevin koşullarına göre, göstergelerinin toplamını kullanarak sonucu toplamda değerlendirmek gerekecek ve biz bir çizgi oluşturana kadar, biz tüm segmentlerin birleşik değerlendirmesini bilemez.

Dmitry Fedoseev :

Bununla birlikte, 1. seçenekten sonra, olası tüm başlangıç konumlarından zincir oluşturmaya başlama arzusu olacaktır. Bu doğrudur, ancak algoritmanın çalışma miktarı önemli ölçüde artar.

Evet! Orijinal setin her bir bölümünden inşa seçeneklerine başlamak ve baştan sona inşa etmeye devam etmek gerekir.

Ayrıca bana öyle geliyor ki bu daha doğru bir strateji! Ancak, yinelenen seçenekler olabileceğini düşünüyorum.

Kod yazma konusunda yardım?

 
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 diziden elenmedi, sadece iz bıraktı. Artık her varyantta segmentler iki dizide saklandığından, daha kullanışlı hale getirmek için Combine () yöntemi kullanılarak tek bir dizide birleştirilebilirler.

 
Dmitry Fedoseev :

Dubli diziden elenmedi, sadece iz bıraktı. Artık her varyantta segmentler iki dizide saklandığından, daha kullanışlı hale getirmek için Combine () yöntemi kullanılarak tek bir dizide birleştirilebilirler.

Dmitry, yeni algoritma için teşekkürler!

evet çok kopya var

 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 

Anladığım kadarıyla bunlar sayılmaz. 1000 öğenin birleşimini bekleyemedim - netbook'ta bellek tükenmeye başladı :(

Bir segment eklerken tüm kombinasyonları değil, mevcut adımda yalnızca belirli sayıda olası kombinasyonu, diyelim ki en iyi 10'u kullanmak mümkün müdür?

 
Aleksey Vyazmikin :

Dmitry, yeni algoritma için teşekkürler!

evet çok kopya var

Anladığım kadarıyla bunlar sayılmaz. 1000 öğenin birleşimini bekleyemedim - netbook'ta bellek tükenmeye başladı :(

Bir segment eklerken tüm kombinasyonları değil, mevcut adımda yalnızca belirli sayıda olası kombinasyonu, diyelim ki en iyi 10'u kullanmak mümkün müdür?

En iyi olduklarını öğrenmek için başkalarıyla karşılaştırılmaları gerekir, yani önce her şeyi almanız gerekir. Algoritmayı bir şekilde optimize etmek başka bir konu ama hayatımı bu algoritmaya adamak gibi bir amacım yok)

Belki yeterlilik kriterine karar verin ve önce rastgele seçilen tek bir segmentten başlayarak tüm seçenekleri alın ve tatmin edici bir seçenek görünene kadar devam edin.

Evet ve ikinci seçenek hızlandırılabilir - diziyi seçeneklerle bir öğeyle değil, aynı anda birkaç düzine öğeyle ölçeklendirin ve sonunda kırpın.

 
Dmitry Fedoseev :

En iyi olduklarını öğrenmek için başkalarıyla karşılaştırılmaları gerekir, yani önce her şeyi almanız gerekir. Algoritmayı bir şekilde optimize etmek başka bir konu ama hayatımı bu algoritmaya adamak gibi bir amacım yok)

Tek bir segmentten bahsediyorum, diyelim ki kalitesini değerlendirmek için bir katsayısı var, sonra her yinelemeden sonra, örneğin sadece bu 10 en iyi katsayı ile dallanıyoruz.

Dmitry Fedoseev :

Belki yeterlilik kriterine karar verin ve önce rastgele seçilen tek bir segmentten başlayarak tüm seçenekleri alın ve tatmin edici bir seçenek görünene kadar devam edin.

Ne yazık ki, “yeterliliği” değerlendirmek zor - burada standardı bilmeniz gerekiyor, ondan sonra toleransı belirleyebilirsiniz, ancak benim bir standardım yok.

Dmitry Fedoseev :

Evet ve ikinci seçenek hızlandırılabilir - diziyi seçeneklerle bir öğeyle değil, aynı anda birkaç düzine öğeyle ölçeklendirin ve sonunda kırpın.

Tam olarak anlamadım, OpenCL ile paralelleştirme kastediliyor mu?

 
Aleksey Vyazmikin :

1. Tek bir segmentten bahsediyorum, diyelim ki kalitesini değerlendirmek için bir katsayısı var, sonra her yinelemeden sonra örneğin sadece bu 10 en iyi katsayı ile dallanıyoruz.

2. Ne yazık ki, “yeterliliği” değerlendirmek zordur - burada standardı bilmeniz gerekir, ondan sonra toleransı belirleyebilirsiniz, ancak benim bir standardım yok.

3. Tam olarak anlamadım, OpenCL ile paralelleştirme kastediliyor mu?

1. Bu katsayı nerede?

2. Peki ya 1. nokta?

3. Hayır, her şey daha basit. Tamam, yarın hızlandırmaya çalışacağım.