Эта статья входит в число добротных статей и является кандидатом в хорошие
Эта статья входит в число Добротных статей

Задача о ранце

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример задачи о ранце: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной

Задача о ранце (или задача о рюкзаке) — одна из NP-трудных задач комбинаторной оптимизации. Своё название получила от задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о ранце можно столкнуться в экономике, прикладной математике, криптографии и логистике.

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

Классическая постановка задачи[править | править вики-текст]

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

Математически задача формулируется следующим образом: имеется грузов. Для каждого -го груза определён его вес и ценность , . Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью . Необходимо

максимизировать
с ограничениеми и [1].

Варианты задачи о ранце[править | править вики-текст]

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

  1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
  2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
  3. Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
  4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
  5. Мультипликативный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
  6. Многомерный рюкзак (англ. Multy-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
  7. Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определенной квадратичной формой[6].

Приложения[править | править вики-текст]

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о ранце. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса (англ.)[7][8], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem»[9], особенно в 70-90-е годы 20-го века, как теоретиками, так и практиками[2]. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список К. Мэннинга NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[10].

Наглядная интерпретация задачи о ранце привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В одной из работ по вычислительной лингвистике[11] предложена формулировка задачи автоматического реферирования текстов (англ.), частный случай которой соответствует постановке задачи о ранце.

На основе задачи о ранце был создан первый алгоритм асимметричного шифрования. Впервые идея криптографии с открытыми ключами была представлена Уитфилдом Диффи и Мартином Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference)[12][13].

Также задача о рюкзаке может служить моделью для большого числа промышленных задач[2][14]:

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

Задача о ранце в криптографии[править | править вики-текст]

В 1978 году Ральф Меркл и Мартин Хеллман разработали первый алгоритм для обобщённого шифрования с открытым ключом - криптосистему Меркла — Хеллмана, построив её на основе задачи о ранце. Они опубликовали одностадийный (англ. singly-iterated) и мультистадийный варианты (англ. multiply-iterated), а алгоритм мог быть использован только для шифрования. Но Ади Шамир адаптировал его и для использования в цифровых подписях[15].

В дальнейшем было предложено как множество модификаций криптосистемы Меркла — Хеллмана, так и совершенно новых криптосистем на основе задачи о ранце. Среди них[16]:

  1. Рюкзак Грэм — Шамира
  2. Рюкзак Гудмана — Макколи
  3. Рюкзак Накаше — Штерна
  4. Рюкзак Шора — Ривеста

Шифрование с помощью задачи о ранце[править | править вики-текст]

Сложность нахождения точного решения задачи о ранце позволяет зашифровать передаваемое сообщение как решение набора задач о ранце[15].

Определение. Рюкзачным вектором назовём упорядоченный набор из n предметов, где - вес -го предмета[17].

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

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

Пример шифрования данным алгоритмом:

Пусть задан рюкзачный вектор с длиной .

Открытый текст 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Вещи в рюкзаке 3 4 6 7 10 6 7 11
Шифротекст 3 + 4 + 6 + 7 + 10 = 30 6 + 7 = 13 0 11

Для заданного все криптосистемы есть числа, не превышающие 41, то есть суммарный вес всех предметов в рюкзачном векторе.

На практике, для шифрования необходим сверхвозрастающий рюкзак, то есть элементы упорядоченного рюкзачного вектора должны являться сверхвозрастающей последовательностью. В таком случае для каждого исходного текста существует единственный шифротекст[18]. В указанном примере рюкзак не является сверхвозрастающим — можно получить одинаковый шифротекст для векторов 100010 и 001100.

Точные методы решения[править | править вики-текст]

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

Полный перебор[править | править вики-текст]

Как и для других дискретных задач, задачу о ранце можно решить, полностью перебрав все возможные решения. Допустим, имеется предметов, которые можно класть в рюкзак. Нужно определить максимальную стоимость груза, вес которого не превышает .

Дерево полного перебора

Данный алгоритм имеет временную сложность , что позволяет его использовать лишь для небольших значений [19]. С ростом задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для четырёх предметов. Корень дерева соответствует пустому рюкзаку, в кружках показан номер предмета. Первый предмет возможно выбрать четырьмя способами, второй тремя и т. д.

После составления дерева, необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает [20].

Метод ветвей и границ[править | править вики-текст]

Дерево, упрощённое методом ветвей и границ

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

Пусть есть оптимальное решение . Попытаемся его улучшить, рассмотрев решение на другой ветви. Если на рассматриваемой в данной момент ветви решение становится хуже (с какого-то шага), чем , то прекращаем его исследование и выбираем другую ветвь дерева[21].

Пусть для предыдущего четырёхуровневого дерева есть ограничение , а вес предмета соответствует его номеру. Тогда, применяя метод ветвей и границ, можно сократить количество вариантов для перебора с 24 до 8, как показано на рисунке.

Применение метода ветвей и границ[править | править вики-текст]

Метод ветвей и границ можно изобразить следующим образом: на двумерной плоскости по оси откладывается количество предметов, по оси  — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[22].

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

Пример. Пусть вместимость рюкзака .

Сеть, иллюстрирующая наполнение рюкзака. В квадратных скобках указаны суммарная ценность на данном шаге алгоритма, оптимальное решение помечено кругом
Номер предмета Ценность Вес
1 3 5
2 5 10
3 4 6
4 2 5

На рисунке в квадратных скобках [] стоит суммарная ценность на каждом шаге алгоритма. Видно, что для оптимального решения она равна 7.

Методы динамического программирования[править | править вики-текст]

Задача о неограниченном рюкзаке[править | править вики-текст]

При дополнительном ограничении на веса предметов, задачу о ранце можно решить за псевдополиномиальное время методами динамического программирования.

Пусть вес каждого предмета является целым неотрицательным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех , где - заданная грузоподъемность. Определим как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью .

Для нетрудно записать рекуррентные формулы:

  • [23],

где - ценность и вес -го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения , начиная с и до [23]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

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

Задача о рюкзаке 0-1[править | править вики-текст]

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

Рекуррентные соотношения:

  • , если
  • , если

Вычисляя , можно найти точное решение. Если массив помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[23].

 1 // Ввод:
 2 // Ценности предметов (загруженные в массив v)
 3 // Веса предметов (загруженные в массив w)
 4 // Количество предметов (n)
 5 // Грузоподъемность (W)
 6 
 7 for j from 0 to W do:
 8     m[0, j] := 0
 9 
10 for i from 1 to n do:
11     for j from 0 to W do:
12         if w[i] > j then:
13             m[i, j] := m[i-1, j]
14         else:
15             m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Динамическое программирование над ценностями предметов[править | править вики-текст]

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

После этого решим функциональное уравнение динамического программирования:

,

с начальными условиями:

[25]

Приближенные методы решения[править | править вики-текст]

Как и для большинства NP-полных задач, не всегда необходимо получать точное решение, так как решения, близкие к оптимальным, могут применяться в прикладных задачах.

Жадный алгоритм[править | править вики-текст]

Согласно жадному алгоритму предметы сортируются по убыванию стоимости единицы веса каждого. В рюкзак последовательно складываются самые дорогие за единицу веса предметы из тех, что помещаются внутри[26].

Сложность сортировки предметов составляет . Далее происходит решение о помещении каждого предмета в рюкзак за [26]. Итоговая сложность .

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

i вес цена цена/вес
1 15 60 4
2 30 90 3
3 50 100 2

Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190.

Впервые жадный алгоритм был предложен Джорджом Даницгом[27] для решения задачи о неограниченном рюкзаке. Тем не менее, решение жадным алгоритмом проблемы рюкзака 0-1 может быть далеко от оптимального, как показано выше.

Если бы количество каждого предмета было бы неограниченно, то оптимальным решением было бы взять 5 первых предметов с общей ценностью 300. Такое же решение даёт жадный алгоритм.

В худшем случае, ценность в решении, полученном жадным алгоритмом, может составлять только 50% от ценности в оптимальном решении[26].

Приближенная схема полностью полиномиального времени[править | править вики-текст]

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

Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом[25]:

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

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

Генетические алгоритмы[править | править вики-текст]

Пример эволюции популяции при использовании генетического алгоритма. Объектами являются строчки, кодирующие в бинарном виде какие объекты кладутся в рюкзак. Например, строчка (0,1,0,1,0) соответствует выбору коробок весами 12 кг и 7 кг .

Как и для других NP-трудных задач оптимизации, для решения задачи о ранце применяются генетические алгоритмы. Они не гарантируют нахождения оптимального решения за полиномиальное время и не дают оценку близости решения к оптимальному, но обладают хорошими временными показателями, позволяя найти "достаточно хорошее" решение быстрее других известных детерминированных или эвристических методов.[29]

Каждая особь(генотип) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства, информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец[30].

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

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

Решение задачи о сумме подмножеств[править | править вики-текст]

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть - грузоподъемность рюкзака, - вес -го предмета, а его стоимость . Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор . В качестве функции приспособленности следует использовать близость суммарного веса предметов к , с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем )[30].

Определим формально функцию приспособленности . Пусть - сумма весов всех предметов. Тогда - максимально возможное отклонение веса предметов в рюкзаке от .

Пусть - суммарный вес предметов для данного вектора. Тогда положим:

[30]

Пользуясь общим алгоритмом, можно найти приближенное решение:

  1. Создать случайный набор особей - популяцию.
  2. Подсчитать функцию приспособления для каждой особи.
  3. Оставить только наиболее приспособленных особей (естественный отбор).
  4. Произвести скрещивания особей.
  5. Подвергнуть потомков мутации.
  6. Продолжить со второго шага.

Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций[30].

Нелинейная задача о ранце[править | править вики-текст]

В общем виде, нелинейную задачу о ранце можно сформулировать следующим образом:

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

,

при заданном ограничении:

.

Функции предполагаются непрерывными и дифференцируемыми на . - целочисленная константа, множество непусто[31].

В случае линейных функций , задача сводится к одной из классических постановок, в зависимости от множества :

  • - рюкзак 0-1
  • - неограниченный рюкзак
  • - ограниченный рюкзак

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Silvano, 1990, p. 1.
  2. 1 2 3 Silvano, 1990, p. 2.
  3. 1 2 Kellerer, Pferschy, Pisinger, 2003, p. 127.
  4. 1 2 Kellerer, Pferschy, Pisinger, 2003, p. 147.
  5. Silvano, 1990, p. 157.
  6. G. Gallo, P. L. Hammer, B. Simeone Quadratic knapsack problems (англ.) // Mathematical Programming Studies. — 2009. — 24 февраль (vol. 12). — P. 132-149. — ISSN 0303-3929.
  7. G. B. Mathews On the partition of numbers (англ.). — 1897. — P. 486-490.
  8. Kellerer, Pferschy, Pisinger, 2003, p. 3.
  9. Kellerer, Pferschy, Pisinger, 2003, p. 9.
  10. Р. Карп Reducibility Among Combinatorial Problems (англ.). — 1972.
  11. Riedhammer et al, 2008, pp. 2436.
  12. Шнаер, 2002, p. 19.2.
  13. Габидулин, Кшевецкий, Колыбельников, 2011.
  14. Бурков, 1974, p. 217.
  15. 1 2 Шнаер, 2002, p. 19.1.
  16. Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future (рус.). — 2001.
  17. Саломаа, 1995, p. 103.
  18. Саломаа, 1995, p. 104.
  19. Окулов, 2007, pp. 92-93.
  20. Окулов, 2007, pp. 101-105.
  21. Бурков, 1974, p. 225.
  22. 1 2 Новиков, 2001, p. 12.
  23. 1 2 3 Романовский И.В. Алгоритмы решения экстремальных задач. — Наука, 1977. — С. 252-259. — 352 с.
  24. Стивен С. Скиена. Алгоритмы. Руководство по разработке. — 2-e. — СПб: БХВ-Петербург, 2011. — С. 448-451. — 720 с. — ISBN 978-5-9775-0560-4.
  25. 1 2 Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems - Springer.
  26. 1 2 3 Martello S., Toth P. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons Ltd., 1990. — С. 29,50. — 296 с. — ISBN 0-471-92420-2.
  27. George B. Dantzig Discrete-Variable Extremum Problems // Operations Research. — 1957-04-01. — Т. 5, вып. 2. — С. 266–288. — ISSN 0030-364X. — DOI:10.1287/opre.5.2.266.
  28. Ariel Kulik, Hadas Shachnai There is no EPTAS for two-dimensional knapsack // Information Processing Letters. — 2010-07-31. — Т. 110, вып. 16. — С. 707–710. — DOI:10.1016/j.ipl.2010.05.031.
  29. Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Применение генетических алгоритмов к решению задач дискретной оптимизации. — 2007. — Нижний Новгород.
  30. 1 2 3 4 5 С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития (рус.). — С. 38.
  31. 1 2 Kurt M Bretthauer, Bala Shetty The nonlinear knapsack problem – algorithms and applications // European Journal of Operational Research. — 2002-05-01. — Т. 138, вып. 3. — С. 459–472. — DOI:10.1016/S0377-2217(01)00179-5.

Литература[править | править вики-текст]

на русском языке
  1. Левитин А. В. Алгоритмы. Введение в разработку и анализ М.: Вильямс, 2006. — С. 160—163. — 576 с. — ISBN 978-5-8459-0987-9
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456-458. — ISBN 0-07-013151-1.
  3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
  4. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — 1-ое. — Тбилиси: ВЦ АН ГССР, 1974. — 232 с.
  5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
  6. С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
  7. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102-150. — ISBN 5–03–001991–X.
  9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
  10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
на английском языке
  1. Silvano Martelo, Paolo Toth. Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2.
  2. Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — Springer-Verlag, 2003. — 548 с. — ISBN 3540402861.
  3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.

Ссылки[править | править вики-текст]