Перестановка

Розділ 4. Алгоритми перестановок та сортування.

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

Задача про чергу у приймальній.

В приймальній зібралося п відвідувачів. Попереднє опитування дозволило з'ясувати, скільки часу повинен виділити директор кожному відвідувачу (ti). Треба так організувати прийом, щоб відвідувачі знаходилося у приймальній настільки можливо менше часу.

Розв'язком цієї задачі буде деяка перестановка чисел

яка відповідає черзі прийому відвідувачів.

Позначимо через ()час чекання у приймальні відвідувача iза тією чергою, яка задає перестановка . Очевидно, що

()=()+t

()=0;

В цьому випадку формулюємо таке: знайти таку перестановку , на якій величина

F() =

приймає найменше значення.

Задача про приймальну - найпростіша з задач складання черг.Ця задача потребує складання розкладу, вона зводиться до суворого впорядкування виконання деяких робіт. Після відповідної формалізації така задача зводиться до пошуку екстремальної перестановки. Функцію екстремуму називають оптимізуючою функцією або функцією-крітерієм.

Ще один приклад такої задачі: задача про наречених.

Сережа

Лиля

Андрей

Саша

Оля

Зоя

В деякому царстві на одинокому острові живуть n хлопців та m дівчат.
Треба їх найкращим чином переженити. Але:
Оля любит Сашу,
и Зоя любит Сашу,
а Саша любит Лилю,
Лиля же любит Андрея,
да Андрей никого не любит,
но зато вот Саша
по-прежнему любит Олю...

Вважається, що не виключено можливість будь-якого шлюбу, але деякі шлюби мають переваги перед іншими: оцінка шлюбу задається значенням a, які визначаються експертним шляхом.

Ця задача відноситься до класу задач про призначення.

Переглянуті задачі зводяться до побудови перестановок. Розглянемо алгоритми їх побудови.

<== попередня сторінка	\|	наступна сторінка ==>
Контрольні запитання.	\|	Алгоритм 1.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.002 сек.