На головну

Метод неявного перебору по векторної решітці

  1. B) Систематизація конкретно-наукових і загальнонаукових методів пізнання.
  2. D. Симплекс-метод
  3. FDDI. Архітектура мережі, метод доступу, стек протоколів.
  4. I. Внесення відомостей в форму ДМВ-1 при використанні методу визначення митної вартості за ціною угоди із ввезених товарів
  5. I. МЕТОДИКА
  6. I. Методичні вказівки для виконання контрольних робіт
  7. I. Методичні вказівки з підготовки

Векторної гратами називають математичну структуру, визначальну розташування і взаємозв'язок різних значень целочисленного n-мірного вектора х = (х1, .., хn), у якого кожна компонента хi може приймати цілочисельні значення починаючи з хi-min, і закінчуючи хi-max.

Окремі точки вектора х розташовуються за рівнями Хеммінга, які визначаються за допомогою поняття відстані Хеммінга.

відстанню Хеммінга між двома векторами Х1= (Х11, .., Хn1) І Х2= (Х12, .., Хn2) Називається величина визначається таким чином

n

? = ? | xi1 - xi2 ?

і = 1

рівнем Хеммінга називають розташування точок векторної решітки відстань Хеммінга до яких від однієї точки до іншої однакові.

При цьому номер рівня приймають рівним величині відстані Хеммінга.

Формування векторної решітки завершує правило, згідно з яким 2 її точки, що знаходяться на сусідніх рівнях і стоять один від одного на відстані Хеммінга дорівнює одиниці соеденения дугою.

Маршрутом називають будь-який шлях проходять через вершини векторної решітки соеденения дугами.

Крок вперед це перехід на рівень з великим номером.

Крок назад - це зворотний рух.

Для скорочення перебору по векторної решітці в методі ісспользуется 3 критерію:

1. Критерій неприпустимість

2. Критерій планомірного виключення альтернатив

3. Критерій кращою змінної

критерій неприпустимість застосовується до кожної точки векторної решітки після початкового потрапляння в неї за допомогою кроків вперед він формує залишкові умови неможливості досягнення при русі вперед з даної точки жодного допустимого рішення. Якщо ці умови виконуються, то кажуть, що критерій відсіває дану точку. Необхідно закінчити рух вперед і зробити крок назад по векторної решітці.

Критерій планомірного виключення альтернативзастосовується до окремих кроків вперед з даної точки х після того як знайдено 1-е допустиме рішення. Суть роботи-критерій відсіває ті кроки вперед які не можуть привести до кращих, т. Е. Меншим значенням цільової функції, допустимим рішенням. Його дії засновано на исспользование фільтруючого обмеження.

Критерій кращою змінної(КПП)-це критерій для впорядкування кроків вперед з кожної неприпустимою крапки не отсеяной за критерієм неприпустимість після 1-го приходу в неї.

Мета критерію - розглянути ті маршрути які призводять до допустимим рішенням. Дія критерію щодо скорочення перебору якщо мета впорядкування реалізується, проводиться спільно з критерієм кращою змінної. Чим раніше буде знайдено 1-е допустімоерешеніе тим раніше включається КПП, при кращих допустимих рішеннях дія обмежена по відсіву кроків вперед стає плоским.



Метод лексикографічного перебору | наближені методи

Математичне формулювання завдань дискретного програмування | Метод відсікань. Формулювання вірного відсікання. алгоритм методу | Переваги та недоліки алгоритму. | Формування нижніх і верхніх оцінок цільової функції | алгоритм методу | комбінаторні методи | Алгоритм симплекс методу | Друга стандартна форма | Вихідна задача в канонічній формі | Xi |

© um.co.ua - учбові матеріали та реферати