Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

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

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

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

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

,

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

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

()=()+t

()=0;

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

F() =

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

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

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

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

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

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

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




Переглядів: 712

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

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

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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