Алгоритм (6): Графический жадный алгоритм

искусственный интеллект алгоритм Java WeChat

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

Ссылаться на:блог wooooooo.cn на.com/Steven_oh уже/…

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

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

  • жадный алгоритм иНет фиксированной алгоритмической основы решения, ключом алгоритма является выбор жадной стратегии и выбор разных стратегий в соответствии с разными задачами.

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

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

Основная мысль

Основная идея решения задачи такова:

1. Построить математическую модель для описания проблемы

2. Разделите решаемую проблему на несколько подзадач.

3. Решите каждую подзадачу, чтобы получить локальное оптимальное решение подзадачи.

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

кейс

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

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

Проблема интервального планирования:

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

курс Время начала Время окончания
искусство 9AM 10AM
английский 9:30AM 10:30AM
математика 10AM 11AM
компьютер 10:30AM 11:30AM
Музыка 11AM 12PM

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

1. Выберитезакончить раньшеэто первый урок, который будет преподаваться в этом классе 2. Затем выберите класс, который начнется после окончания первого урока, и закончите самый ранний урок, который будет вторым в классе.

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

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

Случай 2

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

вещь масса цена
Гитара 15 1500
Аудио 30 3000
ноутбук 20 2000
монитор 29 2999
Ручка 1 200

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

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

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

Выберите: Динамик + Ручка, общее значение 3000 + 200 = 3200

Не лучшее решение: гитара + ноутбук, общая стоимость 1500 + 2000 = 3500

Конечно, стратегия выбора иногда не сильно фиксирована, она может быть следующей:

(1) Каждый раз выбирайте тот, у которого наибольшее значение, и окончательный вес не превышает:

Выберите: Динамик + Ручка, общее значение 3000 + 200 = 3200

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

Выберите: Динамик + Ручка, общее значение 3000 + 200 = 3200

(3) Каждый раз выбирайте тот, у которого наибольшая стоимость единицы (цена/вес), а окончательный вес не превышает:

Выбор: ручка + монитор, общее значение 200 + 2999 = 3199.

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

Случай 3

Проблема покрытия коллекции:

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

Радиовещательная станция Крытая площадь
K1 ID,NV,UT
K2 WA,ID,MT
K3 OR,NV,CA
K4 NV,UT
K5 CA,AZ
... ...

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

(1) Перечислите набор всех возможных радиовещательных станций, который называется набором мощности. Предполагая, что всего имеется n вещательных станций, всего имеется 2ⁿ комбинации вещательных станций.

(2) Среди этих наборов выбрать наименьший набор, покрывающий всю область, предполагая, что n отсутствует, но когда n очень велико, предполагая, что 10 подмножеств могут быть вычислены в секунду.

Количество радиостанций n Общее количество подмножеств 2ⁿ нужно время
5 32 3,2 секунды
10 1024 102,4 секунды
32 4294967296 13,6 лет
100 1,26*100³º 4x10²³ лет

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

Стратегии выбраны потому, что требуется наименьший набор, охватывающий все регионы:

(1) Выберите станцию, которая охватывает большинство непокрытых областей, даже если она включает некоторые покрытые области. (2) Повторяйте шаг 1, пока не будут покрыты все области.

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

  • как быстро
  • Насколько близко полученное приближенное решение к оптимальному решению

В этом примере жадный алгоритм является хорошим выбором, не только скорость работы высока, но и время работы этого примера составляет O (n²).Общая сумма должна быть запрошена n * n = O (n²), реализацию можно просмотреть в следующей реализации кода Java

Количество радиостанций n Общее количество подмножеств 2ⁿ истощение требует времени Жадный алгоритм
5 32 3,2 секунды 2,5 секунды
10 32 102,4 секунды 10 секунд
32 32 13,6 лет 102,4 секунды
100 32 4x10²³ лет 1000 секунд

В это время алгоритм выбирает K1, K2, K3, K5, которые охватывают все области, и, возможно, не ожидаются K2, K3, K4, K5 (возможно, ожидается, что они будут дешевле, проще в реализации и т. д.).

НП полная проблема

Случай 4:

задача коммивояжера

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

Существование 3! (факториал) = 6 возможных случаев:

A->B->C
A->C->B
B->A->C
B->C->A
C->A->B
C->B->A

Здесь и в предыдущем алгоритме поиска кратчайшего пути (поиск в ширину, Дейкстры, Беллмана-Форда), самое большое отличие в том, что нет фиксированной исходной точки (начальной точки), каждый узел может быть исходной точкой, и в нее нужно идти через каждый узел, поэтому исчерпывающее правило должно найти каждую возможность и сравнить.

Когда количество городов равно n, вероятность равна n!, при условии, что один маршрут обрабатывается каждую секунду.

номер п всего н! истощение требует времени
5 120 120 секунд
10 32 42 дня

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

Первое сравнение n-1 городов Второе сравнение n-2 городов ... n-1 сравнение 1 города В энный раз сравнивать не с кем

0+1+2+3+..+(n-1) ≈ O(n²/2)

номер п всего н! истощение требует времени Жадность требует времени
5 120 120 секунд 12,5 секунды
10 32 42 дня 50 секунд

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

Как судить, что это NP-полный:

1. Когда количество элементов невелико, скорость бега обычно высокая, но по мере увеличения количества элементов скорость становится очень медленной. 2. Обычно NP-полные задачи, требующие вычисления и сравнения «всех комбинаций». 3. Нельзя разбивать на мелкие проблемы, надо рассматривать все возможные ситуации. Это может быть NP-полная задача 4. Если задача включает последовательности (например, последовательность городов в задаче о коммивояжере) и ее трудно решить, она может быть NP-полной. 5. Если задача связана с набором (например, с набором радиостанций) и ее трудно решить, вероятно, она является NP-полной. 6. Если задачу можно преобразовать в задачу о покрытии множества или задачу о коммивояжере, то она должна быть NP-полной.

резюме

1. Жадный алгоритм может найти локальное оптимальное решение и таким образом попытаться получить глобальное оптимальное решение.

2. Полученное решение может быть приближенным оптимальным решением, а может быть и оптимальным решением (интервальная задача планирования, задача кратчайшего пути (сначала в ширину,Дейкстра))

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

4. Перед NP-полными задачами лучше всего использовать приближенные алгоритмы.

5. Жадный алгоритм (алгоритм аппроксимации) в большинстве случаев легко реализовать, а эффективность хорошая.

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

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

/**
 * 贪婪算法 - 集合覆盖问题
 * @author Administrator
 *
 */
public class Greedy {
	
	public static void main(String[] args){
		//初始化广播台信息
		HashMap<String,HashSet<String>> broadcasts = new HashMap<String,HashSet<String>>();
		broadcasts.put("K1", new HashSet(Arrays.asList(new String[] {"ID","NV","UT"})));
		broadcasts.put("K2", new HashSet(Arrays.asList(new String[] {"WA","ID","MT"})));
		broadcasts.put("K3", new HashSet(Arrays.asList(new String[] {"OR","NV","CA"})));
		broadcasts.put("K4", new HashSet(Arrays.asList(new String[] {"NV","UT"})));
		broadcasts.put("K5", new HashSet(Arrays.asList(new String[] {"CA","AZ"})));

		//需要覆盖的全部地区
		HashSet<String> allAreas = new HashSet(Arrays.asList(new String[] {"ID","NV","UT","WA","MT","OR","CA","AZ"}));
		//所选择的广播台列表
		List<String> selects = new ArrayList<String>();
		
		HashSet<String> tempSet = new HashSet<String>();
		String maxKey = null;
		while(allAreas.size()!=0) {
			maxKey = null;
			for(String key : broadcasts.keySet()) {
				tempSet.clear();
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);
				//求出2个集合的交集，此时tempSet会被赋值为交集的内容，所以使用临时变量
				tempSet.retainAll(allAreas);
				//如果该集合包含的地区数量比原本的集合多
				if (tempSet.size()>0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
					maxKey = key;
				}
			}
			
			if (maxKey != null) {
				selects.add(maxKey);
				allAreas.removeAll(broadcasts.get(maxKey));
			}
		}
		System.out.print("selects:" + selects);

	}
}

执行完main方法打印信息如下:
selects:[K1, K2, K3, K5]

публика

Если вам интересно, вы можете подписаться на общедоступный аккаунт WeChat и вместе добиваться прогресса.

Категории