Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/practicum/disopt.pdf Дата изменения: Mon Sep 6 18:11:45 2010 Дата индексирования: Mon Oct 1 21:58:52 2012 Кодировка: Windows-1251

Дискретная оптимизация (П.А. Алисейчик, А.С. Строгалов)
1. Введение

1.1. Цели практикума
1. Использование ООП при проектировании архитектуры программы. 2. Анализ существующих алгоритмов. 3. Разработка своего алгоритма. 4. Оптимизация алгоритма. 5. Анализ сложности алгоритма. 6. Эксперимент и тестирование. 7. Общее представление о графических библотеках (на примере MFC). 8. Архитектура программ с графическим интерфейсом.

1.2. Указания по планированию архтектуры системы
Результатом работы должны быть 4 главных класса: 1. Класс, хранящий данные и решающий задачу ПО ШАГАМ. 2. Класс консольного интерфейса пользователя, позволяющий решать задачу целиком или по шагам. 3. Тестирующий класс. 4. Класс графического интерфейса пользователя, позволяющий решать задачу целиком или по шагам.

1


Консольное приложение должно использовать классы 1,2,3, MFC-приложение 1,3,4. Таким образом, классы 1 и 3 должны быть написаны таким образом, чтобы уметь взаимодействовать как с консольным, так и с графическим интерфейсом пользователя. Взаимодействие между классами осуществляется с помощью public-методов.

1.3. Этапы работы
Работа делится на этапы, каждый из которых заканчивается сдачей работающей программы: 1. План архитектуры системы: определения 2-х основных классов (алгоритм решения задачи по шагам и интерфейс пользователя), большинство методов пока без реализации. 2. Консольное приложение без оптимизации: реализована 1-я версия решения задачи по шагам и консольный интерфейс пользователя, файловый вводвывод. 3. Тестирование: проверка корректности работы алгоритма на различных входных данных. 4. Оптимизация: оптимизированная версия решения задачи, измерение сложности каждого шага и подсчет общей сложности решения задачи. 5. Анализ сложности и эксперимент: набор тестов, позволяющих обнаружить зависимость общей сложности решения от параметров задачи. 6. Графический интерфейс: MFC-приложение для визуализации хода решения по шагам.

2. Условия задач

2.1. Упаковка предметов в контейнеры
Дано:

N

предметов , каждому сопоставлен размер

p(i)

(вектор действительных чи-

сел длины

N

.) которые можно класть предметы (все ящики имеют вместимость фиксированы.

S ящиков, в V m > p(i)). Числа N , S

Программа из входного файла должна получать вектор размеров предметов и значение вместительности ящиков.

2


Надо: Реализовать алгоритм оптимальной (по количеству использованных ящиков) упаковки в предметов в ящики, или используя такой алгоритм: 1) отсортировать предметы по убыванию размера 2) первый предмет положить в 1 ящик, второй туда же, если влезает. если не влезает во второй. и т.д. Вывести ответ в выходной файл.

2.2. Задача о рюкзаке
По данному набору из

n

предметов стоимостями

v1 , v2 , . . . , v

n и весами

w1 , w2 , . . . , w

n

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

W

.

2.3. Покрытие таблицы из 0 и 1
Во входном файле задана матрица

N ЧM

из 0 и 1. Необходимо построить по-

крытие матрицы, используя следующий алгоритм: 1) Взять столбец веса рассмотрения. 2) В полученной матрице повторить процедуру. (Строка покрывает столбец, если на их пересечении находится 1. таким образом, матрица покрывается набором строк) Вывести ответ в выходной файл.

k

. Удалить его и все строки, которые его покрывают из

2.4. Гамильтонов цикл
В гиперкубе, заданном как векторе размерности Вывести ответ в выходной файл.

2N

, построить гамильтонов цикл.

2.5. Обход графа методом ближайшего соседа
Дан граф, как набор вершин (общее число

F

) и ребер (пар вершин) в фай-

ле. Используя алгоритм "ближайшего соседа"построить его обход по вершинам. Структура хранения графа на усмотрение решающего. Вывести ответ в выходной файл.

3


2.6. Гамильтонов обход графа
Дан полный граф, для которого выполнено неравенство треугольника, как набор вершин (общее число решающего. Вывести ответ в выходной файл.

F

) и ребер (пар вершин) в файле. Построить гамиль-

тонов обход графа. Найти его вес. Структура хранения графа на усмотрение

2.7. Минимальное остовное дерево
Дан граф, как набор вершин (общее число фа на усмотрение решающего. Вывести ответ в выходной файл.

F

) и ребер (пар вершин) в файле.

Построить минимальное остовное дерево графа. Структура хранения гра-

2.8. Эволюция слов

M из алфавита {0, 1, . . . , N }.N < M . Также M в файле задана функция F : {0, 1, . . . , N } {0, 1, . . . , N }M , в виде слова (это слово результат применения функции к набору 0, 1, l dots, N ). Для произвольноj го j построить F (W ). Проверить, нет ли в получившемся слове подряд идущих
В файле задано слово

W

длины

букв алфавита. Вывести ответ в выходной файл.

2.9. Х-О на доске
Задано число

N ЧN
Реализовать игру "крестики-нолики". Предполагается,

N > 10.

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

NЧ

N

. Выигравшим считается тот, кто первым построил ряд из 5 крестиков (или Консольный интерфейс: вывод на экран текущей позиции с виде

ноликов).

- 1 - 2 - 3 -

| + | + | + | -

a| -+ | -+ | -+ | --

b| -+ | -+ X| -+ | --

c| -+ | -+ O| -+ X| --

d| -+ | -+ O| -+ X| --

e| -+ | -+ | -+ O| --

| | | -| | -| | - -, f -

запрос с клавиатуры следующего хода человека.

4


Оптимизация алгоритма: функция оценки позиции, сокращение перебора таким образом, чтобы обеспечить оценку позиции на 3 хода вперед (2 хода программы и 1 ход человека). Усложнение задачи: реализовать игру на бесконечной доске (структуру данных для хранения позиции, обеспечивающую быструю оценку позиции).

2.10. Задача о раскройке
Дан прямоугольник

P ЧS

(длины сторон

P

и

S

задаются на входе программы

пользователем). Задано 20 фиксированного одинакового размера многоугольников вида "Г". Построить рациональную раскройку прямоугольника на многоугольники так, чтобы коэффициент

v

=(Площадь остатка прямоугольника после вырезания)/(

P ЧS

) был мини-

мальным из всех возможных случаев. Вывести ответ в выходной файл.

2.11. Нахождение подслов
Даны два слова ва

S

и

Q, S

причем длина слова

Q.

Требуется найти все вхождения и

Q

в

S S

намного превосходит длину сло. Программа должна считать из

входного файла слова

Q

и напечатать ответ в выходной файл.

2.12. Быстрое умножение двоичных чисел
Даны два

n-битовых

числа

x

и

y

. Если

n

не степень двойки, то надо эти числа до-

определить слева нулями. Требуется реализовать алгоритм быстрого умножения двоичных чисел. Алгоритм быстрого умножения состоит в следующем: 1. представляем каждое число

xиy

в виде

x = x1 x

2и

y = y1 y2

, где

x1 , x2 , y1 , y2



n/2-битовые
2. вычисляем

числа; ;

x1 y1 , x2 y2 ,(x1 + x2 )(y1 + y2 )

(n-1) 3. вычисляем xy по формуле: xy = (x1 Ч 2 2n + (x1 y2 + x2 y1 ) Ч 2(n-1) + x2 y2 , где x1 y2 + x2 y1

+ x2 )(y1 Ч 2(n-1) + y2 ) = x1 y1 Ч = (x1 + x2 )(y1 + y2 ) - x1 y1 - x2 y2 .

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

5


2.13. Быстрое умножение матриц
Даны две матрицы

A

и

B

размера

nЧn

. Если

n

не степень двойки, то надо

доопределить их нулями, например, начиная с верхнего левого угла. Требуется реализовать алгоритм быстрого умножения матриц. Алгоритм быстрого умножения состоит в следующем:

1. представляем матрицы где

A

и

B

в виде:

Aij , Bij

матрицы размера

A11 A12 A21 A22 (n/2) Ч (n/2); A=

B=

B11 B12 B21 B22

2. вычисляем

p p p p p p p

1 2 3 4 5 6 7

= = = = = = =

(A11 + A22 (A21 + A22 A11 (B12 - A22 (B21 - (A11 + A12 (A21 - A11 (A12 - A22 AB
4 5 4 3

)(B11 + B22 ) )B11 B22 ) B11 ) )B22 )(B11 + B12 ) )(B21 + B22 )
по формуле

3. вычисляем

AB =

C C

11 21

C C

12 22

, где

C C C C

11 12 21 22

= = = =

p p p p

1 3 2 1

+ + + +

p p p p

- p5 + p7 , , , - p2 + p6 .

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

2.14. Проверка однозначности декодирования

A = {a1 , . . . , ar } ставится в соответствие некоторое слово Bi из алфавита B = {b1 , . . . , bq }. Для каждого кода Bi рассмотрим все его нетривиальные разложения Bi = q1 Bj1 . . . Bjk q2 . Обозначим через V множество, содержащее пустое слово E и все слова q ,
Каждой букве

a

i из алфавита

встречающиеся в нетривиальном разложениях как в виде начал, так и в виде окончаний. Построим помеченный ориентированный граф правилам. Множеством вершин графа ны q1 в вершину q2 , если q1 является началом, а q Bj1 . . . Bjk .

G

по следующим

G

является

V

. Проводим дугу из верши-

и только если в некотором нетривиальном разложении

2 концом. При этом дуга

(q1 , q2 )

помечается словом

6


Схема кодирования не обладает свойством однозначности декодирования тогда и только тогда, когда граф

G

содержит контур, проходящий через вершину

E

. Программа должна считать из входного файла кодовые слова

Bi

и напеча-

тать в выходной файл либо 0, если граф вершину

G

содержит контур, проходящий через

E

(схема не обладает свойством однозначности декодирования), либо 1

в противном случае (схема обладает свойством однозначности декодирования).

2.15. Задача о куче камней

wi , i = 1, . . . , N , и l. Разбиваем мноM = {i|i = 1, . . . , N } на k подмножеств Mi , i = 1, . . . , k , где k < N . Вес подмножества W (Mi ) определяется как сумма всех wj из Mi . Вводится ограничение max (W (Mi )) < l .
Задано множество положительных чисел жество Требуется найти разбиение, для которого k минимально. Программа должна считать из входного файла сначала число

l

, а затем по-

w1 , . . . , w N , и i = 1, . . . , k множество {wj |j Mi },
следовательно числа

напечатать в выходной файл для каждого начиная каждое множество с новой строки.

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

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

l

. Требуется рас-

l

красок. Можно использовать любой алгоритм,

2.18. Нахождение кратчайшего пути
Дан граф без петель и кратных ребер и выделенная вершина

s

. Ребрам этого гра-

фа приписаны положительные числа. Требуется найти кратчайшие расстояния

7

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

s

до остальных вершин графа,

а также с новой строки вектора предшественников на кратчайших путях, т.е номера тех вершин, которые встречаются в этих путях.

2.19. Распределение последовательностей букв в тексте
Во входном файле записан текст. Пусть символов из алфавита лами на слова). Пусть

A

множество всех непробельных сим-

волов этого текста. Словом текста будем называть всякую последовательность

A L

(сам текст, при этом, разбивается пробельными симво длина длиннейшего слова текста. В выходной файл

последовательно для каждого натурального писать все слова длины

n

не превосходящего

L

следует за-

n

(в алфавите

A

), упорядоченные в порядке убывания

частоты встречаемости в качестве подслова в каком-то слове текста.

2.20. Наибольшее общее подслово
Входной файл содержит два слова, раздел?нных пробелом. В выходной файл следует записать их общее подслово максимальной длины (в частности, ничего не записать, если единственное общее подслово пустое слово).

2.21. Задача о растекании жидкости
Имеется клетчатая область размера

nЧk

. В начальный момент в каждой клетке

имеется некоторое количество жидкости. Процесс растекания жидкости происходит в дискретном времени в соответствии с правилом: для каждой ячейки Я области 1. если ячейка Я правая нижняя ячейка области, то жидкость, находившаяся в ней, оста?тся на месте; 2. иначе если ячейка Я крайняя правая ячейка области, то вся находившаяся в ней жидкость перетекает в соседнюю ячейку снизу; 3. иначе если ячейка Я крайняя нижняя ячейка области, то вся находившаяся в ней жидкость перетекает в соседнюю ячейку справа; 4. иначе

q

частей жидкости из ячейки перетекает в соседнюю ячейку справа,

а оставшиеся

(1 - q )

частей в соседнюю ячейку снизу.

8


Требуется смоделировать этот процесс. Входной файл содержит матрицу, задающую исходное распределение жидкости (n строк, в каждой строке

k

чисел, раздел?нных пробелом) и число

q

.В

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

2.22. Выпуклая оболочка
Дано конечное множество алгоритмом Грехема: 1. Пусть

M = {(x1 , y1 ), . . . , (xn , yn )}

точек на плоскости. Тре-

буется построить их выпуклую оболочку. Можно воспользоваться, например,

p

0 точка с наименьшей ординатой среди точек из

M

,а

p1 , . . . , p

n

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

M, p0 .
.

отсортированные в порядке возрастания

p0 , p1 , p2

3. Последовательно перебирая точки

p3 , . . . , p

n , в зависимости от направления

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

< xk , yk >,

раздел?нных

пробелами. В выходной файл следует вывести координаты точек выпуклой обо-

p

0 в порядке обхода против часовой стрелки.

2.23. Компоненты связности ориентированного графа
Дан ориентированный граф (без кратных р?бер). Множество называется компонентой связности, если для любых ентированный путь в графе из

v1 , v2

из

M вершин графа M существует ори-

v1 M

в

v2

, проходящий через вершины из множества

M

. Компонента связности

M

называется максимальной, если для любой вер, множество

шины

v

графа, не лежащей в

M

, объединенное с

v

, не является

компонентой связности. Требуется найти все максимальные компоненты связности графа. Матрица инцидентности графа, содержащего

n

вершин, это матрица раз-

n Ч n, в ребро из i-ой
мера строке

клетке

(i, j )

которой стоит 1, если граф содержит ориентированное

вершины в

j

-ую, и 0 в противном случае.

Входной файл содержит матрицу инцидентности графа (n строк, в каждой

n

чисел из множества

{0, 1}

, раздел?нных пробелом).В выходной файл

9


следует вывести матрицы инцидентности максимальных компонент связности (рассматриваемых как граф с не соединены ребром).

n

вершинами, некоторые из которых, возможно,

10