Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Задача: Имеется набор чисел. Необходимо распределить их по заданному количеству множеств таким образом, чтобы сумма чисел во множестве, имеющим самую большую сумму из всех остальных множеств в данном варианте распределения, была минимальной по сравнению со всеми остальными возможными вариантами распределения чисел по множествам. Пример 1: Имеется следующий набор чисел: 4; 5; 3; 4; 3. Необходимо распределить их на 2 множества. Ожидаемый ответ: множество 1: 5; 4 (сумма равна 9). множество 2: 4; 3; 3 (сумма равна 10) Пример 2: Имеется следующий набор чисел: 4; 5; 3; 4; 3. Необходимо распределить их на 3 множества. Ожидаемый ответ: множество 1: 5 (сумма равна 5). множество 2: 4; 3 (сумма равна 7) множество 3: 4; 3 (сумма равна 7) Я знаю один вариант алгоритма перестановки чисел, но не могу сформулировать условие его завершения. Я специально не стал его здесь писать, чтобы вам мозги лишним не забивать. Я уверен на 100 процентов что эта задача имеет давным-давно разработанное решение и математическое описание, но, увы, я его не знаю - сказывается отсутствие профильного образования :-( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 00:06 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Инет есть? Есть. Полазай, посмотри. Ты думаешь тебе сейчас с ъходу готовый алгоритм выдадут? Задача похожу на "медвежонковскую". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 00:30 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Ken_new Я уверен на 100 процентов что эта задача имеет давным-давно разработанное решение и математическое описание Однозначно. Поищи в сети. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 10:31 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Да понимаете, я пытался порыться в Интернете, но не нашёл ни фига. Проблема в том, что я не очень представляю как правильно сформулировать название задачи. Это явно не задача оптимизации, не задача поиска экстремумов и т.п. Подозреваю что она имеет какое-то конкретное наименование, но вот какое... Вообще, раз уж пошла дискуссия, расскажу какой алгоритм мне пришел в голову. Имеем набор чисел 4; 5; 3; 4; 3. Шаг 1: сортируем числа по убыванию: 5; 4; 4; 3; 3. Шаг 2: последовательно (то есть первое число - в первое множество, второе - во второе, третье - снова в первое и так далее) раскидываем числа на два множества: Множество 1: 5; 4; 3 (сумма 12). Множество 2: 4; 3 (сумма 7). Шаг 3. Перебрасываем из множества, имеющего максимальную сумму элементов, минимальное число в другое множество: Множество 1: 5; 4 (сумма 9). Множество 2: 4; 3; 3 (сумма 10). Ответ: минимальная сумма равна 10 Проблема в том, что я не могу сформулировать критерий, по которому алгоритм должен завершаться. Анализ сумм множеств не даёт результата, так как в общем случае не каждом шаге они могут меняться изменяются как в сторону увеличения, так и в сторону уменьшения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 10:57 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Это из области комбинаторных алгоритмов, дискретной математики ИМХО. Поищи по вышеуказанным ключевым словам. Задача явно популярная на производстве. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 11:04 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Может это поможет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 13:19 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Идея для полного перебора. Неэффективно, но хоть что- то. Количество шагов = (кол-во множеств) в степени (кол-во чисел) Представляем себе множества в виде столбиков одинаковой высоты, так чтобы все числа умещались в одно множество (столбик). Ставим столбики рядом.Начальная позиция- все числа в самый левый столбик. Перемещать числа будем только по горизонтали, т.е. числа не падают вниз и не поднимаются; суммы считаются по вертикали. Собственно, получается прямоугольный массив, заполненый нулями там, где нет наших чисел. Если количество чисел задано твердо- то перебор это столько вложеных циклов for, сколько чисел задано. Или можно рекурсивно. 1.Перебор всех состояний первого (самого нижнего) числа - это переход этого числа последовательно из самого левого в самый правый столбец. Здесь для каждого перехода считаются суммы и все что необходимо для запоминания "минимальной конфигурации" 2.Перебор всех состояний 2-го числа - это переход этого числа последовательно из самого левого в самый правый столбец, и для каждого такого перехода вызывается 1. 3.Перебор всех состояний N-го числа, это переход этого числа последовательно из самого левого в самый правый столбец, и для каждого такого перехода вызывается "Перебор всех состояний N-1 го числа". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2005, 21:58 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Извините , я немного не понял условия, что все таки надо минимизировать может надо просто получить несколько примерно равных по сумме групп чисел ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 11:33 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
ValerИзвините , я немного не понял условия, что все таки надо минимизировать может надо просто получить несколько примерно равных по сумме групп чисел ? Да нет. Аналогичная "жизненная" задача может звучать так: передача данных идет по нескольким каналам (аналог множест). Каждый передатчик требует себе определённое количество временных интервалов в канале для передачи данных (аналог чисел). Как распределить передатчики по каналам, чтобы в итоге занимать наименьшее количество временных интервалов с целью экономии ресурсов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 12:29 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
2 Ken new 1) Ты привел реальный пример из своего производства (то есть я хотел спросить примников-передатчиков действительно 3-5)? В этом случае я бы мог предложить алгоритм полного перебора. ИМХО можно вполне сгенерировать перестановки и сочетания 5 элементов по 3 группам и для КАЖДОГО случая посчитать оптимальность. Если из будет ОООЧЕНЬ много то лучше ограничить такой алгоритм по времени. То есть дать ему лимит (скажем 1 сек) и взять локально оптимальный план который ему удалось сформировать. 2) Какое минимальное время отклика требуется для выдачи плана распределения? Есть системы в которых это время меряется микросекундами. Есть менее критичные (сети передачи данных). Есть вообще некритичные электронная почта, новости, телеграф. 3) Может быть стоит подумать не над построением очередного плана а над ОПТИМИЗАЦИЕЙ существующего? То есть к примеру, нам удалось вычислить оптимальный план, и если передатчик № 1 выключается а через некоторое время включается передатчик № 2 то можно вносить кратковременные корректировки в план без полного перерасчета. 4) Какими библиотеками и технологиями пользуешся в разработке (некоторые элементы комбинаторных алгоритмов уже реализованы в STL). C уважениме Mayton ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 12:54 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
mayton2 Ken new 1) Ты привел реальный пример из своего производства (то есть я хотел спросить примников-передатчиков действительно 3-5)? В этом случае я бы мог предложить алгоритм полного перебора. ИМХО можно вполне сгенерировать перестановки и сочетания 5 элементов по 3 группам и для КАЖДОГО случая посчитать оптимальность. Если из будет ОООЧЕНЬ много то лучше ограничить такой алгоритм по времени. То есть дать ему лимит (скажем 1 сек) и взять локально оптимальный план который ему удалось сформировать. Не совсем из моего, но суть похожа. Реально элементов (ну, пусть будут "передатчики") может быть до ста. Мнеожеств ("каналов"), по которым они будут распределены - от одного до шести. mayton2 Ken new 2) Какое минимальное время отклика требуется для выдачи плана распределения? Есть системы в которых это время меряется микросекундами. Есть менее критичные (сети передачи данных). Есть вообще некритичные электронная почта, новости, телеграф. 3) Может быть стоит подумать не над построением очередного плана а над ОПТИМИЗАЦИЕЙ существующего? То есть к примеру, нам удалось вычислить оптимальный план, и если передатчик № 1 выключается а через некоторое время включается передатчик № 2 то можно вносить кратковременные корректировки в план без полного перерасчета. Система не рилтаймовая, поэтому время не очень критично. Другое дело что эту задачу, возможно, необходимо будет решить 500 или даже 1000 раз подряд. mayton2 Ken new 4) Какими библиотеками и технологиями пользуешся в разработке (некоторые элементы комбинаторных алгоритмов уже реализованы в STL). C уважениме Mayton Самое смешное и самое грустное, что эту задачу, возможно, необходимо будет решить средствами MS SQL'а, в хранимой процедуре, скорее всего :-( Вообще, я думаю что, возможно, тут следует соблюдать компромисс между быстродействием и точностью. Возможно следует применять алгоритм, работающий быстрее и возвращающий избыточное решение, вместо 100% точного алгоритма, но работающего очень долго. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 13:21 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Kenneth = Ken_new. Я зарегистрировался... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 13:22 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Ken_new ValerИзвините , я немного не понял условия, что все таки надо минимизировать может надо просто получить несколько примерно равных по сумме групп чисел ? Да нет. Аналогичная "жизненная" задача может звучать так: передача данных идет по нескольким каналам (аналог множест). Каждый передатчик требует себе определённое количество временных интервалов в канале для передачи данных (аналог чисел). Как распределить передатчики по каналам, чтобы в итоге занимать наименьшее количество временных интервалов с целью экономии ресурсов. насколько я понял в общей куче лежит несколько чисел ( до сотни) - времена передачи сигналов от разл передатчиков есть несколько каналов по которым их надо распихать число каналов может менятся что надо минимизировать ? общее время передачи или число каналов ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 17:28 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Valer насколько я понял в общей куче лежит несколько чисел ( до сотни) - времена передачи сигналов от разл передатчиков есть несколько каналов по которым их надо распихать число каналов может менятся что надо минимизировать ? общее время передачи или число каналов Общее время передачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 19:10 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
"минимизировать максимальную сумму" = "распределить числа по наборам как можно равномернее" Чипуха, короче говоря. Тем более, что есть готовое решение на t-sql от акуза: Код: plaintext 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2005, 21:39 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Абсолютно согласен с пред тов арищем B, надо просто равномерно разложить числа по заданному числу множеств. Если задача не динамическая т е в процессе раскладывания не появляются новые числа, то не вижу проблем в ее решении. Непонятно почему это надо делать на TSQL, а не на VB или Ci ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2005, 09:17 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
b"минимизировать максимальную сумму" = "распределить числа по наборам как можно равномернее" Чипуха, короче говоря. Тем более, что есть готовое решение на t-sql от акуза: Нифига не так. Не "распределить числа по наборам как можно равномернее", а распределить так, чтобы "минимизировать максимальную сумму". Вот такой набор чисел: 5 2 6 7 5 4 3 3 8 6 3 пример, который ты привёл, распределяет их так: 3 3 8 = 14 7 4 3 = 14 5 2 6 = 13 5 6 = 11 Максимальная сумма тут 14. А мне необходимо чтобы они были распределены следующим образом: 8 5 = 13 6 5 2 = 13 6 4 3 = 13 7 3 3 = 13 Максимальная сумма тут 13. Теперь понятно что мне нужно? Вообще, я написал алгоритм, который решает данную задачу так, как мне нужно. Сейчас я его тестирую и выложу как только буду уверен что он работает как надо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2005, 14:00 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
ValerНепонятно почему это надо делать на TSQL, а не на VB или Ci Такая архитектура системы, заложена ещё в 2000 году, сейчас ничего уже не изменить без глобального переписывания. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2005, 14:08 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Да Вы, батенка, шутник, однако. Или Вы думали, что я брошусь тестировать код акуза и ловить в нем баги? Его код обязан был выдать (почему не выдал - это вопрос к нему): 8 5 = 13 6 5 2 = 13 6 4 3 = 13 7 3 3 = 13 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2005, 14:29 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
bДа Вы, батенка, шутник, однако. Или Вы думали, что я брошусь тестировать код акуза и ловить в нем баги? Его код обязан был выдать (почему не выдал - это вопрос к нему): 8 5 = 13 6 5 2 = 13 6 4 3 = 13 7 3 3 = 13 Да к тебе претензий нет :-) Я просто думал что ты задачу неправильно понял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2005, 15:18 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
1 По моему мнению критерий оптимальности должен быть другой, если S сумма всех n чисел m число групп (множеств ), то минимизировать надо размер множества - S / m пример 101 , 101,101,97 лучше чем 102,100,99,99 2 задача может решаться приближенно раскладыванием n чисел по m группам. Если цена отклонения от оптимального решения не велика , то этого возможно достаточно точное решение имеет сложность A в степени n т.е. с ростом n катострофически растет ( возможно A > 2 ) т.к. надо генерировать все возможные комбинации элементов 3 В свое время делал задачу о рюкзаке, при числе групп m=2 указанная задача сводится к задаче о рюкзаке емкостью S/2 4 Делать точное решени на TSQL ,бессмыслено. Почему нельзя на клиенте прочитать таблицу, провести расчеты и записать результаты в таблицу? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.02.2005, 09:50 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Ну вот, выкладываю алгоритм как и обещал. Ломайте, тестируйте, критикуйте :-) Код: plaintext 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. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.03.2005, 16:28 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Я не очень внимательно читал прошлые месаги в этом топике, но по как я понял вопрос в АЛГОРИТМЕ. Зачем T-SQL ? Дайте алгоритм а кому как надо так и напишет. Мне например очень трудно разобратся в приведенных исходниках. Задачка кстати мне очень понравилась. С тех пор как я на ACM был мозги так не напрягал (в плане придумывания алгортма) Вот такие пока идеи есть: (если я пропустил готовый алгоритм - поправте меня) 1) однозначно суммы оджны минимально отличатся, в таком случае максимальная из них и будет минимальной для всех разных наборов. 2) Кто то там вспоминал о рюкзаке (или о двух). ИМХО это здесь не подходит. Хотя некорые аналогии можно провсти. И то и то по идее А вообще мне пахнет здесь жадными алгоритмами... По дороге с работы в метро обязательно подумаю. Хотя можно и в поисовиках поискть - но это не сравнится с тем удовольствием когда сам решаешь :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2005, 14:36 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
По поводу Жадных алгоритмов - пока не уверен. У задач, которые решаются с помощью жадных алгоритмов должно быть свойство оптимальности для подзадач. Как я помню задачу оптимизации можно решать при помощи жадного выбора, если последовательность локально оптимальных выборов дает глобально оптимальное решение. А вот в динамическом программирования просчитываются сразу последствия всех вариантов. Оптимальность для подзадач: оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. Так по поводу алгоритма больше никто не выскажется??? Придется читать T-SQL ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2005, 14:42 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Kenneth Нифига не так. Не "распределить числа по наборам как можно равномернее", а распределить так, чтобы "минимизировать максимальную сумму". А по моиму моему как раз наборы сума которых буде равномернее и будут решением задачи. Вопрост только в том, чт опонимать под словом равномернее. И кто то там говорил, что это задача не оптимизации... ИМХО как рах оптимизации. И еще то что надо числа отсортировать - факт! Какой бы алгоритм потом не применялся ему это понадобится Сегодня вечером обязательно что то придумаю :) Очень хочется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2005, 14:56 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
В кратце, алгоритм следующий: Шаг 1 : сортируем числа по убыванию и распределяем их по множествам "зейкой". То есть для набора чисел 5 2 6 7 5 4 3 3 8 6 3 и четырёх множеств это будет следующим образом: Сортировка: 8 7 6 6 5 5 4 3 3 3 2 Распеределение: (8 3 3) = 14 (7 4 3) = 14 (6 5 2) = 13 (6 5 ) = 11 Шаг 2 : переносим минимальный элемент из одного множества в другое при условии что разница их сумм больше чем переносимый элемент. Этот шаг повторяем до тех пор, пока приведённое выше условие выполняется. Таким образом при распределении чисел "змейкой" на перовом шаге, этот шаг для данного набора чисел игнорируется. Для других наборов, в которых числа различаются на большие величины, этот шаг выполняется. Шаг 3 : выбираются два множества - с максимальной и минимальной суммой элементов. Выполняем проверку что разность их сумм больше 1 (исходим из того, что работаем с целыми числами). Если это условие не выполняется, то нашли оптимальное решение, в противном случае находим разность между элементами множества (каждый элемент с каждым). Полученные разности упорядочеваем по возрастанию и находим попадающие в интервал [1, CEILING((S1 - S2)/2)] (где S1 и S2 - суммы множеств, CEILING - округление в большую сторону). Из значений, удовлетворяющих этому неравенству выбираем максимальное. Пару элементов множества, удовлетворяющих приведённому условию, меняем местами. Этот шаг повторяем до тех пор, пока можем поменять элементы местами. Таким образом: итерация 1: (8 3 3) = 14 (6 5 ) = 11 S1 - S2 = 3 Пары элементов: (8 - 6 = 2) (3 - 6 = -3) (3 - 6 = -3) (8 - 5 = 3) (3 - 5 = -2) ( 3 - 5 = -2) 1 <= Xij <= CEILING(1.5) = 2 меняем местами элементы 8 и 6. Получаем: (6 3 3) = 12 (7 4 3) = 14 (6 5 2) = 13 (8 5 ) = 13 итерация 2: рассуждая аналогично меняем местами элементы первого и второго множества. Тут, однако, возможны варианты. Можно поменять местами 6 и 7, либо 3 и 4. Однако, это не имеет значение что мы будем менять местами. Если мы менем местами 7 и 6, то получаем: (7 3 3) = 13 (6 4 3) = 13 (6 5 2) = 13 (8 5 ) = 13 - искомый результат. Если мы меняем местами 3 и 4 то получаем: (6 4 3) = 13 (7 3 3) = 13 (6 5 2) = 13 (8 5 ) = 13 - искомы результат. Вот. В принципе, основную роль в алгоритме играет шаг 3. Используя только его можно получить ответ, однако шаг 1 и шаг 2 значительно сокращают количество итераций на шаге 3. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2005, 17:54 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
О! Спасибо большое за алгоритм. Так я хоть понял. Он по идее правльный Однако мне что то заело (чисто с теор. точки зрения). Часов с 6-ти голову ламаю. Вот как-то мне он не неравится Как минимум нету доказательства, что он правильный. Особенно действия описаные в Шаге 3. Который по сути главный. Вопрос к теоретикам (Они же тоже должы читать этот форум:) ): что скажете? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2005, 01:06 |
|
||
|
Гуру, подскажите алгоритм решения задачи с множествами!
|
|||
|---|---|---|---|
|
#18+
Насколько помню такие алгоритмы называются обменно-итерационными. Известно, что в задаче разрезания графа (разбить множество вершин графа на 2 подмножества так, что бы сумма связей между подмножествами была минимальной) обменно-итерационный алгоритм дает лишь локально оптимальное решение. Хотя задача разрезания графа кажется более сложной, чем рассматриваемая за счет наличия связей между элементами, скорее всего аналогичная картина будет и здесь: варьируя начальное разбиение будем получать различные локальные минимумы, из который выберем наилучший. Что это будет глобальный минимум - не факт. Повторюсь еще раз, что это только мое предположение, но доказательство того, что обменно-итерационный алгоритм в этой задаче всегда сходится к глобальному минимуму действительно необходимо. В теории локального поиска есть предположение (однако такие вещи опасно обобщать), что "хорошие" алгоритмы слабо зависят от качества начального приближения и всегда находят локальные оптимумы определенной "силы". С этой точки зрения интересно посмотреть, дают ли шаги 1 и 2 преимущество по сравнению со случайным выбором начального разбиения. Если требуется найти точное решение, я бы поступил так. Ясно, что оптимум надо искать вблизи равномерных разбиений. В рассматриваемом примере общая сумма 52, идеальный случай 4 подмножества по 13. Находим все комбинации элементов, дающие в сумме 13 (это как раз одна из разновидностей задачи о рюкзаке). Далее смотрим существуют ли среди полученных комбинаций 4 таких, что: 1.Каждый элемент в них встречается ровно 1 раз. 2.Не существует элемента, который не встретился ни разу. В данном примере такое разбиение существует, но в общем случае его может и не быть. Тогда отступаем на шаг - 13,13,14,12 и повторяем процесс. Сколько итераций придется сделать в общем случае неясно, однако есть предположение, что конечное число :^) Способ хотя и не самый быстрый, но теоретически обоснованный: "правильность" конечного результата следует из "правильности" алгоритма решения задачи о рюкзаке, которую мы решаем на каждом шаге и которая известна. Кроме того, имея все комбинации элементов, дающие в сумме 13, можно искать не обязательно 4 подмножества , а также 3, 5 и т.д. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2005, 12:11 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1347815]: |
0ms |
get settings: |
8ms |
get forum list: |
17ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
134ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
| others: | 266ms |
| total: | 500ms |

| 0 / 0 |
