Использование алгоритмов порождения комбинаторных объектов при решения задач выбора

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

В задаче из примера 1 исходным множеством S (множеством из которого формируются траектории) является совокупность из n камней, а траекторией будет его разбиение на два подмножества S ₁ и S ₂, таких, что S ₁È S ₂= S и S ₁Ç S ₂=0. Если { s ₁, s ₁,…, s_n } - массы камней, то - функционал, а - оптимальное значение функционала. Перебор траекторий осуществляется с помощью систематического порождения подмножеств S ₁, множества S. Всего траекторий 2 ⁿ.

В задаче из примера 2 в качестве исходного множества выступают все возможные пары городов. Траекторией будет совокупность этих пар, образующая маршрут из начального города, удовлетворяющий всем перечисленным требованиям. Функционалом является сумма стоимостей проезда между парами городов, образующих траекторию. Оптимальным решением будет траектория с минимальным значением функционала. Для организации полного перебора траекторий в данной задаче необходимо порождение всех перестановок из n-1 элементов. Всякая такая перестановка Р=(р1,р2,…,рn-1) определяет допустимый маршрут:

" начальная вершина "® р ₁® р ₂®…® р_{n -1}®" начальная вершина ".

Всего траекторий (n -1)!.

Задача из примера 3 также сводится к порождению всех перестановок n -элементного множества.

Дата добавления: 2014-12-27