Алгоритм (7): графическое динамическое программирование

Java алгоритм

Введение в алгоритмы

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

Отличие от жадного алгоритма

  • Оба делят большую проблему на более мелкие подзадачи.

  • Суть динамического программирования заключается в методе «разделяй и властвуй» и решении избыточности.Решение каждой подзадачи сохраняется, чтобы можно было напрямую сослаться на нее, когда она встретится позже, чтобы избежать повторных вычислений.Одна из Отличительной особенностью динамического программирования является то, что будет большое количество подзадач.Повторяю, вы можете напрямую использовать предыдущее решение

  • Каждая операция жадного алгоритма напрямую влияет на результат (объем задачи становится все меньше и меньше), а динамическое программирование — нет. Жадный алгоритм делает выбор для решения каждой подзадачи и не может вернуться назад, динамическое программирование выбирает текущую по предыдущему результату выбора и имеет функцию отката (например, задача о рюкзаке, чем меньше рюкзак в такая же колонка той же мощности, тем больше Последнее является оптимальным решением, переворачивающим предыдущий выбор). Динамическое программирование в основном используется в двумерных или трехмерных задачах, тогда как жадное программирование обычно используется в одномерных задачах.

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

  • Динамическое программирование похоже на поиск или заполнение форм.Для задач с оптимальными подструктурами можно использовать динамическое программирование, в противном случае можно использовать жадные алгоритмы.

кейс

Случай здесь из книги "Иллюстрированный алгоритм"

Дело номер один

Проблема с рюкзаком: есть рюкзак вместимостью 4 фунта со следующими предметами.

вещь масса цена
Гитара (соль) 1 1500
Аудио(С) 4 3000
Компьютер (L) 3 2000

Требуемая цель - иметь максимальную общую стоимость загруженного рюкзака и не превышать вес.

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

Решение подобных задач можно разложить на решаемые небольшие задачи, предполагая, что имеются рюкзаки различной вместимости 1, 2, 3 и 4 (правило распределения вместимости — целое число, кратное минимальному весу):

Например:

вещь 1 фунт 2 фунта 3 фунта 4 фунта
Гитара (соль)
Аудио(С)
Компьютер (L)

Для первой строки (i=1) в настоящее время можно выбрать только гитару, поэтому

вещь 1 фунт 2 фунта 3 фунта 4 фунта
Гитара (соль) 1500(G) 1500(G) 1500(G) 1500(G)
Аудио(С)
Компьютер (L)

Во втором ряду (i=2) в настоящее время есть выбор между гитарами и динамиками, поэтому

вещь 1 фунт 2 фунта 3 фунта 4 фунта
Гитара (соль) 1500(G) 1500(G) 1500(G) 1500(G)
Аудио(С) 1500(G) 1500(G) 1500(G) 3000(S)
Компьютер (L)

Для третьего ряда (i=3) на данный момент есть гитары, колонки и компьютеры на выбор, поэтому

вещь 1 фунт 2 фунта 3 фунта 4 фунта
Гитара (соль) 1500(G) 1500(G) 1500(G) 1500(G)
Аудио(С) 1500(G) 1500(G) 1500(G) 3000(S)
Компьютер (L) 1500(G) 1500(G) 2000(L) 3500(L+G)

Все вышеперечисленное укладывается в формулу:

F(i,j) = max{ F(i-1,j), W(i) + F(i,j = j-V(i))} 
即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的最大价值}

F(i,j)的代表 i行j列可以获得的最大价值，W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量,
F(i,j = j-V(i)) : 假设

Например, F(3,4) = max{ F(2,4), F(3,3) + 2000 } = max { 3000, 1500 + 2000} = 3500, временная сложность этой задачи O(V *N) , V-битная вместимость рюкзака, N - общее количество предметов, то есть общее количество ячеек сетки.

Вышеупомянутое пространство рюкзака обычно делится в соответствии с целым числом, кратным размеру, занимаемому самым маленьким предметом (вот гитара, которая занимает 1 фунт).1,1,5,2,2,5,3,3,5,4)

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

Используя приведенную выше формулу, когда вес рюкзака составляет 4 фунта, максимальное значение, которое можно загрузить, по-прежнему составляет 3500:

вещь 1 фунт 2 фунта 3 фунта 4 фунта
Аудио(С) 3000(S)
Компьютер (L) 2000(L) 3000(S)
Гитара (соль) 1500(G) 1500(G) 2000(G) 3500(L+G)

процесс расчета:

i=1:(1,1), (1,2), (1,3): поскольку, когда j=1,2,3

i=2:(2,1), (2,2): поскольку, когда j=1,2

i=3:(3,1) : макс{F(2,1), 1500 + F(3,0)} = 1500 (3,2) : max{ F(2,2), 1500 + F(3,1)} = 1500 (потому что гитара только одна, ее нельзя повторить) (3,3) : max{ F(2,3), 1500 + F(3,2)} = max{2000,1500} = 2000 (потому что гитара только одна, ее нельзя повторить) (3,4): макс{F(2,4), 1500 + F(3,3)} = макс{3000,3500} = 3500

Случай 2

Оптимизация маршрута путешествия:

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

Живописное место время счет
Лондонская церковь (А) 0,5 дня 7
Лондонский театр (B) 0,5 дня 6
Лондонская художественная галерея (К) 1 день 9
Лондонский музей (D) 2 дня 9
Лондонский тренажерный зал (клавиша E) 0,5 дня 8

Эта проблема на самом деле рюкзак, но емкость становится временем, а способ обработки такой же, как указано выше, и его можно быстро получить:

F(i,j) = max{ F(i-1,j), W(i) + F(i,j-V(i))} 即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的价值}

F(i,j)的代表 i行j列可以获得的最大价值，W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量
Живописное место 0,5 дня 1 день 1,5 дня 2 дня
Лондонская церковь (А) 7(A) 7(A) 7(A) 7(A)
Лондонский театр (B) 7(A) 13(A+B) 13(A+B) 13(A+B)
Лондонская художественная галерея (К) 7(A) 13(A+B) 16(A+C) 22(A+B+C)
Лондонский музей (D) 7(A) 13(A+B) 16(A+C) 22(A+B+C)
Лондонский тренажерный зал (клавиша E) 8(E) 15(A+E) 21(A+B+E) 24(A+C+E)

ограничение

Одним из ограничений динамического программирования является то, что каждый раз, когда он обрабатывается, весь элемент рассматривается для обработки, и он не может поддерживать практику взятия дроби.Например, случай 1 изменен на:

    背包4磅，1.有一整袋10磅的燕麦，每磅6美元 ； 
                 2.有一整袋10磅的大米，每磅3美元 ； 
                 3.有一整袋10磅的土豆，每磅5美元 ； 
        
        因为整袋无法装入，情况不再是要么拿要么不拿，而是打开包装拿物品的一部分，这种情况下动态规划就无法处理。动态规划只适合于整件物品处理的情况。但使用前面介绍的贪婪算法则很合适，一个劲拿最贵的，拿光后再拿下一个最贵。

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

Живописное место время счет
Эйфелева башня (Ф) 1,5 дня 8
Парижский университет (G) 1,5 дня 9
Парижская больница (H) 1,5 дня 7 
从这些地方还需要很长时间，因为得从伦敦前往巴黎，这需要0.5天时间（1.5天包含了0.5天的路程消耗）。如果这3个地方都去的话，是总的需要1.5 * 3= 4.5天？ 其实并不是，到达巴黎后，连续玩这3个地方其实只需 1.5 + 1 + 1 = 3.5天。 这种将 "巴黎铁塔"装入"背包"会使得"巴黎大学"、"巴黎医院"变便宜的情况，无法使用动态规划来进行建模。

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

Java-реализация

案例一：

/**
 * 动态规划 - 简单背包问题
 * @author Administrator
 *
 */
public class KnapsackProblem {
	
	public static void main(String[] args){

		float knapsackWeight = 4;
		float[] itemsWeights = new float[] {1, 4, 3};
		float[] itemsPrices = new float[] {1500, 3000, 2000}; 
		float[][] table = knapsackSolution(knapsackWeight, itemsWeights, itemsPrices);
		
		for (int line = 0; line < table.length; line++ ) {
			System.out.println("-----------------line =" + line);
			for (int colume = 0; colume < table[line].length; colume++ ) {
				System.out.println(table[line][colume] + ",");
			}
		}
	}
	
	/**
	 * 
	 * @param knapsackWeight 背包总容量
	 * @param itemsWeights	  各个物品的所占据的容量
	 * @param itemsPrices	  各个物品所具有的价值	
	 * @return
	 */
	public static float[][] knapsackSolution(float knapsackWeight, float[] itemsWeights, float[] itemsPrices) {
		if (itemsWeights.length != itemsPrices.length) {
			throw new IllegalArgumentException();
		}
		
		//计算表格的行数 --物品数量
		int lines = itemsPrices.length;
		//计算出划分的背包最小的空间，即表格每一列代表的重量为  column * minWeight
		float minWeight = getMinWeight(itemsWeights);
		//计算表格的列数 --分割出的重量数目
		int colums = (int) (knapsackWeight/minWeight);
		System.out.println("lines = " + lines + ",colums = " + colums + ",minWeight = " + minWeight);
		//创建表格对象,lines行colums列
		float[][] table = new float[lines][colums];
	
		for (int line = 0; line < lines; line++ ) {
			for (int colume = 0; colume < colums; colume++ ) {
				
				float left = table[(line - 1) < 0 ? 0 : (line - 1) ][colume];
				float right = 0;
				//判断当前划分的小背包是否可以装下该物品，当前背包容量为(colume +1)*minWeight
				if ((colume +1)*minWeight >= itemsWeights[line]) {
					//获取当前背包剩余空间
					float freeWeight = ((colume+1)*minWeight - itemsWeights[line]);
					//判断剩余空间是否还可以装下其它的东西
					int freeColumn = (int) (freeWeight/minWeight) - 1;
					if (freeColumn >= 0 && line > 0) {
						//因为表格上同一列的位置上，越往下价值越高，所以这边直接取的上一行的freeColumn位置就行
						right = itemsPrices[line] + table[line - 1][freeColumn];
					}else {
						right = itemsPrices[line];
					} 	
				}

				table[line][colume] = Math.max(left, right);
			}
			
		}
		return table;
		
	}
	
	/**
	 * 获取所有物品中最小的重量
	 * 
	 * @param itemsWeights 各个物品的所占据的容量
	 * @return
	 */
	public static float getMinWeight(float[] itemsWeights) {
		float min = itemsWeights[0];
		
		for (float weight : itemsWeights) {
			min = min > weight ? weight : min;
		}
		//保留最多2位小数，并默认非零就进位1.222 --> 1.23
		//为啥String.valueOf，参照https://www.cnblogs.com/LeoBoy/p/6056394.html
		return new BigDecimal(String.valueOf(min)).setScale(2, RoundingMode.UP).floatValue();
	}
	
}

执行完main方法打印信息如下:
lines = 3,colums = 4,minWeight = 1.0
-----------------line =0
1500.0,
1500.0,
1500.0,
1500.0,
-----------------line =1
1500.0,
1500.0,
1500.0,
3000.0,
-----------------line =2
1500.0,
1500.0,
2000.0,
3500.0,

Он просто изменен на код реализации случая 2: поплавок вес рюкзака = 2; float[] itemsWeights = new float[] {0.5f,0.5f,1,2,0.5f}; float[] itemsPrices = new float[] {7,6,9,9,8};

Категории