4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 00:46, 23 января 2014
, 23 января 2014→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}\ ^d</math> найти путь минимальной длины, проходящий через каждую точку ровно один раз. | Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}\ ^d</math> найти путь минимальной длины, проходящий через каждую точку ровно один раз. | ||
Стоимость <math>\delta\ (x, y)</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R}\ ^d</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta\ (x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} </math>, где <math>x = (x_1, ..., x_d) \; </math> и <math>y = (y_1, ..., y_d \; )</math>. В более общем виде расстояние можно определить с использованием других норм – таких как | Стоимость <math>\delta\ (x, y)</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R}\ ^d</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta\ (x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} </math>, где <math>x = (x_1, ..., x_d) \; </math> и <math>y = (y_1, ..., y_d \; )</math>. В более общем виде расстояние можно определить с использованием других норм – таких как <math>\ell _p</math>-нормы для любого p > 1, <math>\delta\ (x, y) = (\sum_{i=1}^d (x_i - y_i)^p)^{1/p} </math>. | ||
Для заданного множества S точек в евклидовом пространстве Rd, для целого d > 2, евклидов граф (сеть) представляет собой граф G = (S; E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа: | Для заданного множества S точек в евклидовом пространстве Rd, для целого d > 2, евклидов граф (сеть) представляет собой граф G = (S; E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа: | ||