ДП на подмножествах - История изменений

Algocourselecturenotes: Исправил опечатки

2020-05-14T22:50:09Z

Исправил опечатки

Algocourselecturenotes: /* Оптимизация наивного решения с помощью ДП */

2020-04-30T16:55:24Z

‎Оптимизация наивного решения с помощью ДП

Algocourselecturenotes: /* Задача о гамильтоновом цикле */

2020-04-30T16:49:24Z

‎Задача о гамильтоновом цикле

Algocourselecturenotes: /* Задача о гамильтоновом цикле */

2020-04-30T16:47:01Z

‎Задача о гамильтоновом цикле

Algocourselecturenotes: /* Задача о гамильтоновом цикле */

2020-04-30T16:34:34Z

‎Задача о гамильтоновом цикле

Algocourselecturenotes: /* Задача о гамильтоновом цикле */

2020-04-30T16:33:52Z

‎Задача о гамильтоновом цикле

Algocourselecturenotes в 16:24, 30 апреля 2020

2020-04-30T16:24:32Z

Algocourselecturenotes: /* Описание проблемы */

2020-04-30T16:23:31Z

‎Описание проблемы

Algocourselecturenotes: /* Как работать с множествами, с помощью масок? */

2020-04-30T16:22:29Z

‎Как работать с множествами, с помощью масок?

Algocourselecturenotes: /* Как работать с множествами, с помощью масок? */

2020-04-30T16:17:31Z

‎Как работать с множествами, с помощью масок?

@@ Строка 1: / Строка 1: @@
 == Проблема представления подмножеств ==
-Пусть у нас есть некоторое множесьво N = {0, 1, 2, ..., n - 1}, n &le; 30 <br><br>
+Пусть у нас есть некоторое множество N = {0, 1, 2, ..., n - 1}, n &le; 30 <br><br>
 Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".
@@ Строка 6: / Строка 6: @@
 ===Что такое битовые маски?===
 Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br>
-Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х.
+Например, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х.
 ===Как работать с множествами, с помощью масок?===
 <p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p>
@@ Строка 12: / Строка 12: @@
          return (mask >> pos) & 1;
+     }
-Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответсвует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.
+Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подойдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответствует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.
 ==ДП на подмножествах==
 ===Задача о гамильтоновом цикле===
-) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F гамильтонов цикл] наименьшего веса.
+) Пусть есть неориентированный взвешенный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F гамильтонов цикл] наименьшего веса.
 ====Наивное решение====
-Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходиь.
+Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходить.
 ====Оптимизация наивного решения с помощью ДП====
-Заведем массив <code>dp</code> такой, что <code>dp[mask][v]</code> - миннимальная длина пути из 0-й вершины в вершину v, проходящий только по вершинам из множества mask ровно по одному разу.
+Заведем массив <code>dp</code> такой, что <code>dp[mask][v]</code> - минимальная длина пути из 0-й вершины в вершину v, проходящий только по вершинам из множества mask ровно по одному разу.

@@ Строка 19: / Строка 19: @@
 Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходиь.
 ====Оптимизация наивного решения с помощью ДП====
-    Заведем массив dp.
+Заведем массив <code>dp</code> такой, что <code>dp[mask][v]</code> - миннимальная длина пути из 0-й вершины в вершину v, проходящий только по вершинам из множества mask ровно по одному разу.

← Предыдущая		Версия 16:49, 30 апреля 2020
Строка 18:		Строка 18:
	====Наивное решение====		====Наивное решение====
	Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходиь.		Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходиь.
		+	====Оптимизация наивного решения с помощью ДП====
		+	Заведем массив dp.

@@ Строка 15: / Строка 15: @@
 ==ДП на подмножествах==
 ===Задача о гамильтоновом цикле===
-) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F Гамильтонов путь] наименьшего веса.
+) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F гамильтонов цикл] наименьшего веса.

@@ Строка 15: / Строка 15: @@
 ==ДП на подмножествах==
 ===Задача о гамильтоновом цикле===
-) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F Гамильтонов путь] наименьшего веса (простой путь, проходящий через каждую вершину ровно один раз).
+) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F Гамильтонов путь] наименьшего веса.

← Предыдущая		Версия 16:33, 30 апреля 2020
Строка 15:		Строка 15:
	==ДП на подмножествах==		==ДП на подмножествах==
	===Задача о гамильтоновом цикле===		===Задача о гамильтоновом цикле===
		+	1) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F Гамильтонов путь] наименьшего веса (простой путь, проходящий через каждую вершину ровно один раз).

← Предыдущая		Версия 16:24, 30 апреля 2020
Строка 13:		Строка 13:
	}		}
	Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответсвует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.		Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответсвует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.
		+	==ДП на подмножествах==
		+	===Задача о гамильтоновом цикле===