Мозгопромывающая задача на перебор...

← →
q10nik (2006-11-30 09:11) [0]

Есть динамический массив записей

ObjBase=record
//имя объекта
ObjName:string[200];
//свойства объекта заполн. не все
ObjProp:array[1..10] of string[80];
//рассчитанное значение значимости объекта на основе ответов пользователей
ObjValu:real;
// zn:=(ObjValu*PropCh)/PropCount-1; //рассчитанное значение уровня защищенности
zn:real;
//реальное количество свойств 0,1,2...10 объекта
PropCount:byte;
//номер выбранного свойства данного объекта (для рассчета zn)
PropCh:SmallInt;
end;

AR:array of ObjBase;
длинна массива определяется количеством введенных в файл объектов
SetLength(ar,ObjectsCount);

А ЗАДАЧА ТАКАЯ: вводится суммарный уровень безопасности Z=СУММ(AR[n].zn), => мне по всем элементам массива ar нужно перебирать допустимые PropCh и вычислять zn, складывать все полученные AR[n].zn и если они примерно равны Z то записывать полученную комбинацию элементов AR и продолжать поиск пока
не будут перебраны все комбинации

P.S. если не лень то хотя бы небольшой фрагмент...
всем заранее спасибо.

← →
Ганна Юхимівна (2006-11-30 09:15) [1]

Небольшой фрагмент :)
procedure MindAblutionTask(); begin // Начало вычислений... end;

← →
novill © (2006-11-30 10:53) [2]

Получается, что зафиксировав значения PropCh в массиве тебе придется перебрать (2^n) комбинаций элементов массива.

В худшем случае таких фиксированных наборов 10^n.(PropCount, если у всех объектов заполнены все поля. Если заполнены не все то надо перемножить все ненулевые PropCount элементов массива)

Таким образом в пессимистическом варианте получается 2^n*10^n=20^n.

Ну, или если очень грубо (например в среднем в объектах заполнено 5 свойств) 10^n итераций.

Помножь на стоимость одной итерации, которая тоже зависит от n, получишь время выполнения :)

Оно тебе надо?

Ну если сильно надо, то реши сначала отдельно задачу перебора всех комбинаций элементов массива, потом отдельно задачу получения всех возможных наборов значений PropCh, вложи одну в другую и добавь вычисление суммы и сравнение с заданной точностью.

Удачи :)

← →
q10nik (2006-11-30 17:46) [3]

Это система моделирования объектов защиты информации, тестовый экземпляр.
Реальная ситуация - будет порядка 200 объектов у каждого от 5 до 300 свойств, причем можно добавлять и удалять объекты.
Методом парного сравнения каждого объекта устанавливается значение для каждого из них - ObjValue
Т.е. учитвая сложность реализации тех или иных объектов защиты можно будет строить гибкие и дешевые модели с заданным уровнем безопасности
за основу конечно стоит брать OpenBSD =)

to novill спасибо за идею правда реализовать пока не смог
кстати PropCh<=PropCount в любом случае

кто с реализацией перебора помочь может???

> PropCh<=PropCount в любом случае
это и так понятно.

1. алгоритм перебора всех сочетаний элементов есть в инете (я, правда, видел только в качестве блок-схемы)
2. алгоритм перебора всех вариантов значений PropCh проще всего сделать с помощью простого пересчета в неоднородной позиционной системы счисления (как в десятичной, но максимальное значение у каждого разряда своё) т.е. увеличиваешь значение PropCh у первого элемента до тех пор пока оно не достигнет PropCount, как достигло - обнуляешь и увеличиваешь значение в следующем разряде, если достигло максимума там, то обнуляешь, и увеличиваешь в следующем... алгоритм простой.

> 200 объектов у каждого от 5
у тебя получается 5^200 вариантов = 10^100

Если задачу функционально не ограничить, она не разрешима :)
Если конечно у тебя нет под рукой сверхмощной системы :)

Надо разбираться с условиями.

Мозгопромывающая задача на перебор... Найти похожие ветки