Презентация за алгоритмите на Pokritta
Подобни презентации
Презентация по темата: „Покритни алгоритми . Пример за проблем с покритието Да предположим, че организацията трябва да наеме преводачи за френски, немски, гръцки, италиански,“ - Стенограма на презентация:
2 Пример за проблем с покритието Да предположим, че организацията трябва да наеме преводачи от френски, немски, гръцки, италиански, испански, руски и китайски на английски и че има пет кандидати A, B, C, D и E. Всеки кандидат има само собствена подгрупа от горния набор от езици и изисква много специфична заплата. Необходимо е да се реши кои преводачи (от горните езици на английски) трябва да бъдат наети, за да поддържат разходите за заплата възможно най-ниски. Това е най-малкият проблем с покритието.
3 Математическо описание на проблема Нека бъде набор за подкрепа. Има много подмножества. На всяко подмножество се присвоява номер, наречен цена. Наборът се нарича решение на проблема с покритието или просто покритие, ако условието е изпълнено. В този случай цената. Терминът "покритие" означава, че множеството от комплекти съдържа всички елементи от множеството B, т.е. Обхваща множеството B.
4 Определения и теореми Покритието се нарича нередудентно, ако след премахване на поне един елемент от него престане да бъде покритие. В противен случай покритието е излишно. Покритието P се нарича минимално, ако цената му е най-малката сред всички покрития за даден проблем. Покритие P се нарича най-кратко, ако l е най-малкото от всички корици на дадения проблем. Минимално и кратко покритие - не е излишно.
5 Изложение на проблема с покритието 1. Необходимо е да се намери цялото покритие. За да се реши проблемът, е необходимо да се извърши цялостно изброяване на всички подмножества от множеството А. 2. Необходимо е да се намерят само неподходящи корици. Няма прост и ефективен алгоритъм, който да не изисква изграждането на всички излишни покрития. (Използва се търсене на граници или декомпозиция на колони в TP). 3. Необходимо е да се намери такъв без излишно покритие. Решението на проблема се основава на намаляване на таблицата. Покриващите проблеми могат да бъдат решени точно (за малко измерение) или приблизително.
6 Таблица на покритието Удобно и визуално представяне на първоначалните данни и техните трансформации в проблема с покритието е таблицата на покритието. Таблицата на покритието е матрицата T на отношението на принадлежност на елементите от множествата към референтния набор B. Колоните на матрицата са свързани с елементите на множеството B, редовете - с елементите на множеството A
7 Съставяне на таблица за покритие