Структуры и алгоритмы обработки данных на ЭВМ
Классификация структур данных. Алгоритмы поиска и сортировки массивов и файлов. Работа с последовательностями. Динамические структуры данных – виды списков и деревья поиска. Методы машинного представления графов, алгоритмы обхода, поиска кратчайших путей.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | учебное пособие |
| Язык | русский |
| Дата добавления | 02.04.2012 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
осле этого происходит возврат и i-й объект удаляется из выборки.
Классический алгоритм с возвратом стал бы рекурсивно генерировать всевозможные решения без i-го объекта - принцип включения-невключения действует иначе.
Прежде, чем пытаться получать решения без i-го объекта, проверим, можно ли, не включив этот объект, получить решение лучшее, чем найденное оптимальное с i-м объектом. Если нет - то не стоит и пытаться.
ак проверить возможность получения без i-го объекта более ценной выборки, чем текущая оптимальная, если мы не собираемся сразу строить эти выборки?
ужно посчитать стоимость, которую мы, может быть, наберем без i-го объекта. Для этого просуммируем стоимости всех предметов, уже вошедших в выборку, и стоимости всех еще неисследованных предметов (разумеется, без i-го объекта).
сли эта стоимость, которую, может быть, удастся набрать (а, может, и не удастся - ведь неисследованные объекты могут не пройти ограничение по весу!) будет больше оптимальной - есть смысл генерировать решения без i-го объекта.
пишем рекурсивную процедуру TRY с включением-невключением.
1 procedure try(i);
{i - номер объекта}
2 begin
3 IF ВКЛЮЧЕНИЕ ПРИЕМЛИМО THEN
4 begin
5 включить i-тый объект;
6 if i=N then проверить оптимальность
7 else try(i+1); {продолжить выборку}
8 удалить i-тый объект; {возврат}
9 end;
{оптимум с i-тым объектом запомнен, а сам объект удален}
10 IF НЕВКЛЮЧЕНИЕ ПРИЕМЛИМО THEN
{подсчет возможной стоимости без i-того объекта и сравнение ее с оптимальной}
11 if i=N then проверить оптимальность
12 else try(i+1);
{строим выборки без i-того объекта}
13 end;
усть имеется 3 предмета и ограничение по весу 16:
|
НОМЕР |
1 |
2 |
3 |
|
|
ВЕС |
5 |
8 |
11 |
|
|
СТОИМОСТЬ |
10 |
8 |
15 |
ервый раз из основной программы вызывается try(1). Рассмотрим трассировку алгоритма:
|
try(i) |
№ 1 |
№ 2 |
№ 3 |
Сумма-рный вес |
Суммарная стоимость |
Возможная стоимость |
Оптимальная стоимость |
Примечания |
|
|
try(1) |
+ |
? |
? |
5 |
10 |
33 |
0 |
Вкл. 1 |
|
|
try(2) |
+ |
+ |
? |
13 |
18 |
33 |
0 |
Вкл. 2 |
|
|
try(3) |
+ |
+ |
- |
13 |
18 |
18 |
18 |
Оптимум |
|
|
try(2) |
+ |
- |
? |
5 |
10 |
25 |
18 |
25>18 Невкл. 2 |
|
|
try(3) |
+ |
- |
+ |
16 |
25 |
25 |
18 |
Оптимум |
|
|
try(1) |
- |
? |
? |
0 |
23 |
23 |
25 |
23<25 Невкл. 1 неприем. |
оследний оптимум, равный 25 достигается на выборке [1,3] и далее уже не меняется.
режде, чем записать алгоритм решения задачи о рюкзаке, сделаем полное описание глобальных переменных.
CONST N = 3;
VES = 16;
TYPE index = 1..N;
obj = record
v,st: integer {вес и стоимость}
end;
VAR A: array[index]of obj; {массив объектов}
X,OptX: array[index]of boolean;
{выборка, оптимальная выборка}
SumCost: integer;{общая стоимость всех объектов}
OptCost: integer; {оптимальная стоимость}
ЛГОРИТМ {Рюкзак}
анные: Массив A записей obj, ограничение по весу VES.
езультаты: Выборка max ценности с ограничением по весу.
{Считаем, что массив записей A уже сформирован}
1 procedure My_try(i:index; sum_v,pos_st: integer);
{i - текущий объект, sum_v - вес текущей выборки,
pos_st - возможная стоимость}
2 begin
{включение}
3 if sum_v + A[i].v <= VES then
4 begin {проверка допустимости}
5 X[i]:= ложь;{включаем i-й}
6 if (i=N) and (pos_st > OptCost) then
7 begin {новый оптимум}
8 OptX:= X; OptCost:= pos_st
9 end
10 else
11 My_try(i+1, sum_v+A[i].v, pos_st);
{строим решения с i-тым объектом, pos_st не изменилась, т.к. i-тый объект из неисследованных перешел во включенные}
12 X[i]:= истина;{возврат}
13 end; {проверка допустимости}
{невключение}
14 st1:= pos_st-A[i].st; {возможная ценность без i-того объекта}
15 if st1 > OptCost then
16 if i=N then
17 begin {новый оптимум}
18 OptX:= X; OptCost:= st1
19 end
20 else
{строим решения без i-того объекта}
21 My_try(i+1, sum_v, st1);
22 end;
1 begin {основная часть}
2 SumCost:= 0;
3 for i:=1 to N do
4 begin
5 SumCost:= SumCost+A[i].st;
6 X[i]:= истина; OptX[i]:= истина;
7 end;
8 OptCost:=0;
9 My_try(1, 0, SumCost);
10 печать OptX, OptCost;
11 end.
Вопрос 2. Почему первый вызов My_Try происходит с возможной стоимостью, равной SumCost?
Вопрос 3. Почему мы передаем суммарный вес рюкзака и возможную стоимость в виде параметров, а не вычисляем их внутри процедуры My_Try в цикле за O(N) шагов?
Ответ 1. При удлинении решения будет добавляться отрицательная стоимость, в результате чего будет происходить уменьшение целевой функции cost, в то время как она не должна убывать.
Ответ 2. Все предметы неисследованы.
Ответ 3. В наихудщем случае обращение к My_Try будет происходить 2N раз и, соответственно, этот цикл будет выполняться 2N раз.
данные алгоритм последовательность граф
10. Кратчайшие пути
В этом разделе будут рассмотрены алгоритмы поиска маршрутов, позволяющие не только «дойти до выбранного места», но и сделать это «самым коротким путем».
Дадим основные определения и обозначения для объектов, из которых будет построена наша математическая модель.
Будем рассматривать ориентированные графы, дугам которых приписаны веса (рис. 10.1).
Рис. 10.1. Модельный граф
Это означает, что каждой дуге (u>v) поставлено в соответствие вещественное число A[u,v]. Матрицу весов дуг данного графа будем обозначать A, несуществующим дугам будем приписывать веса, равные +, т.е. A[u,v] = +, если дуга (u>v) не существует.
Матрица весов A для модельного графа (рис. 10.1):
|
+ |
1 |
+ |
+ |
3 |
|
|
+ |
+ |
3 |
3 |
8 |
|
|
+ |
+ |
+ |
1 |
-5 |
|
|
+ |
+ |
2 |
+ |
+ |
|
|
+ |
+ |
+ |
4 |
+ |
В программе граф будет задаваться матрицей весов и (если потребуется) списками инцидентности PRED и SLED. В списках PRED для каждой вершины v хранится список ее предшественниц u, т.е. вершин, из которых дуга идет в эту вершину.
В списках SLED для каждой вершины v хранится список ее потомков, т.е. вершин, в которые из v идет дуга.
Длина пути будет подсчитываться как сумма весов, входящих в него дуг.
Зафиксируем в графе пару вершин s (источник) и t (сток).
Длину кратчайшего пути от s до t будем обозначать D[s, t], где D - матрица расстояний между всеми парами вершин. Если такого пути не существует, то будем считать, что D[s, t] = +.
Если источник s зафиксирован, то расстояния от s до остальных вершин графа будут храниться в векторе (одномерном массиве) D, где D[v] - расстояние от s до v.
Как видно из определения, дугам могут быть приписаны отрицательные веса. Если в графе существует контур (замкнутый путь) отрицательной длины, то понятие кратчайшего пути теряет смысл: обходя этот контур сколь угодно большое число раз, можно сделать длину пути как угодно малой.
Если потребовать, чтобы в качестве кратчайшего пути искать только элементарные пути, т.е. пути, не содержащие контуров, то задача станет вполне корректной, но, увы, NP - полной. Поскольку мы собираемся решать нашу задачу не алгоритмом с возвратом, а разработать для нее эффективные полиномиальные алгоритмы, придется умерить свои требования и поставить задачу так, чтобы мы могли ее решить.
Окончательная постановка: БУДЕМ ИСКАТЬ КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ БЕЗ КОНТУРОВ ОТРИЦАТЕЛЬНОЙ ДЛИНЫ.
На таких графах кратчайшие пути автоматически будут элементарными, так как добавление контура может привести только к увеличению стоимости пути. В этом разделе мы рассмотрим четыре алгоритма, которые будут вычислять матрицу D расстояний между источником и всеми остальными вершинами:
- первый подходит графам самого общего вида, т.е. без контуров отрицательной длины;
- второй применяется для графов с неотрицательными весами;
- третий - для бесконтурных графов;
- четвертый на графе общего вида находит расстояния между всеми парами вершин.
Сразу возникает вопрос: зачем нужны четыре различных алгоритма, когда для решения всех этих задач было бы достаточно одного, самого первого?
Дело в том, что идет борьба за эффективность, т.е. вычислительную сложность алгоритма. Чем более специального вида граф, тем более быстрым специализированным алгоритмом решается задача о кратчайшем пути.
Прежде, чем рассматривать эти алгоритмы, обратим внимание на следующее: алгоритм выдает в качестве результата не сами пути, а матрицы расстояний. Решим следующую задачу:
зная расстояния от источника s до всех остальных вершин, найдем путь от источника до какой-то выбранной вершины t.
Если нам удастся по последней вершине t восстановить предпоследнюю (назовем ее v), то задача решена. Восстановим предпоследнюю, по ней предпредпоследнюю и так до тех пор, пока не дойдем до источника.
Предпоследняя вершина v кратчайшего пути обладает следующим свойством: D[s,t] = D[s,v] + A[v,t].
ЛГОРИТМ {Восстановление кратчайшего пути от s до t.}
анные: Расстояния D[v] от источника s до всех остальных vV, фиксированная вершина t, матрица весов A[u,v], u,vV.
езультаты: СТЕК, содержащий путь от s до t.
1 begin
2 СТЕК:= 0; СТЕК t; v:= t;
3 while v<>s do
4 begin
5 u:= первая из списка PRED[v];
6 while D[v]<>D[u]+A[u,v] do
7 u:= следующая из списка PRED[v];
8 СТЕК u; v:= u;
9 end
10 end.
Так как для поиска всех вершин u происходит просмотр не более m дуг (в списках PRED), то вычислительная сложность этого алгоритма О(m). Заметим, что при наличии в графе контура нулевого веса эта процедура зацикливается, и ее следует модифицировать таким образом, чтобы исключать повторяющиеся вершины.
Вопрос. Как переделать процедуру восстановления пути так, чтобы в случае существования нескольких путей одной длины на печать выдавались все?
Ответ. Цикл (6-7) находит одну предыдущую вершину, но для печати всех путей нужно находить все такие вершины.
10.1 Алгоритм Форда - Беллмана
Рассмотрим теперь алгоритм, формирующий массив расстояний D для самого общего случая, т.е. для графа без контуров отрицательной длины.
Мы должны вычислить матрицу расстояний D[v]. За начальные (приближенные) значения D[v] возьмем веса дуг A[s,v]. Они будут соответствовать путям из s в v длиной в одну дугу. Если дуги (s>v) не существует, то начальное D[v] принимается равным +. Расстояние от источника до самого себя всегда считается равным 0.
Каким образом можно уточнить значения D[v]? Взять все пути из s в v длиной в две дуги и сравнить их с начальными D[v]. За окончательное значение D[v] принимается минимальное. Затем берутся пути длиной в три дуги и т.д. Процесс пересчета будет продолжаться до тех пор, пока не будут рассмотрены пути длиной в n-1 дугу. Нет смысла рассматривать пути длиной в n и более дуг, так как они будут содержать контур, который только увеличит суммарную длину пути.
Остается выяснить, каким образом из пути в k дуг можно получить все пути длиной в k+1 дугу. Из рис. 10.2 видно, что, добавив между s и v промежуточную (предпоследнюю) вершину u, мы автоматически удлиняем путь ровно на одну дугу. Длина старого пути равна D[v], длина нового пути равна D[u] + A[u,v].
Рис. 10.2. Удлинение пути на одну дугу
ЛГОРИТМ Форда - Беллмана
анные: Орграф G=<V,E> с n вершинами и выделенным источником s, заданный списками инцидентности PRED, матрица весов A[u,v], u,vV; граф не содержит контуров отрицательной длины.
езультаты: Расстояния D[v] от источника s до всех остальных vV.
1 begin
2 for vV do D[v]:= A[s,v];
3 D[s]:= 0;
4 for k:=1 to n-2 do
5 for vV-[s] do
6 for uPRED[v] do
7 D[v]:= min(D[v], D[u]+A[u,v]);
8 end.
Возможно, для вычисления D[v] нам не потребуются все n-2 итерации. Момент, когда D[v] будет вычислен окончательно, легко определить. Это произойдет, когда выполнение цикла 4 не вызовет изменения ни одного значения D[v].
Вычислительная сложность алгоритма О(nm). Если граф не является «разреженным» и число дуг m n2 , то можно считать вычислительную сложность равной О(n3).
Трассировка работы алгоритма Форда - Беллмана для графа с рис. 10.1:
|
k |
D[1] |
D[2] |
D[3] |
D[4] |
D[5] |
|
|
0 |
1 |
+ |
+ |
3 |
||
|
1 |
0 |
1 |
4 |
4 |
9 |
|
|
2 |
0 |
1 |
4 |
3 |
-1 |
|
|
3 |
0 |
1 |
4 |
3 |
-1 |
Вопрос. Можно ли воспользоваться алгоритмом Форда - Беллмана для неориентированного графа, заменив каждое неориентированное ребро парой противоположно направленных дуг одного веса?
Ответ. Можно только в том случае, если при этом не образуется контур отрицательного веса, т.е. только для неориентированного графа с неотрицательными весами.
10.2 Алгоритм Дейкстры
Рассмотрим отдельно случай, когда веса всех дуг ориентированного графа неотрицательны.
Разделим все вершины V графа на два множества: T и V-T. T - рабочее множество, в нем содержатся вершины u T, для которых еще не известны окончательные D[u]. V-T - множество вершин, для которых уже известны настоящие расстояния.
В начальный момент в V-T содержится единственная вершина - источник s, все остальные вершины содержатся в T.
На каждой итерации основного цикла одна вершина из T будет переводиться в V-T. Этой вершиной r будет та, у которой D[r] минимально среди всех вершин множества T. Как только такая минимальная r будет найдена и переведена из T в V-T, для оставшихся вершин u T нужно будет пересчитать расстояния D[u].
Пересчет производится следующим образом: проведем путь от s к u через вершину r. Длина этого пути сложится из D[r] и веса дуги A[r,u]. Новое значение D[u] выберется как минимальное из старого D[u] и длины D[r]+A[r,u].
Алгоритм закончит работу, когда все вершины из множества T будут переведены в множество V-T. Доказательство корректности этого алгоритма будет приведено чуть позже, опишем сам алгоритм.
ЛГОРИТМ Дейкстры
анные: Орграф G=<V,E> с выделенным источником s, матрица неотрицательных весов A[u,v], u,v V.
езультаты: Расстояния D[v] от источника s до всех остальных v V.
1 begin
2 for vV do D[v]:= A[s,v];
3 D[s]:= 0;
4 T:= V-[s];
5 while T<>0 do
6 begin
7 поиск вершины r из T, для которой D[r]=min(D[u], uT);
8 T:= T-[r];
9 for uT do D[u]:= min(D[u], D[r]+A[r,u]);
10 end;
11 end.
Подсчитаем вычислительную сложность этого алгоритма.
Цикл 4 выполняется n-1 раз, так как именно столько вершин переводится из T в V-T. Внутри цикла при поиске минимальной просматривается не более n вершин; при пересчете расстояния пересчитываются не более, чем для n вершин. Окончательно получаем О(n2).
Докажем корректность первого шага алгоритма, когда из множества T, содержащего все вершины за вычетом источника, удаляется минимальная вершина r. Рассмотрим для иллюстрации модельный граф на рис. 8.27.
Рис. 10.3. Первый шаг алгоритма
В первый момент расстояния D[v] равны весам дуг A[s,v]. Минимальной вершиной r (вершина 2) является вершина с минимальным весом дуги (s>r) (дуга (1>2) с весом 1). Ни в одну другую вершину нельзя прийти более коротким путем, так как либо первая дуга (s>u) (дуга (1>4) с весом 2) (u r) будет уже длиннее, либо к дуге (s>r) нужно будет добавить хотя бы одну дугу, а веса всех дуг неотрицательны.
Полное математическое доказательство корректности читатель может найти в [1].
Трассировка работы алгоритма Дейкстры для модельного графа (рис. 10.4) представлена в табл. 1.
Рис. 10.4. Модельный граф
Таблица 1
|
Узел пересчета |
D[1] |
D[2] |
D[3] |
D[4] |
D[5] |
D[6] |
|
|
- |
0 |
1 |
+ |
+ |
+ |
+ |
|
|
2 |
0 |
1 |
6 |
3 |
8 |
||
|
4 |
0 |
1 |
4 |
3 |
7 |
8 |
|
|
3 |
0 |
1 |
4 |
3 |
7 |
5 |
|
|
6 |
0 |
1 |
4 |
3 |
6 |
5 |
Вопрос. Всегда ли можно воспользоваться алгоритмом Дейкстры для неориентированного графа с неотрицательными весами ребер?
Ответ. Да, всегда.
10.3 Пути в бесконтурном графе
Для бесконтурного графа с произвольными весами дуг задача нахождения кратчайшего пути может быть решена за О(m) шагов. Рассмотрим модельный бесконтурный граф (рис. 10.5).
Рис. 10.5. Модельный граф
Любой бесконтурный граф обладает следующим свойством: его вершины можно перенумеровать так, что любая дуга будет идти от вершины с меньшим номером к вершине с большим номером.
Такую нумерацию будем называть правильной. Для нашего модельного графа пример возможной правильной нумерации приведен на рис. 10.6.
Рис. 10.6. Правильная нумерация
Доказательством этого свойства будет служить алгоритм правильной нумерации.
Алгоритм основывается на следующем простом факте: в бесконтурном графе существует хотя бы одна вершина, в которую не заходит ни одна дуга (иначе бы в графе существовал контур).
Все такие вершины соберем в стек. Затем
1) вытолкнем из стека произвольную вершину;
2) присвоим ей номер 1;
3) удалим ее из графа вместе со всеми выходящими из нее дугами.
После операции удаления дуг могут появиться новые вершины, в которые не заходит ни одна дуга. Эти вершины помещаются в стек, затем из стека выталкивается произвольная вершина, ей присваивается следующий номер и т.д.
Понятно, что в результате получится правильная нумерация, так как любая вершина u получает номер в тот момент, когда оставшиеся еще незанумерованные вершины v (позже они получат большие номера) либо не соединены дугами с u, либо дуга идет в направлении (u>v).
Не так очевидно, почему все вершины получат номера:
если из стека удалили последнюю вершину, а в графе, получившемся после удаления этой вершины и выходящих из нее дуг, все вершины имеют заходящие в них дуги, то они уже никогда не попадут в стек и никогда не получат номера.
Дело в том, что при удалении из бесконтурного графа вершин и дуг всегда получается бесконтурный граф, а в нем существует хотя бы одна вершина без заходящих в нее дуг. Поэтому каждая вершина обязательно попадет в стек и получит соответствующий номер.
Поскольку из стека выталкивается произвольная вершина, то принцип стека не является обязательным и выбран только для удобства.
ЛГОРИТМ {Правильная нумерация}
анные: Бесконтурный орграф G=<V,E>, заданный списками инцидентности SLED[v], v V.
езультаты: Для каждой вершины v новый номер NN[v] такой, что номера NN[v] являются правильной нумерацией графа G.
1 begin
{INP[v] - число дуг, заходящих в вершину v}
2 for vV do INP[v]:= 0;
3 for uV do
4 for vSLED[u] do
{находим все вершины v, для которых (u>v)}
5 INP[v]:= INP[v]+1;
6 СТЕК:= 0;
7 for vV do
8 if INP[v]=0 then СТЕК v;
9 num:= 0; {текущий номер}
10 while СТЕК <> 0 do
11 begin
12 u СТЕК;
13 num:= num+1;
14 NN[u]:= num;
15 for vSLED[u] do
16 begin
17 INP[v]:= INP[v]-1;
18 if INP[v]=0 then СТЕК v;
19 end;
20 end;
21 end.
Все дуги графа анализируются два раза: в цикле 3-5 для подсчета числа заходящих дуг INP[v], в цикле 10-20, где удаление дуг из графа заменено уменьшением чисел INP[v].
Таким образом, вычислительная сложность алгоритма пропорциональна числу дуг, т.е. равна О(m) шагов.
Теперь можно считать, что у нас имеется бесконтурный граф с правильной нумерацией вершин, и вершина источника имеет номер 1.
Так как все дуги идут из вершины с меньшим номером в вершину с большим номером, то промежуточные вершины на пути от 1 до j будут иметь номера, меньшие j. Поэтому для нахождения кратчайшего расстояния D[j] нужно знать только D[2],…,D[j-1]. Идея алгоритма следующая: зная D[1] (оно равно 0), вычислить D[2]; зная D[1] и D[2], вычислить D[3] и т.д.
ЛГОРИТМ {Расстояния в бесконтурном графе}
анные: Орграф G=<V,E> с правильной нумерацией, заданный списками PRED[v], матрица весов A[u,v], u,vV.
езультаты: Расстояния D[v] от источника 1 до всех остальных v V.
1 begin
2 D[1]:= 0;
3 for j:=2 to n do D[j]:= +;
4 for j:=2 to n do
5 for iPRED[j] do
6 D[j]:= min(D[j], D[i]+A[i,j]);
7 end.
В цикле 4-6 каждая дуга анализируется ровно один раз, поэтому вычислительная сложность алгоритма равна О(m) шагов.
Бесконтурный граф может служить математической моделью для задач управления выполнением проектов. Дуги графа соответствуют элементарным задачам, составляющим проект, веса дуг - времени, необходимому для выполнения элементарной задачи. Вершина s соответствует началу выполнения проекта, вершина t - его завершению. Для любых двух дуг (u>v) и (v>p) предполагается, что задача (u>v) должна быть закончена до начала выполнения задачи (v>p). Самый длинный путь от s до t требует времени, минимально необходимого для выполнения всего проекта.
Вопрос. Каким образом можно воспользоваться процедурой поиска кратчайшего пути для нахождения самого длинного пути?
Ответ. Изменить веса дуг на противоположные. Граф бесконтурный, поэтому контуры отрицательного веса в нем не появятся.
10.4 Алгоритм Флойда
Для решения задачи о кратчайших расстояниях между всеми парами вершин можно воспользоваться алгоритмом Форда -Беллмана, применив его n раз к каждой из вершин. Однако существует более эффективный алгоритм, который решает ту же задачу за О(n3) шагов.
Идея алгоритма следующая: будем искать кратчайшие расстояния D[i,j], постепенно увеличивая количество промежуточных вершин в пути от i до j. За начальные приближения возьмем пути от i до j без промежуточных вершин, т.е. веса ребер A[i,j].
Пусть уже известны длины D[i,j] самых коротких путей между всеми парами вершин, имеющих промежуточные вершины из множества 1...k-1. Добавим теперь к множеству промежуточных вершин вершину k. Путь от i до j будет складываться из пути от i до k и пути от k до j (рис. 10.7).
Рис. 10.7. Добавление промежуточной вершины
Так как наши пути не могут содержать повторяющихся вершин (иначе бы они не были кратчайшими), то пути от i до k и от k до j среди промежуточных вершин могут иметь только вершины из множества 1...k-1. Длины таких путей нам известны по предположению, поэтому длина пути от i до j, проходящего через k, сложится как сумма D[i,k]+D[k,j]. Остается сравнить старое значение D[i,j] с этой суммой и в качестве окончательного значения выбрать минимальное. Алгоритм заканчивает работу, когда промежуточными вершинами могут быть все вершины графа.
ЛГОРИТМ Флойда
анные: Орграф G=<V,E>, матрица весов A[u,v], u,vV.
езультаты: Расстояния DD[i,j] между всеми парами вершин i, j V.
1 begin
2 for i:=1 to n do
3 for j:=1 to n do DD[i,j]:= A[i,j];
4 for i:=1 to n do DD[i,i]:= 0;
5 for k:=1 to n do
6 for i:=1 to n do
7 for j:=1 to n do
8 DD[i,j]:= min(DD[i,j], DD[i,k]+DD[k,j]);
9 end.
Очевидно, что тройной цикл дает вычислительную сложность О(n3).
Вопрос. Измените алгоритм печати пути исходя из того, что имеется двумерный массив расстояний DD[i,j].
Ответ. Чтобы найти путь от s до t в процедуру печати пути вместо одномерного массива D расстояний нужно передавать s-ю строку двумерного массива DD.
10.5 Кратчайшие пути с фиксированными платежами
Все задачи о нахождении кратчайшего пути между двумя фиксированными вершинами исходили из следующего предположения: если кратчайший путь от s до t проходит через вершину k, то его отрезок от s до k будет кратчайшим путем от s до k и отрезок от k до t будет кратчайшим путем от k до t. Существует класс задач, для которых это не так. Это задачи с фиксированными платежами. Подобные задачи возникают в том случае, если за прохождение вершины сети взимается плата. Решаются такие задачи довольно сложно, но есть один класс транспортных задач, которые сводятся к уже рассмотренным нами задачам.
ЗАДАЧА О ШТРАФАХ ЗА ПОВОРОТЫ
УСЛОВИЕ. Имеется сеть улиц с односторонним или двусторонним движением. В качестве модельного графа рассмотрим сеть улиц с односторонним движением (рис. 10.8). Дугам приписаны неотрицательные числа, представляющие собой плату или время проезда. При выполнении поворота вводится некая фиксированная плата - задержка или штраф (неотрицательное число). Этот штраф зависит от направления движения при въезде и выезде. За выполнение запрещенного поворота взимается бесконечно большой штраф. Для для модельного графа будем считать, что за выполнение каждого поворота взимается штраф, равный 3.
ВОПРОС. Найти минимальный путь из s=1 в t=8.
ТЕОРЕМА
В сети со штрафами за повороты кратчайший путь из s в t, проходящий через k, не обязан содержать кратчайшие пути от s до k и от k до t.
Для модельного примера:
1-2-3-4-8 - кратчайший путь со стоимостью 15.
1-2-3-4 - путь со стоимостью 11.
1-2-6-5-4 - кратчайший путь со стоимостью 10.
Рис. 10.8. Модельный граф
Мы уже умеем находить кратчайшие пути в задачах, где стоимости приписаны только дугам. Следовательно, по исходной сети нужно построить новую фиктивную сеть, где бы штрафы за повороты включились бы в стоимость дуг. Затем в фиктивной сети найти кратчайший путь и по нему восстановить кратчайший путь в исходной сети.
ЛГОРИТМ {Кратчайший путь со штрафами за повороты}
Шаг 1
Ввести фиктивный источник s0 и соединить его дугой с источником s. Ввести фиктивный сток t0 и соединить его дугой со стоком t. Стоимости фиктивных дуг положить равными 0 и считать, что повороты из фиктивных вершин никогда не выполняются.
Шаг 2
Каждой i-й дуге расширенной сети, полученной на шаге 1, приписать имя Li. Если исходная сеть содержала m дуг, то дугам будут приписаны имена L0,L1,…,Lm+1 (рис. 10.9).
Рис. 10.9. Нумерация дуг
Шаг 3
Построение фиктивной сети (рис. 10.10).
Каждой дуге расширенной сети будет соответствовать вершина фиктивной. Две вершины фиктивной сети Li и Lj соединены дугой только в том случае, если в исходной сети конец дуги Li был бы началом дуги Lj. Стоимость такой дуги определяется по следующей формуле:
A(Li)+P(Li,Lj),где A(Li) - стоимость дуги Li,
P(Li,Lj) - штраф за выполнение поворота.
Рис. 10.10. Фиктивная сеть
Стоимости дуг фиктивной сети (рис.10.10):
|
L0-L1 |
L1-L2 |
L1-L8 |
L8-L7 |
L2-L3 |
L3-L9 |
L9-L6 |
L3-L4 |
L4-L5 |
L5-L10 |
L6-L10 |
L7-L6 |
|
|
0 |
1 |
4 |
5 |
3 |
4 |
5 |
1 |
9 |
3 |
4 |
2 |
Вопрос 1. Почему стоимость дуги L5>L10 равна 3, а не 6 (стоимость дуги + штраф за поворот)?
Шаг 4
Используя алгоритм Дейкстры, определить в фиктивной сети кратчайший путь.
Шаг 5
По кратчайшему пути в фиктивной сети восстановить путь в исходной: вершина фиктивной сети>дуга исходной>начало дуги.
Возникает вопрос, каким образом, зная две дуги, определить плату за поворот. В нашей задаче улицы имеют только два направления: горизонтальное и вертикальное. Будем хранить информацию о направлении каждой дуги в двумерном массиве BIN. Если BIN[i,j]=0, то дуга (i>j) имеет горизонтальное направление, если 1, то вертикальное. Рассмотрим сумму BIN[i,j] + BIN[j,k], производя сложение по mod 2. Если поворот происходит, то эта сумма равна 0+1 или 1+0, т.е. 1. Если поворот не происходит, то эта сумма равна 0+0 или 1+1, т.е. 0.
Вопрос 2. Как хранить информацию о поворотах в случае двустороннего движения?
Подсчитаем вычислительную сложность алгоритма.
Построение фиктивной сети можно выполнить за O(n2) шагов. Если соответствие дуг исходной сети вершинам фиктивной записать в специальный массив размерности 2(m+2), то восстановление пути пропорционально его длине, т.е. O(n). Вычислительная сложность алгоритма Дейкстры - O(n2). Окончательно, вычислительная сложность равна O(n2).
Ответ 1. В фиктивную вершину поворот не производится.
Ответ 2. Кодировать возможные направления числами: 0, 1, 2, 3.
10.6 Первые K кратчайших путей
При решении практических задач часто бывает недостаточно знать один самый короткий путь. Будем искать первые K кратчайших путей между парой фиксированных вершин s и t, расположенных в порядке возрастания длин и не содержащих контуров. Граф, как обычно, не должен содержать контуры отрицательного веса.
Вопрос. В каком случае первые K кратчайших путей могут быть найдены уже рассмотренными нами методами?
Основная идея алгоритма - поиск отклонений от уже найденных кратчайших путей.
Пусть мы уже нашли первые j путей (j<K). Обозначим их P1, P2,…, Pj. Найдем j+1 кратчайший путь. Рассмотрим последний найденный путь Pj = <s, , …, , t>.
Зафиксируем какую-нибудь вершину этого пути, не равную t. Пусть это будет i-я вершина (вершина s имеет номер 1). Будем искать отклонение в этой вершине. устроено так: от s до оно совпадает с Pj, затем от до t идет по кратчайшему пути с учетом некоторых запретов (рис. 10.11).
Рис. 10.11. Общий начальный участок
Запреты нужны для того, чтобы, во-первых, не сгенерировать путь, содержащий цикл; во-вторых, не сгенерировать уже найденный путь. Для этого:
1. Запретим использовать вершины s, , …, при поиске кратчайшего пути от до t.
2. Сравним все уже найденные пути P1, P2, …, Pj-1 с путем Pj. Выберем из них те, у которых начальный участок из i вершин <s, , …, > совпадает с начальным участком j-го пути <s, ,… , >. Чтобы не сгенерировать в качестве отклонения один из этих путей, запретим использовать дуги > в каждом из этих путей. Для этого в матрицу стоимостей A для всех таких дуг запишем A[,]= +. Также запретим использование дуги >: A[,]= +.
С учетом этих запретов можно найти отклонение , найдя кратчайший путь от до t алгоритмом Форда - Беллмана или Дейкстры (если в графе все дуги имеют неотрицательные стоимости). Таким образом будет найдено отклонение от пути Pj в i-й вершине.
Уже найденные кратчайшие пути будем хранить в окончательном списке L0, отклонения от кратчайших путей - в рабочем списке L. Поместим в L отклонения от кратчайшего пути Pj во всех вершинах. Минимальный путь из списка L переместим в список L0. Этот путь и будет j+1-м кратчайшим путем.
АЛГОРИТМ Йена
Шаг 1
Положить j=1. С помощью алгоритма Форда-Беллмана или Дейкстры найти кратчайший путь от s до t и поместить его в L0.
Шаг 2
Для всех вершин (кроме последней)j-го кратчайшего пути найти отклонения и поместить их в список L. Для этого выполнить шаги 3-5. Положить i=1.
Шаг 3
Наложить запрет на использование вершин s, Проверить все пути из списков L0 и L и выбрать пути с начальным участком, равным s, Для всех таких путей наложить запрет на использование ребра Для этого в матрицу весов записать
Шаг 4
С помощью алгоритма Форда - Беллмана или Дейкстры найти кратчайший путь от до t. Добавить к нему начальный участок s, Полученный путь поместить в список L.
Шаг 5
Восстановить матрицу весов A и допустимость вершин s, Положить i=i+1. Если не равна t, то переход к шагу 3; иначе - переход к шагу 6.
Шаг 6
Все отклонения от j-го пути уже помещены в список L. Положить j=j+1. Если L пуст, то останов; иначе - найти в L минимальный путь и перенести его в список L0. Если j=K, то останов; иначе - переход к шагу 2.
Подсчитаем вычислительную сложность алгоритма Йена и оценим размерность рабочих списков L0 и L.
Для каждого из первых K-1 путей ищем отклонения во всех вершинах. Вершин в пути не более n, поиск отклонения для одной вершины O(n3) или O(n2). Окончательно, вычислительная сложность равна O(Kn4) или O(Kn3) для неотрицательных весов.
Длина каждого пути не превосходит n (пути не содержат контуров). Количество путей в списке L0 не превосходит K; количество путей в списке L не превосходит числа отклонений (во всех вершинах, кроме последней) для K-1 пути, т.е. (K-1)(n-1).
Пути можно хранить в виде массивов, но наиболее экономными способами являются динамическая структура «связанный список» для пути и «списки инцидентности» - для списков L0 и L.
Ответ. Если в графе имеется не менее K различных путей одной и той же минимальной длины.
ПРИЛОЖЕНИЕ
СПИСОК NP - ПОЛНЫХ ЗАДАЧ
анный список NP-полных задач хоть и не претендует на полноту, но может дать некоторое представление о подобных задачах, возникающих в различных областях математики и информатики.
аждая из таких задач допускает две возможных постановки:
1) задача оптимизации;
2) задача распознавания.
качестве примера рассмотрим задачу о коммивояжере.
птимизационная постановка выглядит так:
СЛОВИЕ. Заданы конечное множество C городов, целые положительные расстояния d(c1,c2) для каждой пары городов c1, c2.
ОПРОС ОПТИМИЗАЦИИ. Найти маршрут минимальной длины, проходящий через все города и возвращающийся в исходный пункт.
тобы получить теперь задачу распознавания, введем дополнительный параметр - числовую границу B.
ОПРОС РАСПОЗНАВАНИЯ. уществует ли маршрут, проходящий через все города, длина которого не превосходит B, где B - целое положительное число? (сли решается задача на максимум, то условие «не превосходит B» заменяется условием «не меньше B».)
радиционно к NP-полным задачам относятся задачи распознавания, однако соответствующие им задачи оптимизации эквивалентны им по сложности, поэтому при формулировке задач можно использовать любую постановку.
1. РАСКРАШИВАЕМОСТЬ ГРАФА (ХРОМАТИЧЕСКОЕ ЧИСЛО)
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|, где |V| - число вершин графа.
ВОПРОС. Верно ли, что граф K-раскрашиваем? (Граф называется K-раскрашиваемым, если его вершины можно раскрасить в K цветов так, чтобы любые две соседние вершины были окрашены в различные цвета).
2. КЛИКА
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Верно ли, что граф G содержит клику размера не менее K?
(Существует ли подграф графа G такой, что число вершин в нем не меньше K и любые две вершины соединены ребром?)
3. ВЕРШИННОЕ ПОКРЫТИЕ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Имеется ли в графе вершинное покрытие не более чем из K элементов? (Имеется ли такое подмножество вершин V' V мощности не более K, что для любого ребра (u-v) Є V хотя бы одна из вершин u, v принадлежит V'?)
4. РАЗБИЕНИЕ
УСЛОВИЕ. Заданы конечное множество A и положительный целый вес w(a) для каждого a Є A.
ВОПРОС. Существует ли подмножество A' A такое, что суммарный вес элементов, принадлежащих A', равен суммарному весу элементов, не принадлежащих A'? (Иными словами, можно ли A разбить на два подмножества, равные по весу?)
5. РЮКЗАК
УСЛОВИЕ. Задано конечное множество A, положительные целые веса w(a), стоимости s(a) для каждого a Є A и общее ограничение на вес K.
ВОПРОС. Найти из всевозможных выборок A' A такую, чтобы суммарный вес входящих в него элементов не превосходил K, а суммарная стоимость была максимальна.
6. РЮКЗАК С КРАТНЫМ ВЫБОРОМ ЭЛЕМЕНТОВ
УСЛОВИЕ. Задано конечное множество A, положительные целые веса w(a), стоимости s(a) для каждого a Є A, общее ограничение на вес K и минимальная стоимость B.
ВОПРОС. Можно ли так сопоставить каждому элементу a Є A целое число c(a) (кратность), чтобы суммарный вес всех предметов из A с учетом кратностей не превосходил K, а суммарная стоимость тех же предметов была не меньше B?
7. УПАКОВКА В КОНТЕЙНЕРЫ
УСЛОВИЕ. Заданы конечное множество A и размеры s(a) Є [0, 1] каждого предмета.
ВОПРОС. Найти такое разбиение множества A на непересекающиеся A1, A2, …, Ak, чтобы сумма размеров предметов в каждом Ai не превосходила 1 и k было минимальным.
8. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ
УСЛОВИЕ. Заданы множество элементов данных A, целые положительные s(a) - размер каждого элемента, r(a) - время его поступления, d(a) - время его жизни, положительное целое число D - размер области памяти.
ВОПРОС. Существует ли для множества данных A допустимое распределение памяти? Иными словами, существует ли такая функция : A {1, 2, …, D}, что для каждого элемента a Є A интервал ((a), (a)+s(a)-1) - место, занимаемое им в динамической памяти, содержался бы в [1, D] и в любой фиксированный момент времени t0 интервалы для данных с r(a) t0 r(a)+d(a) не пересекались?
9. МНОЖЕСТВО ПРЕДСТАВИТЕЛЕЙ
УСЛОВИЕ. Задано семейство C подмножеств множества S, положительное целое число K.
ВОПРОС. Содержит ли S множество представителей для C, т.е. существует ли в S подмножество S' мощности не более K такое, что S' содержит, по крайней мере, один элемент из каждого множества семейства C.
10. УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ
УСЛОВИЕ. Задано конечное множество заданий T и для каждого задания t Є T целое число r(t) 0 - время готовности, целые положительные d(t) и l(t) - директивный срок и длительность.
ВОПРОС. Существует ли для T допустимое расписание, т.е. функция : T N (N - множество натуральных чисел), сопоставляющая заданию t момент начала его выполнения (t)? (Иными словами, задание t выполняется с момента времени (t) до (t)+l(t), оно не может быть начато ранее момента r(t), должно быть закончено не позднее d(t), и временной интервал выполнения одного задания не может перекрываться с интервалом другого).
11. МИНИМИЗАЦИЯ ШТРАФА ЗА НЕВЫПОЛНЕНИЕ ЗАДАНИЙ
УСЛОВИЕ. Задано конечное множество заданий T и для каждого задания t Є T целые положительные d(t) - директивный срок, l(t) - длительность и w(t) - вес, а также целое положительное число K.
ВОПРОС. Существует ли для T однопроцессорное расписание такое, что сумма взятая по тем t Є T, для которых не превосходит K? (Однопроцессорное расписание - это функция : T N (N - множество натуральных чисел), сопоставляющая заданию t момент начала его выполнения (t) такое, что задание t выполняется с момента времени (t) до (t)+l(t), оно должно быть закончено не позднее d(t), и временной интервал выполнения одного задания не может перекрываться с интервалом другого).
12. МИНИМАКСНОЕ МНОЖЕСТВО ЦЕНТРОВ
УСЛОВИЕ. Заданы граф G=<V, E> , положительный целый вес w(v) каждой вершины v Є V, положительная целая длина l(e) каждого ребра e Є E; положительное целое число K |V| и положительное рациональное число B.
ВОПРОС. Существует ли такое множество P мощности K «точек на G» (точка на G либо вершина графа, либо точка на ребре, где ребро e рассматривается как прямолинейный отрезок длины l(e)), что если d(v) - длина кратчайшего пути от вершины v до ближайшей к ней точке из P, то ?
P.S. Вариант этой задачи, в котором P - подмножество вершин, также NP-полон, но если K фиксировано или G - дерево, то разрешим за полиномиальное время.
13. МНОЖЕСТВО ЦЕНТРОВ С МИНИМАКСНОЙ СУММОЙ
УСЛОВИЕ. Заданы граф G=<V, E> , положительный целый вес w(v) каждой вершины v Є V, положительная целая длина l(e) каждого ребра e Є E; положительное целое число K |V| и положительное рациональное число B.
ВОПРОС. Существует ли такое множество P мощности K «точек на G» (точка на G либо вершина графа, либо точка на ребре, где ребро e рассматривается как прямолинейный отрезок длины l(e)), что если d(v) - длина кратчайшего пути от вершины v до ближайшей к ней точке из P, то ?
P.S. Вариант этой задачи, в котором P - подмножество вершин, также NP-полон, но если K фиксировано или G - дерево, то разрешим за полиномиальное время.
14. СКОПЛЕНИЯ
УСЛОВИЕ. Заданы конечное множество X, целые положительныерасстояния d(x,y) для каждой пары x,y элементов из X, целые положительные K и B.
ВОПРОС. Существует ли такое разбиение множества X на непересекающиеся X1, X2, …, Xk, что для всех x, y Xi d(x,y) B при 1 i k?.
15. СОСТАВЛЕНИЕ УЧЕБНОГО РАСПИСАНИЯ
УСЛОВИЕ. Заданы множество H рабочих часов, множество C преподавателей, множество T учебных дисциплин, для каждого преподавателя c дано подмножество A(c) из H, называемое «допустимыми часами преподавателя c», для каждой дисциплины t подмножество A(t) множества H, называемое «допустимыми часами дисциплины t», и для каждой пары (c,t) Є CT целое положительное число R(c,t), называемое «требуемой нагрузкой».
ВОПРОС. Существует ли учебное расписание, обслуживающее все дисциплины? Иными словами, существует ли функция f: CTH {0,1} (где f(c,t,h)=1 означает, что преподаватель c занимается дисциплиной t в момент h), удовлетворяющая следующим условиям:
1) f(c,t,h)=1 только тогда, когда h Є пересечению A(c) и A(t);
2) для каждого h Є H и c Є C существует не более одного t Є T такого, что f(c,t,h)=1;
3) для каждого h Є H и t Є T существует не более одного c Є C такого, что f(c, t, h)=1;
4) для каждой пары (c,t) Є CT существует ровно R(c,t) значений h, для которых f(c,t,h)=1.
16. МИНИМАЛЬНОЕ ПОКРЫТИЕ
УСЛОВИЕ. Задано семейство C подмножеств конечного множества S и положительное целое число K |C|.
ВОПРОС. Существует ли покрытие C' из C мощности не более K? Иными словами, существует ли в C такое подмножество C', что любой элемент из S принадлежит, по крайней мере, одному подмножеству из C'?
17. МИНИМАЛЬНЫЙ НАБОР ТЕСТОВ
УСЛОВИЕ. Задано конечное множество A возможных диагнозов, набор C подмножеств множества A, представляющий тесты, и положительное целое число J |C|.
ВОПРОС. Существует ли в C поднабор C' мощности не более J, такой, что для любой пары Ai, Aj возможных диагнозов имеется некоторый тест c Є C', содержащий ровно один из них?
18. САМЫЙ ДЛИННЫЙ ПУТЬ
УСЛОВИЕ. Заданы граф G=<V, E>, целые положительные длины l(e) для всех ребер, выделенные вершины s и t и положительное целое число B.
ВОПРОС. Существует ли в G элементарный путь из s в t, имеющий длину не менее B?
19. НЕЗАВИСИМОЕ МНОЖЕСТВО
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Существует ли в V независимое множество мощности не менее K? Иными словами, верно ли, что существует подмножество V' Є V такое, что |V'| K и никакие две вершины из V' не соединены ребром из E?
20. КУБИЧЕСКИЙ ПОДГРАФ
УСЛОВИЕ. Задан граф G=<V, E>.
ВОПРОС. Существует ли в E непустое подмножество E' такое, что в графе G'=<V, E'> любая вершина имеет степень, равную 3 или 0?
21. МИНИМАЛЬНЫЙ РАЗРЕЗ
УСЛОВИЕ. Заданы граф G=<V, E>, вес w(e) каждого ребра e Є E и положительное целое число K.
ВОПРОС. Существует ли разбиение множества V на два таких непересекающихся множества V1 и V2, что сумма весов ребер из E, соединяющих вершины из множеств V1 и V2, не превосходит K?
22. МИНИМАЛЬНЫЙ РАЗРЕЗ С ОГРАНИЧЕНИЯМИ
УСЛОВИЕ. Заданы граф G=<V, E> с двумя выделенными вершинами s и t, вес w(e) каждого ребра e Є E и положительные целые числа B и K (B |V|).
ВОПРОС. Существует ли разбиение множества V на два таких непересекающихся множества V1 и V2, что s Є V1, t Є V2, |V1| B, |V2| B и сумма весов ребер из E, соединяющих вершины из множеств V1 и V2, не превосходит K?
23. НАДЕЖНОСТЬ СЕТИ
УСЛОВИЕ. Заданы граф G=<V, E>, подмножество V' Є V, для каждого e Є E рациональное число p(e), 0 p(e) 1 - вероятность неисправности, положительное рациональное число q 1.
ВОПРОС. Верно ли, что с вероятностью, не меньшей q, любые две вершины из V соединены хотя бы одним путем, не содержащим неисправных ребер?
24. КРАТЧАЙШИЙ ПУТЬ С ОГРАНИЧЕНИЯМИ ПО ВЕСУ
УСЛОВИЕ. Заданы граф G=<V, E> с двумя выделенными вершинами s и t, целые положительные веса w(e) и длина l(e) каждого ребра e Є E и положительные целые числа B и K.
ВОПРОС. Существует ли в G элементарный путь из s в t, веса не более B и длины не более K?
25. СЕЛЬСКИЙ ПОЧТАЛЬОН
УСЛОВИЕ. Заданы граф G=<V, E>, целая положительная длина l(e) каждого ребра e Є E, E' - подмножество E и положительное целое число K.
ВОПРОС. Существует ли в G цикл, включающий каждое ребро из E' и имеющий длину не более K?
26. КИТАЙСКИЙ ПОЧТАЛЬОН
УСЛОВИЕ. Заданы смешанный граф граф G=<V, A, E>, где A - множество ориентированных ребер и E - множество неориентированных ребер; целая положительная длина l(e) каждого ребра и положительное целое число B.
ВОПРОС. Существует ли в G цикл, включающий по крайней мере один раз каждое ребро и имеющий длину не более B (ориентированные ребра должны входить в цикл только с правильной ориентацией)?
27. МИНИМАЛЬНОЕ ПО МОЩНОСТИ МАКСИМАЛЬНОЕ ПАРОСОЧЕТАНИЕ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |E|.
ВОПРОС. Существует ли в E непустое подмножество E' такое, что |E'| K и E'- максимальное паросочетание, т.е. никакие два ребра из E' не имеют общего конца, а любое ребро из множества E-E' имеет общий конец с одним из ребер множества E'?
28. СУММА ВЕСОВ
УСЛОВИЕ. Заданы конечное множество A, положительные целые веса w(a) для каждого a Є A и положительный целый вес K.
ВОПРОС. Существует ли такое подмножество A' множества A, что сумма весов его элементов равна K?
29. ДОМИНИРУЮЩЕЕ МНОЖЕСТВО
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Существует ли в V доминирующее множество мощности не более K? Иными словами, верно ли, что существует подмножество V' Є V такое, что |V'| K и для любой вершины uV-V' сущеествует такая вершина vV', что u и v соединены ребром из E?
30. РАЗБИЕНИЕ НА КЛИКИ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K? |V|.
ВОПРОС. Можно ли разбить вершины графа G на k ? K непересекающихся множеств V1,V2,…,Vk таких, что для всех i (1? i ? k) подграф, индуцированный множеством Vi, был бы полным?
31. РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ
УСЛОВИЕ. Заданы граф G=<V, E> такой, что для некоторого положительного целого число q: |V|=3q.
ВОПРОС. Можно ли разбить вершины графа G на q непересекающихся множеств V1,V2,…,Vq таких, что каждое содержит ровно 3 вершины и для всех i (1? i ? q) подграф, индуцированный множеством Vi, был бы треугольником?
32. РАЗБИЕНИЕ НА ЛЕСА
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K ? |V|.
ВОПРОС. Можно ли разбить вершины графа G на k ? K непересекающихся множеств V1,V2,…,Vk таких, что для всех i (1? i ? k) подграф, индуцированный множеством Vi, не содержит циклов?
33. МОНОХРОМАТИЧЕСКИЙ ТРЕУГОЛЬНИК
УСЛОВИЕ. Заданы граф G=<V,E>.
ВОПРОС. Можно ли разбить множество ребер E на два непересекающихся подмножества E1 и E2, таких, что ни один из графов G1=<V, E1> или G2=<V, E2> не содержит треугольника?
34. ИНДУЦИРОВАННЫЙ ПУТЬ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Существует ли в V подмножество V' такое, что |V'| K и подграф, индуцированный множеством V', является элементарным путем на |V'| вершинах?
35. ДВУДОЛЬНЫЙ ПОДГРАФ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |E|.
ВОПРОС. Существует ли в E подмножество E' мощности не менее K такое, что G'=<V, E'> - двудольный подграф?
36. СВЯЗНЫЙ ПОДГРАФ ОГРАНИЧЕННОЙ СТЕПЕНИ
УСЛОВИЕ. Заданы граф G=<V, E>, неотрицательное целое число d |V| и положительное целое число K |E|.
ВОПРОС. Существует ли в E подмножество E' мощности не менее K такое, что подграф G'=<V, E'> связен и не имеет вершин степени более d?
37. ГАМИЛЬТОНОВО ПОПОЛНЕНИЕ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K |V|.
ВОПРОС. Существует ли множество E', содержащее множество E такое, что |E'-E| K, а граф G'=<V, E'> имеет гамильтонов цикл?
38. КАРКАС ОГРАНИЧЕННОГО ДИАМЕТРА
УСЛОВИЕ. Заданы граф G=<V, E>, вес положительный целый вес w(e) каждого ребра e Є E и положительные целые числа B и D |V|.
ВОПРОС. Существует ли в графе G каркас T такой, что сумма весов ребер из T не превосходит B и в T нет элементарного пути, число ребер которого не превосходит D?
39. РАСЩЕПЛЕНИЕ МНОЖЕСТВА
УСЛОВИЕ. Задан набор C подмножеств множества S.
ВОПРОС. Существует ли такое разбиение множества S на два подмножества, что ни одно подмножество из C не содержится целиком ни в S1, ни в S2?
40. КРАТЧАЙШАЯ ОБЩАЯ НАДПОСЛЕДОВАТЕЛЬНОСТЬ
УСЛОВИЕ. Заданы конечный алфавит A, конечное множество R слов в алфавите A и положительное целое число K.
ВОПРОС. Существует ли такое слово w Є , что |w| ? K и каждое слово x Є R есть подпоследовательность слова w (т.е. w = w0x1w1x2w2…xkwk,, где wi Є , а x = x1x2…xk)?
41. ПРЯМОУГОЛЬНОЕ СЖАТИЕ КАРТИНКИ
УСЛОВИЕ. Задана (0 - 1) матрица M порядка и положительное целое число B.
ВОПРОС. Можно ли покрыть все единичные элементы матрицы M не более, чем B прямоугольниками? (Существует ли такая последовательность четверок (ai, bi, ci, di,), 1 i B, где ai bi, ci di, что для каждой пары индексов (i, j), 1 i, j n, тогда и только тогда, когда существует такое k, 1 k B, что ai i bi и ci j di?
42. МАКСИМАЛЬНОЕ ЧИСЛО ОГРАНИЧЕННЫХ НЕПЕРЕСЕКАЮЩИХСЯ ПУТЕЙ
УСЛОВИЕ. Задан граф G=<V, E> с выделенными вершинами s и t и заданы положительные целые числа B и K (B и K ? |V|).
ВОПРОС. Верно ли что в G содержится не менее B путей из s в t, попарно не имеющих общих вершин и включающих не более K ребер?
43. КАРКАС ОГРАНИЧЕННОЙ СТЕПЕНИ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K ? |V|.
ВОПРОС. Существует ли в графе G каркас, у которого степени всех вершин не превосходят K?
44. КАРКАС С МАКСИМАЛЬНЫМ ЧИСЛОМ ЛИСТОВ
УСЛОВИЕ. Заданы граф G=<V, E> и положительное целое число K ? |V|.
ВОПРОС. Существует ли в графе G каркас, у которого не менее K вершин степени 1?
45. ДЕРЕВО ШТЕЙНЕРА
УСЛОВИЕ. Заданы граф G=<V, E> , положительный целый вес w(e) каждого ребра e Є E, подмножество R вершин графа и положительное целое число B.
ВОПРОС. Существует ли в графе G дерево, содержащее все вершины из R, что сумма весов ребер этого поддерева не превосходит B?
46. МАКСИМАЛЬНОЕ ЧИСЛО ОГРАНИЧЕННЫХ НЕПЕРЕСЕКАЮЩИХСЯ ПУТЕЙ
УСЛОВИЕ. Заданы граф G=<V, E> с выделенными вершинами s и t, а также положительные целые числа J и K.
ВОПРОС. Верно ли, что в G содержится не менее J различных путей из s в t, попарно не имеющих общих вершин и включающих не более K ребер?
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
2. Алкок Д. Язык Паскаль в иллюстрациях. М.: Мир, 1988.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
5. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.
6. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
Подобные документы
Работа с массивами, их ввод и вывод, организация программ циклической структуры. Способы описания и использования массивов, алгоритмы их сортировки, сортировка выбором и вставками. Алгоритмы поиска элемента в неупорядоченном и упорядоченном массивах.
лабораторная работа [14,2 K], добавлен 03.10.2010Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.
курсовая работа [78,2 K], добавлен 24.09.2010Сущность языка программирования, идентификатора, структуры данных. Хранение информации, алгоритмы их обработки и особенности запоминающих устройств. Классификация структур данных и алгоритмов. Операции над структурами данных и технология программирования.
контрольная работа [19,6 K], добавлен 11.12.2011Обработка текстовых данных, хранящихся в файле. Задачи и алгоритмы обработки больших массивов действительных и натуральных чисел. Практические задачи по алгоритмам обработки данных. Решение задачи о пяти ферзях. Программа, которая реализует сортировку Шел
курсовая работа [29,2 K], добавлен 09.02.2011Транскрипционные факторы. Представление регуляторных элементов. Алгоритмы поиска мотивов. Скрытые Марковские модели и вспомогательные алгоритмы. Тестирование на сгенерированных и реальных данных, отличия в показателях. Сравнение с другими алгоритмами.
дипломная работа [5,0 M], добавлен 24.05.2012Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.
курсовая работа [138,3 K], добавлен 13.06.2007Линейные динамические структуры. Построение списочной структуры, состоящей из трехнаправленного и двух однонаправленных списков, связанных между собой. Дерево двоичного поиска для заданного множества целых чисел. Листинг программы на языках Си и Паскаль.
курсовая работа [451,1 K], добавлен 19.10.2013Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением .txt).
курсовая работа [2,2 M], добавлен 29.05.2013
