Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного та граничного перебору

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Факультет інтелектуальних інформаційних технологій та автоматизації

Кафедра КН

Лабораторна робота №1

з дисципліни «Дискретна математика»

Виконала: ст. гр. 1КН-22Б                                                 Гуцол А. А.

Перевірив викладач:                                                                   Кирилащук Т. Г.

Вінниця, 2023 р.

Тема: Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного та граничного перебору 

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

Хід роботи:

[pic 1]

[pic 2]Метод повного перебору включає в себе перебір всіх можливих підмножин таблиці покриттів, в той час як метод граничного перебору - достатньо знайти лише ненадлишкові покриття.[pic 3]

[pic 4][pic 5]
[pic 6][pic 7]

[pic 8] [pic 9] [pic 10][pic 11]

[pic 12]

Блок-схема коду

Лістинги програм

1. Повний перебір

from itertools import *

changeToLetter = {

    '1' : 'А',

    '2' : 'Б',

    '3' : 'В',

    '4' : 'Г',

    '5' : 'Д',

    '6' : 'Е',

    '7' : 'Ж',

}

values = [3, 2, 4, 1, 2, 2, 1]

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

table = [{0, 2, 3, 0, 5, 0, 0, 8, 0},

         {1, 0, 3, 4, 0, 0, 0, 8, 0},

         {1, 0, 0, 4, 0, 6, 7, 0, 9},

         {0, 2, 0, 0, 0, 6, 0, 0, 9},

         {0, 0, 3, 4, 0, 0, 0, 0, 9},

         {1, 0, 0, 0, 0, 0, 7, 8, 0},

         {0, 0, 0, 0, 5, 6, 7, 0, 0}]

for item in table:

    print(item)

print()

listPrices = {}

listCount = {}

tmpPrice = 0

tmpCombNumber = []

tmpCombLetter = ''

tmpCombUnion = set()

for integer in range(1, 8):

    for combination in combinations('1234567', integer):

        for numberCombitation in combination:

            tmpCombLetter += changeToLetter[numberCombitation]

            tmpCombNumber.append(int(numberCombitation))

        for i in combination:

            tmpCombUnion = tmpCombUnion.union(table[int(i) - 1])

        if tmpCombUnion == U:

            listCount[tmpCombLetter] = len(combination)

            for index in tmpCombNumber: