powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
17 сообщений из 17, страница 1 из 1
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40090723
Всем привет.

Допустим, есть набор точек (заданы координатами):
Код: 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
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40090729
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Голос из погреба,

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

И кстати, мне кажется, что достаточно проскользить по накопительной кривой заданным окном (N% в высоту). Проскользить слева направо и выбрать эти наиболее узкие интервалы. Тогда вобще один цикл. На глаз вижу 2х претендентов.
...
Рейтинг: 0 / 0
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091044
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091046
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну мимо одного цикла, в самом начале, считающего общую сумму, никуда, надо же знать, сколько это - N%.
А дальше второй цикл.
Держим два указателя, на начало и конец окна, и текущую сумму значений между ними.
Если текущая сумма больше - сравниваем вариант с уже имеющимся. Если он лучше (или если имеющегося - ещё нет), запоминаем. Иначе - сдвигаем первый указатель и повторяем. Если сдвигать некуда - завершаем.
Если проверяли, надо ли запоминать, проверяем, можно ли сдвинуть второй (останется ли сумма больше). Если можно - сдвигаем и повторяем.

Оптимальный порядок действий (для уменьшения количества проверок и веток) искать лениво. Самостоятельно разберётесь.
...
Рейтинг: 0 / 0
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091100
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
накидал 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
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091188
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091190
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
я ведь правильно понял, что все Y больше нуля?
иначе придется немного по-другому решить, тоже линейно, но уже с O(N) памяти
...
Рейтинг: 0 / 0
Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
    #40091193
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тот самый "эксперт": в универсальной проге надо помнить на всякий случ, что значения м.б. <0.

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

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

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

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

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

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

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

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

Код: 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
17 сообщений из 17, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти минимальное подмножество смежных отрезков с длиной >= N% от общей их длины
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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