 |
|
|
 
|
|
Тройки штейнера 
| Master_ |
|
|||
|
Бывалый  Профиль Группа: Участник Сообщений: 247 Регистрация: 31.1.2007 Репутация: нет Всего: нет |
http://en.wikipedia.org/wiki/Steiner_system
Мало инфы в инете... Помогите найти алгоритм... Можно на php/pascal/c/c++/javascript/русский Не понимаю как написать программу... Штейнеровская система троек - такое 3-подмножество, что всякое 2-подмножество встречается один раз. Например 1..9 (V=9) {1,2,3}, {1,7,9}, {2,7,8}, {3,6,9}, {1,4,5}, {2,4,9}, {3,4,8}, {4,6,7}, {1,6,8}, {2,5,6}, {3,5,7}, {5,8,9}. |
|||
|
||||
Загрузка ...
| nworm |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 502 Регистрация: 22.10.2005 Репутация: 4 Всего: 8 |
Какую программу?
Вы пытаетесь привести определение, но не говорите какую надо писать программу. |
|||
|
||||
| Master_ |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 247 Регистрация: 31.1.2007 Репутация: нет Всего: нет |
Генерации троек штейнера до 15ти... Число можно и вводом получить.
А вот как генерировать? |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Вероятно, перебором. Для каждой тройки мы решаем, брать её или нет. Смотрим, если в текущей тройке есть такое 2-подмножество, которое уже встречалось, то эту тройку не берём. Многовато конечно пробных троек, но, по-видимому, другого пути нет. Пару отсечений можно придумать, вероятно, для N=15 прокатит.
|
|||
|
||||
| SoWa |
|
|||
 Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Перебор- это все же решение в лоб
 Даже и с отсечениями. Неинтересно *серьезно задумался, хотя я не Штейнер* Вот тут есть немного по теме под авторством Мура: няяя К вечеру придумаю что-нибудь свое, надеюсь -------------------- Всем добра |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
SoWa, удачи тебе в этом нелёгком деле.
Замечу только, что задача генерации троек Штейнера является NP ;) (даже не NP-полной, как это обычно бывает с задачками от Штейнера , а именно NP ). |
|||
|
||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Действительно, без переборов не выйдет.
Смотрите, что седня надумал. При решении задачи в лоб большинство пожелает составить 3-множества и их уже отсекать. Достаточно много итераций получится. Вроде получится меньше, если делать так: составить все возможные 2-множества а потом их дополнять либо с начала, либо с конца, при этом уже просматривая и отсекая варианты, которые уже есть. Воот, критикуем. -------------------- Всем добра |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
SoWa, одобряем
И правда, перебор такой должен работать намного быстрей того, который по тройкам идти будет. Если б не сессия, накатал бы оба варианта и сравнил бы |
|||
|
||||
| Master_ |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 247 Регистрация: 31.1.2007 Репутация: нет Всего: нет |
Нашел книжку с небольшим описанием задачи, но ничего не понял, что там они с матрицами объясняют.
http://www.eknigu.com/info/0pre-Library/no...dpi)(193s).djvu Надо сдавать уже а я так и не сделал :( |
|||
|
||||
| SoWa |
|
|||
|
Харекришна Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Делай перебор по тому методу, что я написал немного выше.
-------------------- Всем добра |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0947 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |