DM_shpory

35. Задача коммивояжера. Алгоритм поиска субоптимального решения.

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

Дан нагруженный граф с множеством вершин V. Цикл, полученный в результате работы, будет совпадать с конечным значением переменной маршрут, а его длина — конечное значение переменной w.

Begin

Выбрать v Î V;

Маршрут := v;

w:= 0;

v¢:=v;

Отметить v¢;

while останутся неотмеченные вершины do

begin

Выбрать неотмеченную вершину u, ближайшую к v¢;

Маршрут := маршрут и;

w:= w + вес ребра v¢ u;

v¢ := u;

Отметить v¢

еnd

Маршрут := маршрут v;

w:= w + вес ребра v¢ v

end

	u	Маршрут	w
Исходные значения	—	D	0	D
	C	DC	3	C
	A	DCA	9	A
	B	DCAB	14	B
Последний проход	B	DCABD	24	B

!!! В полном графе с 20-ю вершинами существует приблизительно 6,1*1016 гамильтононовых циклов

Содержание