|
|
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
Есть прикладная задача, есть cамописное решение. Если встречались похожие задачи, просьба кинуть описание или ссылку. Есть идеи по уменьшению трудоемкости? Есть идеи, как можно элегантно решить такую задачу на sql? У меня получилось только через процедуру, серий запросов + циклом. Постановка задачи Есть набор объектов, у каждого из которых задан набор свойств: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 1. Один объект может входить только в одну группу. 2. Если 2 разных объекта содержат одинаковое свойство, они должны быть объединены в одну и ту же группу. 3. Если у двух разных объектов нет общего свойства, они должны быть в разных группах. Т.е. в примере будет 3 группы (перечислены свойства в каждой группе): Код: plaintext 1. На практике еще добавляются "начальные" группы и разбор конфликтов, если объект попадает в разные "начальные" группы, но пока для простоты все эти моменты пропустил. Алгоритм Код: 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.03.2011, 08:09 |
|
||
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
hellium, по-моему требование противоречиво: Код: plaintext 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2011, 09:19 |
|
||
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
Naf, Противоречия нет, это будет одна группа (у 1 и 2 объекта общее свойство B, у 2 и 3 - общее свойство C) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2011, 09:26 |
|
||
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
helliumNaf, Противоречия нет, это будет одна группа (у 1 и 2 объекта общее свойство B, у 2 и 3 - общее свойство C) а как же "3. Если у двух разных объектов нет общего свойства, они должны быть в разных группах. "? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2011, 09:50 |
|
||
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
Naf, Да, это я неаккуратно написал :(. Попробую переформулировать: 1. Один объект может входить только в одну группу. 2. Если 2 разных объекта содержат одинаковое свойство, они должны быть объединены в одну и ту же группу, 3. При "транзитивной" похожести (например, [A,B], [B,C], [C,D]), объекты должны быть в одной и той же группе. 4. Если у двух разных объектов нет общего свойства (за исключением случаев "транзитивной" похожести), они должны быть в разных группах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2011, 10:21 |
|
||
|
Алгоритм выделения общих свойств объектов
|
|||
|---|---|---|---|
|
#18+
Это настолько элементарная задача (выделение связных компонент графа), что я пас ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.03.2011, 14:16 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=37166900&tid=1343070]: |
0ms |
get settings: |
6ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
186ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
45ms |
get tp. blocked users: |
1ms |
| others: | 248ms |
| total: | 509ms |

| 0 / 0 |
