Алгоритм объединения диапазонов отрезка - помогите создать

 

Прошу помощи в создании алгоритма, объединяющего куски (диапазоны) отрезка в один отрезок без пересечений отрезков, с возможным пропуском, который будет потом заполнен.

Изначально у нас есть массив чисел в определенном диапазоне, числа могут повторятся, этот массив делится границами на отрезки. Границы генерируются разными алгоритмами, как правило границы неравномерные, таким образом получается, что массив чисел нарезан разными методами и каждый диапазон имеет разный размер. Дальше проведена оценка каждого такого отрезка тремя критериями, у каждого критерия есть своя граница, при несоблюдении которой происходит исключение куска диапазона. В итоге получаем таблицу такого содержания.

i - порядковый номер диапазона;

S - граница начала диапазона;

F - граница окончания диапазона;

%R - критерий №1;

%dP - критерий №2;

%K_SCO - критерий №3;

K_Svod - сводная оценка всех критериев.

Ниже показан рисунок, как могут размещаться куски (отрезки) на плоскости:

3 цвета галочек возле отрезков - потенциальное решение задачи.

Алгоритм должен предоставить разные комбинации решения задачи таким образом, что бы выполнялось условие:

1. Отрезки подобраны без пересечений диапазонов (S>=A && F<B);

2. Добавить ещё один отрезок из имеющихся нельзя - т.е. некая завершенность и максимальная плотность исходя из отобранных и имеющихся вариантов;

3. Последовательность отрезков упорядочена - для исключения одинаковых комбинаций;

4. Используется хотя бы один из лучших отрезков, от 30% лучших согласно K_Svod,  - для снижения комбинаций и сохранения приоритета лучших показателей.

В идеале оценкой качества должна быть максимизация суммы всех отрезков по показателю  K_Svod, но возможно его надо будет чуть поправить с целью оценки заполняемости пространства/пропусков.

Возможно, что я не верную использовал терминологию и моей задаче есть уже давно готовое решение - не осуждайте - просветите.

 
Aleksey Vyazmikin:


1)  K_Svod - сводная оценка всех критериев.

2) Ниже показан рисунок, как могут размещаться куски (отрезки) на плоскости:

3)  Отрезки подобраны без пересечений диапазонов (S>=A && F<B);

1) что это? почему иксы?

2) покажи лучше рисунком что есть правильное решение , а что есть неправильное

3) что есть "А" и что есть "В" ?

4) также сделай "макет" таблицы с данными и покажи что ты хочешь видеть в качестве удовлетворяющего решения  
 
Возможно, решается в терминах теории графов. Вершины графа - отрезки, стрелки графа - соединяют каждую вершину со всеми возможными последующими (ближайшими допустимыми отрезками). Каждая вершина и стрелка помечаются весами и определяется правило, по которому считается вес каждого пути. Применяется какой-нибудь алгоритм поиска оптимального пути в графе. Более подробно исследовать вопрос не готов)
 
mytarmailS:

1) что это? почему иксы?

2) покажи лучше рисунком что есть правильное решение , а что есть неправильное

3) что есть "А" и что есть "В" ?

4) также сделай "макет" таблицы с данными и покажи что ты хочешь видеть в качестве удовлетворяющего решения  

1. Это производная от всех 3х оценок, иксы от того, что я пока не определился с весами - это не существенно.

2. Правильным решением является заполнение пространства отрезками (линия с вероятным незаполненным пространством между отрезками)- на рисунке выше поставил галочки по цветам для каждого из возможных 3х решений. Можно подумать о дополнительной эвристике, допустим что б сумма выделяемого диапазона всех отрезков была как можно больше, но по мимо суммы важен и показатель  K_Svod.

3. Это значение чисел внутри отрезка, правильней было бы написать A1>=S1 && A1<F1 && F1<S2.

4. Решением будет массив с индексами. Или я не понял вопрос. Алгоритм, как это сделать лучше, я не знаю.

 
Aleksey Nikolayev:
Возможно, решается в терминах теории графов. Вершины графа - отрезки, стрелки графа - соединяют каждую вершину со всеми возможными последующими (ближайшими допустимыми отрезками). Каждая вершина и стрелка помечаются весами и определяется правило, по которому считается вес каждого пути. Применяется какой-нибудь алгоритм поиска оптимального пути в графе. Более подробно исследовать вопрос не готов)

Спасибо за идею, думаю, что как вариант можно начать строить последовательность с вершины каждого индекса i, а потом уже оценить получившиеся комбинации. Нужен только критерий отбора отрезка или несколько критериев, что бы получились разные комбинации. Или рандомить критерии.... пока не ясно.

 
Aleksey Vyazmikin:

1. Это производная от всех 3х оценок, иксы от того, что я пока не определился с весами - это не существенно.

2. Правильным решением является заполнение пространства отрезками (линия с вероятным незаполненным пространством между отрезками)- на рисунке выше поставил галочки по цветам для каждого из возможных 3х решений. Можно подумать о дополнительной эвристике, допустим что б сумма выделяемого диапазона всех отрезков была как можно больше, но по мимо суммы важен и показатель  K_Svod.

3. Это значение чисел внутри отрезка, правильней было бы написать A1>=S1 && A1<F1 && F1<S2.

4. Решением будет массив с индексами. Или я не понял вопрос. Алгоритм, как это сделать лучше, я не знаю.

Я все равно не понял

 
Aleksey Vyazmikin:

Спасибо за идею, думаю, что как вариант можно начать строить последовательность с вершины каждого индекса i, а потом уже оценить получившиеся комбинации. Нужен только критерий отбора отрезка или несколько критериев, что бы получились разные комбинации. Или рандомить критерии.... пока не ясно.

А вот где галочки, у них есть какой то критерий, что отрезок принадлежит этой галочке?
По сути, у вас получилось три галочки. Синий, красный. зелёный.
То есть в данном примере, три идентификатора.
Если как то назначить эти идентификаторы, то по ним можно конкатенировать в три основных массива.
По идентификатору получаем размер получившегося отрезка,
по идентификатору определяем основной приемный массив и увеличиваем его капасити на этот размер,
по идентификатору  вставляем отрезок в конец массива. 
То есть нужно определить как то критерий, что отрезок принадлежит этой галочке (идентификатору).

 
mytarmailS:

Я все равно не понял

Уточните, пожалуйста, что не поняли - попробую объяснить иными словами.

 
Roman:

А вот где галочки, у них есть какой то критерий, что отрезок принадлежит этой галочке?
По сути, у вас получилось три галочки. Синий, красный. зелёный.
То есть в данном примере, три идентификатора.
Если как то назначить эти идентификаторы, то по ним можно конкатенировать в три основных массива.
По идентификатору получаем размер получившегося отрезка,
по идентификатору определяем основной приемный массив и увеличиваем его капасити на этот размер,
по идентификатору  вставляем отрезок в конец массива. 
То есть нужно определить как то критерий, что отрезок принадлежит этой галочке (идентификатору).

Я нарисовал отрезки, потом подумал, что надо будет показать вариант их объединения - посмотрел на комбинации, которые не пересекаются и в сумме занимают большую площадь. Обратите внимание, что у некоторых отрезков две галочки, что означает возможность наличия отрезка в более чем одной комбинации.

Т.е. идентификатора нет до начала обработки данных.
 
Aleksey Vyazmikin:

Я нарисовал отрезки, потом подумал, что надо будет показать вариант их объединения - посмотрел на комбинации, которые не пересекаются и в сумме занимают большую площадь. Обратите внимание, что у некоторых отрезков две галочки, что означает возможность наличия отрезка в более чем одной комбинации.

Т.е. идентификатора нет до начала обработки данных.

Возможно исходя из вашего алгоритма, по какому то критерию можно идентифицировать каждый отрезок и присвоить идентификатор.
А то, что отрезок может быть в более чем одной комбинации, тут зависит от того, надо его повторно добавлять в основной массив или нет.
Тернарными или условными операторами как то обыгрывать логику.  

 
Roman:

Возможно исходя из вашего алгоритма, по какому то критерию можно идентифицировать каждый отрезок и присвоить идентификатор.
А то, что отрезок может быть в более чем одной комбинации, тут зависит от того, надо его повторно добавлять в основной массив или нет.
Тернарными или условными операторами как то обыгрывать логику.  

Так алгоритма нет, что б из него исходить :) Каждый отрезок идентифицирован порядковым номером и имеет информацию о координатах (по оси X) и некую оценку полезности на этих координатах.

Пока приходит только одна идея - выбирать наиболее близкий отрезок от начального. Возможно так можно выбрать первые 3 наиболее близких, в зависимости от числа отрезков будет расти и число комбинаций.