Проектирование полно переборных алгоритмов

Сформулировать задачи, согласно вариантам, указанным преподавателем, (см. ниже варианты заданий) на языке теории множеств или теории графов.

Определить, что для данных задач является траекториями, функционалами и оптимальными значениями функционалов.

Разработать алгоритмы решения задач. Для этого свести перебор траекторий к генерации тех или иных комбинаторных объектов и, если необходимо, организовать отбор траекторий, отвечающих оптимальному значению функционалов[10]. Пример решения одной из задач смотри ниже.

Реализовать алгоритмы решения задач.

Подготовить ответы на следующие контрольные вопросы:

Понятие задачи выбора. Что характерно для задач выбора?

Понятие траектории и функционала.

Основные понятия теории графов.

Матричное задание графов.

Варианты заданий

Подмножество V вершин графа G называется независимым (или внутренне устойчивым), если никакие две вершины из V не смежны. Найти наибольшее по мощности независимое множество вершин заданного графа.

Подмножество V вершин графа G называется доминирующим (или внешне устойчивым), если каждая вершина из VG \ V смежна с некоторой вершиной из V. Найти наименьшее по мощности доминирующее множество вершин заданного графа.

Требуется расставить на шахматной доске наибольшее число ферзей так, чтобы они не атаковали друг друга.

Указание: сведите задачу к задаче поиска независимого множества вершин графа наибольшей мощности (задача №1).

Требуется расставить на шахматной доске наименьшее число ферзей так, чтобы каждая клетка была под боем.

Указание: сведете задачу к задаче поиска доминирующего множества вершин графа наименьшей мощности (задача №2).

Задан граф G, все веса ребер равны 1. Найти наименьшее подмножество вершин V Í VG, такое, что каждая вершина графа должна находиться на расстоянии не более 1 от какой-либо вершины из V.

Указание: Установите связь между данной задачей и задачей № 2.

Подмножество V Í VG называется покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из ЕG инцидентно хотя бы одной вершине из V. Найти покрытие минимальной мощности заданного графа.

Указание: Установите связь между данной задачей и задачей поиска независимого множества вершин графа наибольшей мощности (задача №1).

Подмножество V вершин графа G называется кликой, если любые две входящие в него вершины смежны, т.е. понятие клики является антиподом понятия независимого множества (см. задачу №1). Найти клику наибольшей мощности для заданного графа.

Подмножество ребер Е Í ЕG называется реберным покрытием графа G, если каждая вершина из VG инцидентна хотя бы одному ребру из Е. Найти все реберные покрытия заданного графа G.

Подмножество попарно несмежных ребер графа называется паросочетанием (или независимым множеством ребер). Найти все паросочетания заданного графа.

Паросочетание (см. задачу №9) называется совершенным (или 1-фактором), если оно одновременно является реберным покрытием (см. задачу №8). Найти все совершенные паросочетания заданного графа.

Имеется конечное множество исполнителей { х ₁,..., х_n }, каждый из которых может выполнять некоторые из работ { у ₁,..., у_n }. Для каждого исполнителя задан список работ, которые он может выполнять. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы. Найти все возможные распределения исполнителей по работам.

Указание: свести задачу к задаче №10.

То же, что и задача №11, только задана стоимость выполнения работы у_i исполнителем х_i, и требуется распределить исполнителей по работам, минимизируя затраты.

Два графа G ₁ и G ₂ называются изоморфными, если существует взаимно однозначное соответствие f: VG ₁® VG ₂, такое, что (v, w)Î EG ₂, тогда и только тогда, когда (f (v), f (w))Î EG, т.е. существует соответствие между вершинами графа G ₁ и вершинами графа G ₂, сохраняющее отношение смежности (графы G ₁ и G ₂ отличаются только нумерацией вершин). Определить, являются ли два заданных графа изоморфными.

Заданы два графа G ₁ и G ₂. Требуется определить, существует ли в G ₂ порожденный подграф, изоморфный графу G ₁.

Заданы множество А и множество В, причем элементами последнего служат некоторые подмножества из первого, и В является покрытием множества А, что означает следующее: объединение всех элементов из В, т.е. соответствующих подмножеств из А, равно множеству А. Требуется найти все покрытия множества А, составленные из элементов множества В.

Есть n станков. Каждый из станков делает различные операции (какие задано). При обработке детали необходимо выполнить k заданных операций. Найти минимальное множество станков, требуемых для обработки детали.

Определить, имеет ли заданный неориентированный граф гамильтонов цикл.

Всего n рабочих. В выездной бригаде должны находиться рабочие, которые все вместе владеют не менее чем k заданными специальностями. Для каждого рабочего задан список его специальностей. Сформировать бригаду из минимального числа рабочих.

Существует ли решение в (0,1) – числах следующего уравнения: , и b заданы.

Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью s ₁, s ₂,…, s_k тонн, . Стоимость рейса c ₁, c ₂,…, c_k руб. не зависит от массы груза, перевозимого самолетом. Найти оптимальное множество самолетов для перевозки груза.

То же, что и задача №21, только c ₁, c ₂,…, c_k зависят от массы груза.

Получить все возможные бинарные отношения между элементами конечного n -элементного множества, удовлетворяющие условиям симметричности и антирефлексивности.

Получить все возможные бинарные отношения между элементами конечного n -элементного множества, удовлетворяющие условиям антисимметричности.

Задано бинарное отношение между элементами конечного множества мощности n. Проверить является ли данное отношение транзитивным.

Найти все матрицы размера n ´ n с элементами из множества {0,1}, удовлетворяющие следующим условиям:

Город разделен улицами на квадраты со стороной равной 1 ед. Таких квадратов в направлении с севера на юг n, а в направлении с запада на восток – m. Перечислить все кратчайшие пути из крайней северо-западной точки города в крайнюю юго-восточную точку. Каждый путь выдавать на экран. Требования к графическому представлению пути не выдвигаются. Путь может быть изображен с помощью символов “|” и “_”.

Пример представлен на рис 6.

Перечислить все способы расстановки n-ладей на «шахматной» доске размера n´n. Причем никакие две ладьи не должны стоять на одной вертикали или горизонтали (ладьи не должны атаковать друг друга). Требования к графическому представлению ладей и шахматной доски не выдвигаются. Для изображения местоположения ладьи можно использовать любой символ.

Задано множество предметов. Для каждого предмета известен его вес. Можно ли разделить предметы на две равные по весу части.

Разработать алгоритм генерации всех логических функций n -переменных. Функции выдать в СДНФ.

Разработать алгоритм генерации всех самодвойственных логических функций n -переменных. Функции выдавать в СДНФ.

Разработать алгоритм генерации всех линейных логических функций n -переменных. Функции выдавать в виде полинома.

Проверить, не содержит ли строка символов представляющая логическую функцию в ДНФ синтаксических ошибок, и вычислить таблицу истинности этой функции.

Например, логическая функция может быть представлена следующей строкой ^x1&x2Vx2&^x3&x4Vx3&x5. Данная строка не содержит синтаксических ошибок. Строка ^x1&x2Vx2&^x3&x4V&x5 содержит синтаксическую ошибку в 17-ой позиции.

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

Например, логическая функция может быть представлена следующей строкой ^((^x1&x2Vx4)&^x3V^(x5&x6)). Данная строка не содержит синтаксических ошибок. Строка ^((^x1&x2Vx4)&^x3V^(x5&x6) содержит синтаксическую ошибку в 26-ой позиции – нет закрывающейся скобки.

Задана логическая функция в ДНФ. Каждая элементарная конъюнкция кодируется двумя векторами – вектором вхождения () и вектором обращения (). Элементы векторов определяются следующим образом:

Вычислить таблицу истинности заданной логической функции.

Например, логическая функция может быть закодирована в массиве из двух элементов. Каждый элемент представляет собой структуру из двух полей - и (рис.7). Символ «*» обозначает любое значение – 0 или 1. Обычно вектора и хранят в битовой форме (для хранения элементов и используется 1 бит).

	1		2
VV
VO			*	*	*

Рис.7

Логическая функция записана в ДНФ с использованием общепринятых соглашений (знак конъюнкции опускается; нумерация переменных осуществляется натуральными числами от 1 до n, где n – число переменных). Такая запись закодирована в массиве следующим образом:

Вычислить таблицу истинности заданной логической функции.

Например, логическая функция будет закодирована в массиве как показано на рис.8.

1	2	3	4	5	6
	-2			-3	-4

Рис.8

Логическая функция задана в СДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Выполнить все возможные склеивания.

Например, в логической функции можно выполнить следующие склеивания: и . Т.о. в результате выполнения всех возможных склеиваний получим элементарные конъюнкции и . Т.е. из исходного массива A необходимо получить массив B (рис.9).

A	1		2		3
VV
VO

B	1		2
VV
VO		*		*

Рис.9

Логическая функция задана в СДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Выполнить все возможные склеивания и все возможные поглощения.

Указание. Использовать список, каждая компонента списка хранит вектор вхождения и обращения.

Для функции процесс формирования списка изображен на рис.10.

Две логические функции заданы в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Проверить функции на эквивалентность.

Две логические функции f и g заданы в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Проверить является ли функция g импликантом функции f.

Две логические функции f и g заданы в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Проверить является ли функция g простым импликантом функции f.

Две логические функции f и g заданы в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Проверить является ли функция g двойственной к f.

Логическая функция задана в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Проверить является ли заданная функция самодвойственной.

Логическая функция f задана таблицей истинности. Найти полином Жегалкина функции f.

Указание. Для нахождения полинома Жегалкина можно использовать метод неопределенных коэффициентов, состоящий в следующем. Рассматривается полином в виде

и для каждого набора составляется уравнение . Решение этих уравнений дает коэффициенты полинома . Например, задана логическая функция , ее полином имеет вид

Составим систему уравнений.

Находим , . Таким образом, .

Логическая функция задана в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Найти полином Жегалкина заданной функции.

Логическая функция задана в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Найти все существенные переменные заданной функции.

Логическая функция задана в ДНФ. Каждая конъюнкция кодируется вектором вхождения и вектором обращения, см. задачу 34. Найти все фиктивные переменные заданной функции.

Логическая функция задана в ДНФ как в задаче 35. Определить есть ли в функции фиктивные переменные.

Разработать и обосновать структуры данных для хранения импликантной матрицы (матрицы Квайна). По заданной импликантной матрице найти все тупиковые ДНФ логической функции.

Определить таблицу истинности логической функции заданной бинарным графом.

Используя формулу разложения логической функции по переменной любую логическую функцию можно представить следующим образом

Используя эту формулу, можно представить логическую функцию в виде бинарного графа, в котором имеется ровно одна вершина без входящих в нее дуг (начальная); все вершины по числу выходящих дуг делятся на два типа: вершины с двумя выходящими дугами (условные вершины), вершины без выходящих дуг (заключительные вершины). Дуги помечаются символами 0 и 1. Условные вершины помечаются символом переменной, заключительные – комадой " ".

Пример бинарного графа, задающего функцию , приведен на рис. 11. Здесь вершины – начальная; , и - условные; и – заключительные.

Каждому набору значений аргументов в БГ соответствует путь из начальной вершины в заключительную вершину. Таким образом, БГ каждому набору значений аргументов ставит в соответствие значение функции и может служить для ее задания и вычисления. Разным наборам может соответствовать один и тот же путь. Например, для графа, изображенного на рис.11, наборам и соответствует путь .

Даны два бинарных графа (см. предыдущую задачу). Определить задают ли эти графы одну и ту же логическую функцию.

Например, бинарные графы, изображенные на рис. 11 и 12 задают одну и ту же логическую функцию .

Пример решения

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

Траекторией данной задачи является подмножество выбранных предметов (предметов положенных в рюкзак), функционалом – стоимость данных предметов. Таким образом, для решения задачи необходимо перебрать все 2 ⁿ подмножеств предметов и найти подмножество, удовлетворяющее условиям задачи.

Пусть масса и стоимость предметов хранятся в массиве записей MS. Каждая запись содержит два поля: M – масса предмета и S – стоимость предмета. В переменной n хранится число предметов, в переменной MaxSM – максимальная суммарная масса выбранных предметов.

Текущее подмножество предметов будем хранить в массиве b, в котором b [ i ]=1, если i -й предмет принадлежит подмножеству, и b [ i ]=0, если i -й предмет не принадлежит подмножеству. Суммарную стоимость и массу предметов составляющих текущее подмножество будем хранить в переменных SS и SM соответственно. Для запоминания подмножества выбранных предметов будем использовать массив b 1 аналогичный массиву b. Суммарную стоимость выбранных предметов будем хранить в переменной MaxSS.

Укрупненная блок-схема алгоритма решения задачи представлена на рис.11.

В приложении 3 (вариант 1) представлена реализация алгоритма решения задачи на языке Turbo Pascal. При этом для организации перебора траекторий взят алгоритм порождения подмножеств в порядке двоичного счета (алгоритм 1).

Если при организации перебора траекторий за основу взять алгоритм порождения подмножеств в порядке минимального изменения (алгоритм 3), то быстродействие алгоритма может быть повышено. Это достигается за счет более быстрого подсчета функционала.

Действительно если подмножества порождаются в порядке минимального изменения, то текущее подмножество отличается от предыдущего только одним элементом. Поэтому для подсчета суммарной стоимости предметов составляющих текущее подмножество (переменная SS) не надо суммировать стоимость каждого из этих предметов. Достаточно выполнить только одно из действий:

- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем удаления некоторого предмета, то необходимо от стоимости предметов составляющих предыдущее подмножество отнять стоимость данного предмета;

- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем добавления некоторого предмета, то необходимо к стоимости предметов составляющих предыдущее подмножество добавить стоимость данного предмета.

Сказанное относится и к подсчету суммарной массы предметов составляющих текущее подмножество (переменная SM).

Реализация алгоритма решения задачи на языке Turbo Pascal с использованием алгоритма порождения подмножеств в порядке минимального изменения представлена в приложении 3 (вариант 2).

СПИСОК ЛИТЕРАТУРЫ

Айгнер М. Комбинаторная теория. – М.: Мир, 1982. – 556 с.

Ахо Х., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977. – 368 с.

Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.

Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики: Пер. с укр. - М.: Наука. Гл. ред. физ.-мат. лит.,1977.-80 с.

Компьютер и задачи выбора / Автор предисл. Журавлев Ю.И.-М.: Наука, 1989.-208 с. -(теория "Кибернетика - неограниченные возможности и возможные ограничения").

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - 2-е изд., перераб. и доп. - М.: Энергоатомиздат, 1988. -480с.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975. – 240 с.

Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич.- М.: Наука. Гл. ред. физ.-мат. лит., I990.-384 с.

Муромцев В.В. Методы синтеза логических схем: Учебное пособие. Белгород: Изд-во БелГТАСМ, 1994. – 78 с.

Прикладная теория цифровых автоматов/ К.Г. Самофалов,
А.М. Романкевич, В.Н. Валуйский и др. – К.: Вища шк., 19897. – 375 с.

Рейнгольд Э., Нивергельт Ю., Дэо Н. Комбинаторные алгоритмы (теория и практка): Пер. с англ. - М.: мир, 1980.- 476 с.

Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука, 1980. – 400с.