Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины / 17 сообщений из 17, страница 1 из 1
14.08.2021, 13:22
    #40090723
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Всем привет.

Допустим, есть набор точек (заданы координатами):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
x        y
===========
327.31 	 6
327.32 	 2
327.33	 4
...
330.26	 5
330.27	10
(всего около 300)

И по ним построена диаграмма (см в аттаче).
Требуется найти такое подмножество смежных отрезков, для которого верны следующие утверждения:
1) сумма длин его отрезков не меньше N% от общей суммы длин всех отрезков;
2) число отрезков в этом множестве - минимальное (т.е. нет аналогичных других подмножеств, в которых число отрезков строго меньше, чем в найденном)

Что-то не могу понять: что гуглить ? название алгоритма хотя бы или направление в математике для этого...
...
Рейтинг: 0 / 0
14.08.2021, 13:43
    #40090729
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Голос из погреба,

быстрее будет написать несколько циклов и найти минимум
...
Рейтинг: 0 / 0
14.08.2021, 13:56
    #40090735
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Один цикл чтобы посчитать общую сумму.
Второй цикл чтобы найти все возможные группы отрезков.
Третий цикл, вложенный во второй, чтобы посчитать количество отрезков в каждой группе.
Вот и весь алгоритм. Лабораторная работа первокурсника.
...
Рейтинг: 0 / 0
16.08.2021, 13:49
    #40091012
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Я тоже из погреба. Нужен наиболее узкий и непрерывный кусок спектра распределения? с интегралом больше заданного. Или непрерырвность не требуется?

И кстати, мне кажется, что достаточно проскользить по накопительной кривой заданным окном (N% в высоту). Проскользить слева направо и выбрать эти наиболее узкие интервалы. Тогда вобще один цикл. На глаз вижу 2х претендентов.
...
Рейтинг: 0 / 0
16.08.2021, 15:45
    #40091044
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
exp98
Я тоже из погреба. Нужен наиболее узкий и непрерывный кусок спектра распределения? с интегралом больше заданного. Или непрерырвность не требуется?

И кстати, мне кажется, что достаточно проскользить по накопительной кривой заданным окном (N% в высоту). Проскользить слева направо и выбрать эти наиболее узкие интервалы. Тогда вобще один цикл. На глаз вижу 2х претендентов.


Постановка не особо сложная. Но слова могут быть слишком по разному интерпретированы.
Я-бы предложил автору взять на бумажке вручную посчитать хотя-бы 1 вариант решения
где в исходных данных будет всего 5-10 отрезков.

И потом по этим данным сформировать следующее утверждение в таком формате.

Input:

Код: sql
1.
2.
3.
4.
5.
N=50%
x       y
327.31 	 6
327.32 	 2
327.33	 4



Output:
Код: sql
1.
2.
Set1 : [ {x=327.31, y=6},  {x=327.32, y=2} ]
Set2 : ..... e.t.c.



Далее - по этому утверждению мы сможем написать модульный тест и код к нему.

Если этого не сделать - то задача будет "заболтана". В топик зайдут эксперты которые
будут задавать бесконечное число уточнений и мыслей и тема задачи будет просто похоронена под
потоком деталей.

Гуглить задачу - скорее всего бесполезно.
...
Рейтинг: 0 / 0
16.08.2021, 16:05
    #40091046
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Ну мимо одного цикла, в самом начале, считающего общую сумму, никуда, надо же знать, сколько это - N%.
А дальше второй цикл.
Держим два указателя, на начало и конец окна, и текущую сумму значений между ними.
Если текущая сумма больше - сравниваем вариант с уже имеющимся. Если он лучше (или если имеющегося - ещё нет), запоминаем. Иначе - сдвигаем первый указатель и повторяем. Если сдвигать некуда - завершаем.
Если проверяли, надо ли запоминать, проверяем, можно ли сдвинуть второй (останется ли сумма больше). Если можно - сдвигаем и повторяем.

Оптимальный порядок действий (для уменьшения количества проверок и веток) искать лениво. Самостоятельно разберётесь.
...
Рейтинг: 0 / 0
16.08.2021, 20:02
    #40091100
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
накидал VBA-код в Excel:

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
Option Explicit

'описатель окна (диапазона)
Type T_WND
  iFirst As Long 'начальный индекс в массиве
  iLast As Long  'завершающий индекс в массиве
  rTotal As Long 'сумма значений в диапазоне
End Type


Sub alg_version_1()

  Dim a()
  'получаем массив для обработки
  a = mk_array
  '---------------
   Dim N As Double
   Dim i As Long
   Dim xTotal As Long, Limit As Long
      
   ' подсчет суммы
   For i = LBound(a, 1) To UBound(a, 1)
     xTotal = xTotal + a(i, 1)
   Next
   'минимальный процент суммы длин, который должен содержать отыскиваемый диапазон
   N = 0.43 ' 43%
   
   'лимит, по превышении которого окно просмотра закрывается
   Limit = Round(N * xTotal, 0)
   
   Debug.Print "Total=" & xTotal & " N=" & N & " Limit=" & Limit
   '-------------------------------------------------------------
   
   ' диапазон-победитель
   Dim r_winner As T_WND
   
   r_winner.iFirst = -1
   r_winner.iLast = UBound(a, 1) + 1
   
   ' ищем самый узкий диапазон, содержащий сумму значений не менее, чем Limit
   FindNarrowRange r_winner, a, r_winner.iLast, Limit
   
   'печать результата
   If r_winner.iFirst >= 0 Then
     Debug.Print "Лучший диапазон: Старт="; r_winner.iFirst; " Стоп="; r_winner.iLast; " Сумма="; r_winner.rTotal; " Элементов:"; r_winner.iLast - r_winner.iFirst + 1
   Else
     Debug.Print "диапазон не найден"
   End If
   
   
End Sub

Sub FindNarrowRange(ByRef r_winner As T_WND, ByRef a() As Variant, ByVal iStop As Long, ByVal Limit As Long)
' поиск наиболее узкого диапазона
' параметры:
' ByRef r_winner As T_WND - результирующий диапазон
' ByRef a() As Variant - обрабатываемый двумерный массив
' ByVal iStop As Long - номер последнего индекса в массиве + 1
' ByVal Limit As Long - лимит суммы значений для закрытия окна

   ' текущий диапазон
   Dim r_current As T_WND

   While r_current.iFirst < iStop
       'формируем размер окна, содержащего сумму значений длин не менее, чем Limit
       make_window r_current, a, Limit, iStop
       
       'устанавливаем победителя между текущим и предыдущим окном
       CompareAndSet r_winner, r_current, Limit
    
       ' сдвигаем начало и сбрасываем ширину окна для нового шага цикла
       r_current.iFirst = r_current.iFirst + 1
       r_current.iLast = r_current.iFirst
       ' обнуляем сумму
       r_current.rTotal = 0&
   Wend

End Sub

Sub make_window(ByRef r_current As T_WND, ByRef a() As Variant, ByVal p_limit As Long, ByVal p_stop As Long) 
'формирование диапазона (окна) содержащего требуемый процент от общей суммы
   If r_current.iLast < p_stop And r_current.rTotal < p_limit Then
    Do
      r_current.rTotal = r_current.rTotal + a(r_current.iLast, 1)
      If r_current.rTotal >= p_limit Or r_current.iLast + 1 = p_stop Then
        Exit Do
      End If
      r_current.iLast = r_current.iLast + 1
    Loop
   End If
End Sub

Sub CompareAndSet(ByRef r_left As T_WND, r_right As T_WND, ByVal p_limit As Long)
'выбор и установка наилучшего диапазона
   If r_right.iLast - r_right.iFirst + 1 < r_left.iLast - r_left.iFirst + 1 _
       And r_right.rTotal >= p_limit Then
     LSet r_left = r_right
   End If
End Sub

Function mk_array() As Variant
'формирование массива анализируемых значений
Dim a()
  ReDim a(18, 1)
  '-- 0
  a(0, 0) = 327.31
  a(0, 1) = 6
  '-- 1
  a(1, 0) = 327.32
  a(1, 1) = 2
  '-- 2
  a(2, 0) = 327.33
  a(2, 1) = 4
  '-- 3
  a(3, 0) = 327.35
  a(3, 1) = 7
  '-- 4
  a(4, 0) = 327.36
  a(4, 1) = 4
  '-- 5
  a(5, 0) = 327.37
  a(5, 1) = 4
  '-- 6
  a(6, 0) = 327.39
  a(6, 1) = 8
  '-- 7
  a(7, 0) = 327.4
  a(7, 1) = 9
  '-- 8
  a(8, 0) = 327.41
  a(8, 1) = 5
  '-- 9
  a(9, 0) = 327.42
  a(9, 1) = 5
  '-- 10
  a(10, 0) = 327.44
  a(10, 1) = 1
  
  '-- 11
  a(11, 0) = 327.45
  a(11, 1) = 19
  '-- 12
  a(12, 0) = 327.46
  a(12, 1) = 11
  '-- 13
  a(13, 0) = 327.47
  a(13, 1) = 9
'-- 14
  a(14, 0) = 327.48
  a(14, 1) = 5
'-- 15
  a(15, 0) = 327.49
  a(15, 1) = 10
'-- 16
  a(16, 0) = 327.5
  a(16, 1) = 57
'-- 17
  a(17, 0) = 327.51
  a(17, 1) = 19
'-- 18
  a(18, 0) = 327.52
  a(18, 1) = 16
  '-----------
  mk_array = a
End Function



Пока не вижу, можно ли сделать что-то существенно лучше или нет.
...
Рейтинг: 0 / 0
17.08.2021, 13:06
    #40091188
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
https://jsfiddle.net/cb9ga7qj/ в принципе, по описанию Akina
расширяем окно вправо, а если оказалось больше или равно мин. сумме, то сужаем слева. Линейная сложность, без доп. памяти.


Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
function getBestRange(arr, minSum) {
    let begin = 0;
    let end = 0;
    let sum = 0;
    let bestBegin = -1, bestEnd = -1;
    while (end < arr.length) {
        sum += arr[end];
        end++;
        if (sum >= minSum) {
            while (sum - arr[begin] >= minSum) {
                sum = sum - arr[begin];
                begin++;
            }
            if (bestBegin < 0 || end - begin < bestEnd - bestBegin) {
                bestBegin = begin;
                bestEnd = end;
            }
        }
    }
    return [bestBegin, bestEnd - 1];
}


...
Рейтинг: 0 / 0
17.08.2021, 13:15
    #40091190
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
я ведь правильно понял, что все Y больше нуля?
иначе придется немного по-другому решить, тоже линейно, но уже с O(N) памяти
...
Рейтинг: 0 / 0
17.08.2021, 13:22
    #40091193
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Я тот самый "эксперт": в универсальной проге надо помнить на всякий случ, что значения м.б. <0.

mayton,
вспомнился вопрос о выборе лучшей невесты оптимальным способом. Вот если бы добавить ещё совсем неможко данных, то выбор оказался бы третьим по росту. И теоретическая оценка матож 3/4 от макс была бы превышена.
К сож в наборе этой длины скорее всего невеста будет ростом ~490, это ~в 1-й десятке , и от матож это уже дальше.
...
Рейтинг: 0 / 0
17.08.2021, 14:41
    #40091236
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
2Имя пользователя1,

можно положить
let bestBegin = 0, bestEnd = arr.length;
тогда проверка bestBegin < 0 уйдёт.

в остальном, кажется, nice
...
Рейтинг: 0 / 0
17.08.2021, 14:53
    #40091241
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Матрица скользящих сумм.

По горизонтали - отрезки. А по вертикали - скольящая сумма N соседей.
По матрице - должна образоваться некая "область" решений которую
удобно обозревать глазами. Как в транспортной задаче.
...
Рейтинг: 0 / 0
17.08.2021, 15:26
    #40091253
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
И нервную сеть на на матрицу напустить, чтобы самому не программировать.
...
Рейтинг: 0 / 0
17.08.2021, 15:37
    #40091255
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Кстати подобных экспериментов "непрограммирования" уже есть у нас.

Тут и там появляются НС которые то играют в Супер-Марио а то и программируют PacMan без строчки кода.
...
Рейтинг: 0 / 0
17.08.2021, 15:44
    #40091257
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
booby
можно положить
let bestBegin = 0, bestEnd = arr.length;
тогда проверка bestBegin < 0 уйдёт.
да, точно.

у меня с этими "крайними кейсами" всё время путаница )
...
Рейтинг: 0 / 0
18.08.2021, 10:00
    #40091402
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Голос из погреба,

что-то очень ваш график на гаусианы наложенные смахивает
Вы точно ищете то, что написали?

Я честно говоря подумал, исходя из рисунка, что нужно найти параметры гаусиан, это делается различными модификациями EM-методов
...
Рейтинг: 0 / 0
18.08.2021, 11:37
    #40091432
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Автор выложи все данные. Вместо этого огрызка.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
x        y
===========
327.31 	 6
327.32 	 2
327.33	 4
...
330.26	 5
330.27	10
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины / 17 сообщений из 17, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]