Приступил к опробованию кода, создал искусственный пример - заполнил массив
Получаю:
Т.е. получили один вариант, но ожидается ещё и вариант
Можно ли алгоритм научить и его находить?
А вариант "0-1 3-6 7-9" не лучше варианта "0 - 0-1 2-5 7-9" - оба от 0 до 1 и имеют по 2 пропуска длиной 1.
Два варианта представляется в данном случае:
1 - сделать все тоже самое, но с конца набора отрезков.
2 - сразу искать не самый ближайший отрезок, а с допуском. Но в это случае, если данных много и много стыкующихся последовательностей, то будет еще больше.
Однако после варианта 1 возникнет желание начинать построение цепочек из всех возможных начальных положений. Это правильно, но объем работы алгоритма значительно увеличивается.
Да! Надо начинать построение вариантов от каждого из отрезков исходного набора и продолжать построение в начало и конец.
А вариант "0-1 3-6 7-9" не лучше варианта "0 - 0-1 2-5 7-9" - оба от 0 до 1 и имеют по 2 пропуска длиной 1.
В данном случае они равнозначны, согласен, но они разные и по условиям задачи необходимо будет оценить суммарно результат с помощью суммы их показателей, а пока не построим строку мы не узнаем объединённую оценку всех отрезков.
Dmitry Fedoseev:
Однако после варианта 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];
voidOnStart(){
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;
}
}
}
// соединить два массива в 1for(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;
}
}
Дубли не отсеивал из массива, только пометку сделал. Поскольку теперь в каждом варианте отрезки хранятся в двух массивах, чтобы было удобней, их можно объединить в один массив методом Combine().
Дубли не отсеивал из массива, только пометку сделал. Поскольку теперь в каждом варианте отрезки хранятся в двух массивах, чтобы было удобней, их можно объединить в один массив методом Combine().
Дмитрий, спасибо за новый алгоритм!
Да, копий действительно много
2021.04.2216:55:43.829 Q_Podbor_02 (Si-6.21,M1) Вариант 0 - 0-12-57-92021.04.2216:55:43.829 Q_Podbor_02 (Si-6.21,M1) Вариант 1 - 0-12-57-92021.04.2216:55:43.829 Q_Podbor_02 (Si-6.21,M1) Вариант 2 - 0-13-67-92021.04.2216:55:43.829 Q_Podbor_02 (Si-6.21,M1) Вариант 3 - 0-13-67-9
Как я понимаю, их не считать не получится. Комбинацию из 1000 элементов дождаться не смог - память начала кончаться на нетбуке :(
А есть ли возможность использовать не все комбинации при добавления отрезка, а только определенное количество из возможных на текущем шаге, допустим лучшие 10?
Как я понимаю, их не считать не получится. Комбинацию из 1000 элементов дождаться не смог - память начала кончаться на нетбуке :(
А есть ли возможность использовать не все комбинации при добавления отрезка, а только определенное количество из возможных на текущем шаге, допустим лучшие 10?
Чтобы узнать, что они лучшие, их надо сравнить с другими, то есть сначала надо получить все. Другое дело - как-то оптимизировать алгоритм, но у меня нет цели посвятить этому алгоритму свою жизнь)
Может быть, определиться с критерием достаточности и сначала получить все варианты, начиная только с одного отрезка, случайно выбранного и так далее, пока не появится удовлетворительный вариант.
Да и второй вариант можно ускорить - масштабировать массив с вариантами не по одному элементу, а сразу на несколько десятков элементов, а в конце подровнять его.
Чтобы узнать, что они лучшие, их надо сравнить с другими, то есть сначала надо получить все. Другое дело - как-то оптимизировать алгоритм, но у меня нет цели посвятить этому алгоритму свою жизнь)
Я говорю об отдельно взятом отрезке, допустим у него есть коэффициент для оценки его качества, тогда после каждой итерации мы ветвимся, к примеру, только по 10 лучшим этим коэффициентам.
Dmitry Fedoseev:
Может быть, определиться с критерием достаточности и сначала получить все варианты, начиная только с одного отрезка, случайно выбранного и так далее, пока не появится удовлетворительный вариант.
К сожалению, "достаточность" оценить вот сложно - тут надо знать эталон, тогда от него можно определить допуск, а эталона у меня нет.
Dmitry Fedoseev:
Да и второй вариант можно ускорить - масштабировать массив с вариантами не по одному элементу, а сразу на несколько десятков элементов, а в конце подровнять его.
Не совсем понял, подразумевается распараллеливание с помощью OpenCL?
1. Я говорю об отдельно взятом отрезке, допустим у него есть коэффициент для оценки его качества, тогда после каждой итерации мы ветвимся, к примеру, только по 10 лучшим этим коэффициентам.
2. К сожалению, "достаточность" оценить вот сложно - тут надо знать эталон, тогда от него можно определить допуск, а эталона у меня нет.
3. Не совсем понял, подразумевается распараллеливание с помощью OpenCL?
1. А где этот коэффициент?
2. А п.1?
3. Нет, все проще. Ладно, завтра постараюсь ускорить.
Для авторизации и пользования сайтом MQL5.com необходимо разрешить использование файлов Сookie.
Пожалуйста, включите в вашем браузере данную настройку, иначе вы не сможете авторизоваться.
Вы вошли в аккаунт. Двухфакторная аутентификация отключена. Настройте её заново и отсканируйте новый QR-код или продолжите с отключённой двухфакторной аутентификацией.
Как-то так...
Как-то так...
Спасибо! Сразу видна рука мастера! Завтра буду пробовать, смотреть, что выходит.
Как-то так...
Приступил к опробованию кода, создал искусственный пример - заполнил массив
Получаю:
Т.е. получили один вариант, но ожидается ещё и вариант
Можно ли алгоритм научить и его находить?
Приступил к опробованию кода, создал искусственный пример - заполнил массив
Получаю:
Т.е. получили один вариант, но ожидается ещё и вариант
Можно ли алгоритм научить и его находить?
А вариант "0-1 3-6 7-9" не лучше варианта "0 - 0-1 2-5 7-9" - оба от 0 до 1 и имеют по 2 пропуска длиной 1.
Два варианта представляется в данном случае:
1 - сделать все тоже самое, но с конца набора отрезков.
2 - сразу искать не самый ближайший отрезок, а с допуском. Но в это случае, если данных много и много стыкующихся последовательностей, то будет еще больше.
Однако после варианта 1 возникнет желание начинать построение цепочек из всех возможных начальных положений. Это правильно, но объем работы алгоритма значительно увеличивается.
Да! Надо начинать построение вариантов от каждого из отрезков исходного набора и продолжать построение в начало и конец.
А вариант "0-1 3-6 7-9" не лучше варианта "0 - 0-1 2-5 7-9" - оба от 0 до 1 и имеют по 2 пропуска длиной 1.
В данном случае они равнозначны, согласен, но они разные и по условиям задачи необходимо будет оценить суммарно результат с помощью суммы их показателей, а пока не построим строку мы не узнаем объединённую оценку всех отрезков.
Однако после варианта 1 возникнет желание начинать построение цепочек из всех возможных начальных положений. Это правильно, но объем работы алгоритма значительно увеличивается.
Да! Надо начинать построение вариантов от каждого из отрезков исходного набора и продолжать построение в начало и конец.
Мне так же кажется, что это более правильная стратегия! Однако, думаю, что могут возникнуть дублирующиеся варианты.
Поможете написанием кода?
Дубли не отсеивал из массива, только пометку сделал. Поскольку теперь в каждом варианте отрезки хранятся в двух массивах, чтобы было удобней, их можно объединить в один массив методом Combine().
Дубли не отсеивал из массива, только пометку сделал. Поскольку теперь в каждом варианте отрезки хранятся в двух массивах, чтобы было удобней, их можно объединить в один массив методом Combine().
Дмитрий, спасибо за новый алгоритм!
Да, копий действительно много
Как я понимаю, их не считать не получится. Комбинацию из 1000 элементов дождаться не смог - память начала кончаться на нетбуке :(
А есть ли возможность использовать не все комбинации при добавления отрезка, а только определенное количество из возможных на текущем шаге, допустим лучшие 10?
Дмитрий, спасибо за новый алгоритм!
Да, копий действительно много
Как я понимаю, их не считать не получится. Комбинацию из 1000 элементов дождаться не смог - память начала кончаться на нетбуке :(
А есть ли возможность использовать не все комбинации при добавления отрезка, а только определенное количество из возможных на текущем шаге, допустим лучшие 10?
Чтобы узнать, что они лучшие, их надо сравнить с другими, то есть сначала надо получить все. Другое дело - как-то оптимизировать алгоритм, но у меня нет цели посвятить этому алгоритму свою жизнь)
Может быть, определиться с критерием достаточности и сначала получить все варианты, начиная только с одного отрезка, случайно выбранного и так далее, пока не появится удовлетворительный вариант.
Да и второй вариант можно ускорить - масштабировать массив с вариантами не по одному элементу, а сразу на несколько десятков элементов, а в конце подровнять его.
Чтобы узнать, что они лучшие, их надо сравнить с другими, то есть сначала надо получить все. Другое дело - как-то оптимизировать алгоритм, но у меня нет цели посвятить этому алгоритму свою жизнь)
Я говорю об отдельно взятом отрезке, допустим у него есть коэффициент для оценки его качества, тогда после каждой итерации мы ветвимся, к примеру, только по 10 лучшим этим коэффициентам.
Может быть, определиться с критерием достаточности и сначала получить все варианты, начиная только с одного отрезка, случайно выбранного и так далее, пока не появится удовлетворительный вариант.
К сожалению, "достаточность" оценить вот сложно - тут надо знать эталон, тогда от него можно определить допуск, а эталона у меня нет.
Да и второй вариант можно ускорить - масштабировать массив с вариантами не по одному элементу, а сразу на несколько десятков элементов, а в конце подровнять его.
Не совсем понял, подразумевается распараллеливание с помощью OpenCL?
1. Я говорю об отдельно взятом отрезке, допустим у него есть коэффициент для оценки его качества, тогда после каждой итерации мы ветвимся, к примеру, только по 10 лучшим этим коэффициентам.
2. К сожалению, "достаточность" оценить вот сложно - тут надо знать эталон, тогда от него можно определить допуск, а эталона у меня нет.
3. Не совсем понял, подразумевается распараллеливание с помощью OpenCL?
1. А где этот коэффициент?
2. А п.1?
3. Нет, все проще. Ладно, завтра постараюсь ускорить.