Алгоритм (5): Графический алгоритм Беллмана-Форда

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

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

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

  • Его принцип состоит в том, чтобы выполнить на графе не более V-1 операций релаксации, чтобы получить все возможные кратчайшие пути. Он превосходит алгоритм Дейкстры тем, что вес ребра может быть отрицательным, а реализация проста, а недостатком является слишком высокая временная сложность, вплоть до O(VE). Однако алгоритм можно оптимизировать несколькими способами для повышения эффективности.

  • Алгоритм Беллмана Форда каждый раз релаксирует все ребра, и каждое релаксирование получает кратчайший путь, поэтому общее количество операций релаксации, которое необходимо выполнить, составляет V - 1 раз. Если он все еще может расслабиться после стольких релаксаций, это означает, что он содержит отрицательное кольцо.

  • по сравнению сАлгоритм Дейкстры, его самым большим преимуществом является то, что Беллман-Форд поддерживает наличие отрицательных весов, а кодовая реализация относительно проста. Недостатком является высокая временная сложность, достигающая O(V*E), где V представляет количество вершин, а E представляет количество ребер.

Может использоваться для решения следующих задач:

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

Идея такова:

  1. Во время инициализации расстояние dist(s->v) от начальной точки s до каждой вершины v присваивается ∞, а dist(s->s) присваивается 0

  2. Последующие операции обхода не более n-1 раз (n — количество вершин, нельзя ввести верхний индекс v, метод ввода...) и операции релаксации выполняются на всех ребрах, предполагая:

    Так называемая релаксация, на примере ребра ab, если dist(a) представляет общую стоимость начальной точки s для достижения точки a, dist(b) представляет собой общую стоимость начальной точки s для достижения точки b, weight(ab) представляет собой вес ребра ab, Если имеется:

    (dist(a) +weight(ab)) < dist(b)

    Это означает, что есть более короткий путь к b, s->...->a->b, общая стоимость обновления точки b равна (dist(a) +weight(ab)), а родительский узел

  3. Если после завершения обхода обход выполняется снова и удается получить более короткий путь от s до некоторых узлов, то это означает наличие отрицательной петли.

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

кейс

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

Давайте возьмем распространенный пример в Интернете, чтобы представить идею его реализации:

Как показано на рисунке ниже, кратчайший путь от начальной точки А до конечной точки получается в соответствии с алгоритмом Беллмана-Форда.

Как видно из приведенного выше введения, поскольку общее количество вершин в графе равно n = 5 вершинам, требуется 5-1 = 4 операции обновления обхода.Если в каждой операции можно найти более короткий путь, значение соответствующий узел будет обновлен.

1. Прежде всего, для установления информации о краевом объекте необходимо начать с исходной точки А, от ближайшего к самому дальнему порядку, в противном случае, если расстояние(с)==∞ бесконечность не начинается с исходной точки, это усложнит последующие вычисления:

AB:-1
AC:4
BC:3
BE:2
BD:2
ED:-3
DC:5
DB:1

1. Сначала перечислите время, затраченное от начальной точки A до каждого узла:

родительский узел узел инициализация
A A 0
.. B ∞
.. C ∞
.. D ∞
.. E ∞

2. Выполнить первую операцию релаксации на всех ребрах:

2.1 Подсчитайте значения AB и AC узлов, которые могут быть достигнуты одним ребром:

AB:-1
AC:4
родительский узел узел Стоимость
A A 0
A B -1
A C 4
.. D ∞
.. E ∞

2.2 Подсчитайте значения BC, BD, BE узлов, до которых можно добраться через 2 ребра:

BC:3
BE:2
BD:2
родительский узел узел Стоимость
A A 0
A B -1
B C 2
B D 1
B E 1

Взяв узел C в качестве примера, поскольку он удовлетворяет: dist(B) + weight(BC) > dist(C), то есть -1 + 3 > 4, C обновляется до 2

2.3 Подсчитайте значения ED и DC узлов, до которых можно добраться через 3 ребра:

ED:-3
DC:5
DB:1
родительский узел узел Стоимость
A A 0
A B -1
B C 2
E D -2
B E 1

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

родительский узел узел Стоимость
A A 0
A B -1
B C 2
E D -2
B E 1

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

Случай 2

Как показано на рисунке ниже, найдите кратчайший путь от A до каждого узла.

1. Всего в графе 7 узлов, и требуется максимум 7-1=6 операций релаксации на всех ребрах.

2. Сначала создайте граничный объект:

AB:6
AC:5
AD:5
CB:-2
DC:-2
BE:-1
CE:1
DF:-1
EG:3
FG:3

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

родительский узел узел Стоимость
A A 0
C B 3
D C 3
A D 5
B E 2
D F 4
E G 5

4. Выполните вторую операцию релаксации обхода, чтобы получить:

родительский узел узел Стоимость
A A 0
C B 1
D C 3
A D 5
B E 0
D F 4
E G 3

5. Выполняется третья операция релаксации обхода, и результат снова не обновляется:

родительский узел узел Стоимость
A A 0
C B 1
D C 3
A D 5
B E 0
D F 4
E G 3

6. На данный момент кратчайший путь от A до каждого узла на краю приведенной выше таблицы может быть получен в обратном порядке.

8. Здесь предполагается, что граничные объекты одного уровня (имея в виду начало из A, могут быть достигнуты через одинаковое количество рёбер, например, DC, CB, BE, DF, CE могут быть достигнуты через 2 рёбра) до настроить позицию сортировки и Не влияет на правильность результата, но влияет на количество необходимых обходов (разные уровни):

Например, выше, AB:6,AC:5,AD:5,CB:-2,DC:-2,BE:-1,CE:1,DF:-1,EG:3,FG:3 требуется код пройти 3 Результат можно подтвердить только один раз (последнее время подтверждения результата не обновляется);

AB:6, AC:5, AD:5, DC:-2, CB:-2, BE:-1, CE:1, DF:-1, EG:3, FG:3 Код необходимо пройти дважды y проверить результаты;

AB:6, AC:5, AD:5, BE:-1, CE:1, DF:-1, DC:-2, CB:-2, EG:3, FG:3 Необходимо пройти код 4 раз проверить результаты;

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

ограничение

Случай 3, когда есть отрицательная петля

  • Измените график случая 1 B->D на -2. Сделайте BD, который образует отрицательную петлю.Так называемая отрицательная петля означает, что сумма весов петли отрицательна, например, на рисунке выше 1 + (-2) = -1

  • Поскольку отрицательный цикл может выполнять бесконечные шаги цикла, до тех пор, пока вы хотите, вы можете бесконечно зацикливаться в B->D->B->D..., поэтому значения B и D могут быть бесконечно малы, Тогда когда значения B и D бесконечно малы, то начиная от узлов B и D к другим узлам, значения других узлов также будут близки к бесконечно малым, поэтому для случая отрицательной петли Беллмана– Форд может судить только о графе. Имеется отрицательный цикл без смысла нахождения кратчайшего пути каждого узла

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

Например, в том же случае 1 после выполнения 4 обходов по графу получаем результат:

родительский узел узел Стоимость линия исполнения
A A 0
A B -2 A->B->D->B
B C 1 A->B->D->B->C
E D -4 A->B->D-B->D
B E 0 A->B->D->B->E

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

родительский узел узел Стоимость линия исполнения
A A 0
A B -3 A->B->D->B->D->B
B C 1 A->B->D->B->C
E D -4 A->B->D-B->D
B E 0 A->B->D->B->E

Найдено, что есть узел B, который можно обновить в это время, что доказывает, что в графе есть отрицательный цикл.

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

резюме

1. Алгоритм BFS в ширину в основном подходит для повторного поиска пути с наименьшим количеством шагов от исходной точки до конечной точки в невесомом графе направлений, когда граф направлений имеет веса, он уже не применим.

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

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

4. Беллман-Форд может определить, есть ли в графе отрицательный цикл, но не поддерживает вычисление кратчайшего пути каждой вершины в случае отрицательного цикла. Необходимо выполнить еще один обход только после завершения (количество узлов - 1) обходов.Если данные все еще могут быть обновлены, это означает, что существует отрицательный цикл.

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

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

/**
 * 贝尔曼-福特算法
 * @author Administrator
 *
 */
public class BellmanFord {
	public static void main(String[] args){
		
		//创建图
		Edge ab = new Edge("A", "B", -1);
		Edge ac = new Edge("A", "C", 4);
		Edge bc = new Edge("B", "C", 3);
		Edge be = new Edge("B", "E", 2);
		Edge ed = new Edge("E", "D", -3);
		Edge dc = new Edge("D", "C", 5);
		Edge bd = new Edge("B", "D", 2);
		Edge db = new Edge("D", "B", 1);
		
		//需要按图中的步骤步数顺序建立数组，否则就是另外一幅图了，
		//从起点A出发，步骤少的排前面
		Edge[] edges = new Edge[] {ab,ac,bc,be,bd,ed,dc,db};
		
		//存放到各个节点所需要消耗的时间
		HashMap<String,Integer> costMap = new HashMap<String,Integer>();
		//到各个节点对应的父节点
		HashMap<String,String> parentMap = new HashMap<String,String>();
		
		
		//初始化各个节点所消费的，当然也可以再遍历的时候判断下是否为Null
		//i=0的时候
		costMap.put("A", 0); //源点
		costMap.put("B", Integer.MAX_VALUE);
		costMap.put("C", Integer.MAX_VALUE);
		costMap.put("D", Integer.MAX_VALUE);
		costMap.put("E", Integer.MAX_VALUE);
		
		//进行节点数n-1次循环
		for(int i =1; i< costMap.size();i++) {
			boolean hasChange = false;
			for(int j =0; j< edges.length;j++) {
				Edge edge = edges[j];
				//该边起点目前总的路径大小
				int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
				//该边终点目前总的路径大小
				int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
				//如果该边终点目前的路径大小 > 该边起点的路径大小 + 该边权重 ，说明有更短的路径了
				if(endPointCost > (startPointCost + edge.getWeight())) {
					costMap.put(edge.getEndPoint(), startPointCost + edge.getWeight());
					parentMap.put(edge.getEndPoint(), edge.getStartPoint());
					hasChange = true;
				}
			}
			if (!hasChange) {
				//经常还没达到最大遍历次数便已经求出解了，此时可以优化为提前退出循环
				break;
			}
		}
		
		//在进行一次判断是否存在负环路
		boolean hasRing = false;
		for(int j =0; j< edges.length;j++) {
			Edge edge = edges[j];
			int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
			int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
			if(endPointCost > (startPointCost + edge.getWeight())) {
				System.out.print("\n图中存在负环路，无法求解\n");
				hasRing = true;
				break;
			}
		}
		
		if(!hasRing) {
			//打印出到各个节点的最短路径
			for(String key : costMap.keySet()) {
				System.out.print("\n到目标节点"+key+"最低耗费:"+costMap.get(key));
				if(parentMap.containsKey(key)) {
					List<String> pathList = new ArrayList<String>();
					String parentKey = parentMap.get(key);
					while (parentKey!=null) {
						pathList.add(0, parentKey);
						parentKey = parentMap.get(parentKey);
					}
					pathList.add(key);
					String path="";
					for(String k:pathList) {
						path = path.equals("") ? path : path + " --> ";
						path = path +  k ;
					}
					System.out.print("，路线为"+path);
				} 
			}
		}

		
	}
	

	
	/**
	 * 	代表"一条边"的信息对象
	 * 
	 * @author Administrator
	 *
	 */
	static class Edge{
		//起点id
		private String startPoint;
		//结束点id
		private String endPoint;
		//该边的权重
		private int weight;
		public Edge(String startPoint,String endPoint,int weight) {
			this.startPoint = startPoint;
			this.endPoint = endPoint;
			this.weight = weight;
		}
		public String getStartPoint() {
			return startPoint;
		}
		
		public String getEndPoint() {
			return endPoint;
		}
		
		public int getWeight() {
			return weight;
		}
	}
}

执行完main方法打印信息如下:
到目标节点B最低耗费:-1，路线为A --> B
到目标节点C最低耗费:2，路线为A --> B --> C
到目标节点D最低耗费:-2，路线为A --> B --> E --> D
到目标节点E最低耗费:1，路线为A --> B --> E

Публичный аккаунт WeChat

Категории