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

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

2020-05-14T22:50:09Z

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

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

2020-04-30T16:55:24Z

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

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

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

2020-04-30T16:49:24Z

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

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

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

2020-04-30T16:47:01Z

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

← Предыдущая версия		Версия от 16:47, 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 ~~Гамильтонов путь~~] наименьшего веса.		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 гамильтонов цикл] наименьшего веса.
			====Наивное решение====
			Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходиь.

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

2020-04-30T16:34:34Z

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

← Предыдущая версия		Версия от 16:34, 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 Гамильтонов путь] наименьшего веса ~~(простой путь, проходящий через каждую вершину ровно один раз)~~.		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 Гамильтонов путь] наименьшего веса.

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

2020-04-30T16:33:52Z

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

← Предыдущая версия		Версия от 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 Гамильтонов путь] наименьшего веса (простой путь, проходящий через каждую вершину ровно один раз).

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

2020-04-30T16:24:32Z

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

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

2020-04-30T16:23:31Z

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

← Предыдущая версия		Версия от 16:23, 30 апреля 2020
Строка 1:		Строка 1:
	== ~~Описание проблемы~~ ==		== Проблема представления подмножеств ==
	Пусть у нас есть некоторое множесьво N = {0, 1, 2, ..., n - 1}, n ≤ 30 <br><br>		Пусть у нас есть некоторое множесьво N = {0, 1, 2, ..., n - 1}, n ≤ 30 <br><br>
	Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".		Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".

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

2020-04-30T16:22:29Z

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

← Предыдущая версия		Версия от 16:22, 30 апреля 2020
Строка 12:		Строка 12:
	return (mask >> pos) & 1;		return (mask >> pos) & 1;
	}		}
	Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask.		Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответсвует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.

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

2020-04-30T16:17:31Z

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

← Предыдущая версия		Версия от 16:17, 30 апреля 2020
Строка 8:		Строка 8:
	Напрмер, если есть множество А = {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х.
	===Как работать с множествами, с помощью масок?===		===Как работать с множествами, с помощью масок?===
	Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:<br>		<p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p>
	'''bool''' elem_in_subset ('''unsigned int''' mask, '''int''' pos) {		'''bool''' elem_in_subset ('''unsigned int''' mask, '''int''' pos) {
	return (mask >> pos) & 1;		return (mask >> pos) & 1;
	}		}
	~~hkjh~~		Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask.

← Предыдущая версия		Версия от 22:50, 14 мая 2020
Строка 1:		Строка 1:
	== Проблема представления подмножеств ==		== Проблема представления подмножеств ==
	Пусть у нас есть некоторое ~~множесьво~~ N = {0, 1, 2, ..., n - 1}, n ≤ 30 <br><br>		Пусть у нас есть некоторое множество N = {0, 1, 2, ..., n - 1}, n ≤ 30 <br><br>
	Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".		Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".

Строка 6:		Строка 6:
	===Что такое битовые маски?===		===Что такое битовые маски?===
	Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br>		Подмножество будем кодировать с помощью двоичного числа, в котором на 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>		<p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p>
Строка 12:		Строка 12:
	return (mask >> pos) & 1;		return (mask >> pos) & 1;
	}		}
	Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве ~~подйдет~~ функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств ~~соответсвует~~ побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.		Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подойдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответствует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.
	==ДП на подмножествах==		==ДП на подмножествах==
	===Задача о гамильтоновом цикле===		===Задача о гамильтоновом цикле===
	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 гамильтонов цикл] наименьшего веса.		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 гамильтонов цикл] наименьшего веса.
	====Наивное решение====		====Наивное решение====
	Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно 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 ровно по одному разу.