| Вопрос: Помогите с алгоритмом. | Добавлено: 05.06.06 13:28 |
Автор вопроса:  dr.Faust
|
|
Задача:
Есть таблица как на рисунке (слева). Колонки A, B, C, D могут выбираться из заданного диапазона (4 таблицы справа). Таким образом, если значение C1 = 3 то C2 = 4, а C3 = 5. Нужно сгенерировать N разных случайных таблиц - это просто. Сложно: Ситуация когда есть число WXYZ (0 <= W,X,Y и Z <= 15) такое, что W=A, X=Bi, Y=Ci и Z=Di удовлетворяющее сразу нескольким таблицам - коллизия. Необходимо сгенерировать случайный набор таблиц с минимальным числом коллизий. Даже не знаю с чего начать, сначало пробывал составить последовательности соответствий групп из B и C такие которые имеют пересечения, например для 1-ой группы из B это 9 и 10 группы. Закодировать эти группы кодами генерить последовательность из таких кодов, проверяя на то, что бы не было идентичных, потом вместо кодов случайно выбирать конкретную группу. Это ни чего не дает. Что делать дальше не знаю. Есть идеи? P.S. На самом деле таблица там подлиннее, число допустимых значений побольше, но нужна общая идея. P.P.S Хранить таблицы и при каждой генерации выполнять проверку - не предлогать, там может быть N>1000000. Рисунок: http://forum.ixbt.com/post.cgi?id=attach:26:34669:0:1 P.P.P.S А как вставить рисунок сюда? |
| Ответы | Всего ответов: 5 |
|
Номер ответа: 1 Автор ответа:  Nj ICQ: 223663115 Вопросов: 21 Ответов: 285 |
Профиль | | #1 | Добавлено: 05.06.06 18:15 |
|
maybe Функция rnd() для генерации случайных чисел...?
|
||
|
Номер ответа: 2 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74 |
Профиль | | #2 | Добавлено: 05.06.06 21:50 |
|
Не фига не понял но могу сказать:
1: генири число A 2: проверяй на коллизию числа А с предыдущими если А удовлетворяет нет коллизий то запоминай его и иди к шагу (1) иначе отбрось его и иди к шагу (1) если было отпрошено больше Т чисел то тут 2 стратегии стр 1: принимаешь любое число (запоминаешь) и переходишь к шагу (1) стр 2: если возвращались с этого места(под местом подразумевается кол-во сгенерированных чисел) уже больше Z раз то использовать стратегию 1 иначе вернуться назад отбросить несколько чисел уже полученных и прейти к шагу (1) Если плотность коллизий велика то лучше придерживаться первой стратегии, а то может вообще не бить даны без коллизий и первая стратегия даст результат быстрее, а вторая будет дольше выполняться! Если плотность коллизий не велика, то вторая стратеги даст лучший результат чем первая! |
||
|
Номер ответа: 3 Автор ответа: dr.FaustВопросов: 6 Ответов: 26 |
Профиль | | #3 | Добавлено: 06.06.06 13:32 |
|
Может я не совсем правильно объяснил.
Вот пример коллизии: http://forum.ixbt.com/post.cgi?id=attach:26:34669:6:1 Все три таблицы удовлетваряют числу 0 3 4 11, хотя они и разные. |
||
|
Номер ответа: 4 Автор ответа: dr.FaustВопросов: 6 Ответов: 26 |
Профиль | | #4 | Добавлено: 06.06.06 13:40 |
|
2 Nj Да пофиг. Можно и rnd(), можно написать какой нибудь конгруентный датчик, можно сгенерить заранние каккойнибудь большой набор таблиц и случайным образом выберать необходимое количество из него. Особо равномерное распределение не нужно. Нужен свиду случайный набор, главное с минимальной плотностью коллизий. |
||
|
Номер ответа: 5 Автор ответа: FeverВопросов: 60 Ответов: 808 |
Профиль | | #5 | Добавлено: 07.06.06 12:26 |
| md? | ||
Страница: 1 |