ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

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

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

Метод ветвей и границ для задачи о коммивояжере

Предыдущая 1 2 3 4 567 8 9 10 11 12 13 14 15 16 Следующая

Задача коммивояжера является одной из знаменитых задач теории комбинаторики.

В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

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

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

Пусть имеется n-городов. Расстояния между любой парой городов (i, j) известны и составляют d_ij, где ; ; i≠j. Если прямого маршрута сообщения между городами не существует, а также для всех i=j полагаем, что d_ij = ∞. На этом основании расстояния между городами удобно представить в виде матрицы D=(d_ij).

На рисунке представлен граф задачи коммивояжёра.

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

Поскольку всего городов n, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько – оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т.е. d_ij= d_ji.

Расстояния между городами записывается в виде матрицы с неотрицательными элементами d_ij , которые отображают длины дуг в сети городов.

Математическая модель задачи:

Условия неотрицательности и целочисленности:

, , .

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

Алгоритм решения задачи рассмотрим на примере:

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

i j						d_i
	M
		M
			M
				M
					M

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

i j
	M
		M
			M
				M
					M

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

i j
	M
		M
			M
				M
					M
d_j

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

i j
	M
		M
			M
				M
					M

Сумма констант приведения определяет нижнюю границу:

H = 40+40+20+10+20+0+10+0+0+0 = 140.

Данные для вычисления берем из столбца d_i таблицы, которая построена в алгоритме 1, то есть 40, 40, 20, 10, 20. Вторую часть данных берем из строки d_j таблицы, построенной в алгоритме 3.

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то D является матрицей n∙n с неотрицательными элементами d_ij . Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij .

5. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i/j						d_i
	M			0(40)
		M	0(20)
		0(10)	M		0(30)
	0(10)			M
	0(0)			0(0)	M
d_j

Пример:

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20;

d(3,2) = 0 + 10 = 10;

d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0;

d(5,4) = 0 + 0 =0.

Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подножества (1,4) и (1*,4*). Нижняя граница гамильтоновых циклов этого подмножества: H(1*,4*) = 140 + 40.

6. Исключение ребра (1,4) проводим путем замены элемента d₁₄ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j						d_i
	M			M
		M
			M
				M
					M
d_j

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d₄₁ заменяем на М, для исключения образования не гамильтонова цикла. В результате получим другую сокращенную матрицу (4х4), которая подлежит операции приведения.

7. После операции приведения сокращенная матрица будет иметь вид:

i j					d_i
		M
			M
	M
				M
d_j

Нижняя граница подмножества (1,4) равна:

H(1,4) = 140 + 10 = 150 < 180.

Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут.

8. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j					d_i
		M	0(20)
		0(10)	M	0(30)
	M		0(30)
	0(30)			M
d_j

Пример:

d(1,3) = 20 + 0 = 20; d(2,2) = 0 + 10 = 10; d(2,4) = 0 + 30 = 30;

d(3,3) = 30 + 0 = 30; d(4,1) = 10 + 20 = 30.

Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подножества (3,5) и (3*,5*). Нижняя граница гамильтоновых циклов этого подмножества:

H(3*,5*) = 150 + 30

9. Исключение ребра (3,5) проводим путем замены элемента d₃₅=0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i j					d_i
		M
			M	M
	M
				M
d_j

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d₅₃ заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (3х3), которая подлежит операции приведения.

10. После операции приведения сокращенная матрица будет иметь вид:

i j				d_i
		M
	M
			M
d_j

Нижняя граница подмножества (3,5) равна:

H(3,5) = 150 + 10 = 160 < 180

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут.

11. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j				d_i
		M	0(20)
	M		0(30)
	0(20)	0(30)	M
d_j

Пример:

d(1,3) = 20 + 0 = 20; d(2,3) = 30 + 0 = 30;

d(3,1) = 0 + 20 = 20; d(3,2) = 0 + 30 = 30.

Наибольшая сумма констант приведения равна (30 + 0) = 30 для ребра (4,3), следовательно, множество разбивается на два подножества (4,3) и (4*,3*). Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 160 + 30.

12. Исключение ребра (4,3) проводим путем замены элемента d₄₃ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j				d_i
		M
	M		M
			M
d_j

13. Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d₃₄ заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (2х2), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:

i j		d_i
	M

d_j

Нижняя граница подмножества (4,3) равна:

H(4,3) = 160 + 20 = 180 < 190

Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут. В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (5,2) и (2,1). В результате по дереву ветвлений гамильтонов цикл образуют ребра: (1,4), (4,3), (3,5), (5,2), (2,1). Длина маршрута равна F(Mk) = 180

Предыдущая 1 2 3 4 567 8 9 10 11 12 13 14 15 16 Следующая