Задача коммивояжера - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:27:32Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-10-23T16:48:00Z

1 версия

StasFomin: обновление данных

2008-10-22T15:39:33Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2006-04-20T19:07:41Z

реплицировано из внутренней CustisWiki

Новая страница

Задача коммивояжера (В англоязычной литературе — [[Traveling Salesman Problem]], сокращенно TSP), заключается в следующем:

Заданы ''n'' городов <math>v_1,v_2,\ldots,v_n</math>
и попарные расстояния <math>d_{ij} \equiv d(v_i,v_j)</math> между ними,
являющиеся положительными целыми числами.

Чему равна наименьшая возможная длина кольцевого маршрута,
проходящего по одному разу через все города? Иными словами, требуется
найти минимально возможное значение суммы
<math>\sum_{i=1}^{n-1} d_{\pi(i),\pi(i+1)} +d_{\pi(n),\pi(1)}</math>,
где минимум берется по всем перестановкам <math>\pi(1),\ldots,\pi(n)</math> чисел
''1,…,n''.

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

<code-python>
# Находит и возвращает гамильтонов цикл минимального веса
# в графе G. Использует перебор по всем вершинам кроме первой.
def tsp_permutations(G):
min_path_length=1e300 # устанавливаем минимальную длину в бесконечность
min_path=[]
start_node=G.nodes()[0] # Фиксируем начальный узел (сокращаем перебор).
for path in xpermutations(G.nodes()[1:]): # перебор всех узлов кроме первого.
path.insert(0,start_node) # добавляем в начало пути стартовый узел
path_length=0 # обнуляем длину текущего пути
path_is_ok=1 # Сначала считаем, что путь проходим
for i in range(0,len(path)):
v1=path[i] #выбираем ребро (v1,v2), для текущей вершины
if i<len(path)-1:
v2=path[i+1]
else:
v2=path[0] # Если нода-последняя, то замыкаем путь.

if G.has_edge(v1,v2):
path_length=path_length+G.get_edge(v1,v2)
else:
path_is_ok=0 # нет ребра (v1,v2) - путь непроходим.
break
if (path_is_ok):
print path, path_length
if min_path_length>path_length:
min_path_length=path_length
min_path=path
print "Optimal path:",min_path, min_path_length
return min_path
</code-python>

['NY', 'Moscow', 'Minsk', 'Berlin', 'Kiev'] 205
['NY', 'Moscow', 'Minsk', 'Kiev', 'Berlin'] 170
['NY', 'Moscow', 'Berlin', 'Minsk', 'Kiev'] 225
['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155
['NY', 'Berlin', 'Moscow', 'Minsk', 'Kiev'] 210
['NY', 'Berlin', 'Minsk', 'Moscow', 'Kiev'] 175
['NY', 'Berlin', 'Minsk', 'Kiev', 'Moscow'] 155
['NY', 'Berlin', 'Kiev', 'Minsk', 'Moscow'] 170
['NY', 'Kiev', 'Moscow', 'Minsk', 'Berlin'] 175
['NY', 'Kiev', 'Minsk', 'Moscow', 'Berlin'] 210
['NY', 'Kiev', 'Minsk', 'Berlin', 'Moscow'] 225
['NY', 'Kiev', 'Berlin', 'Minsk', 'Moscow'] 205
Optimal path: ['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155

<graph>
graph G{ rankdir=LR;
NY -- Berlin[fontcolor="blue",label="$50",style="bold"];
NY -- Moscow[fontcolor="blue",label="$60",style="bold"];
NY -- Kiev[fontcolor="blue",label="$80",style="solid"];
Moscow -- Berlin[fontcolor="blue",label="$50",style="solid"];
Moscow -- Minsk[fontcolor="blue",label="$15",style="solid"];
Moscow -- Kiev[fontcolor="blue",label="$10",style="bold"];
Minsk -- Berlin[fontcolor="blue",label="$20",style="bold"];
Minsk -- Kiev[fontcolor="blue",label="$15",style="bold"];
Berlin -- Kiev[fontcolor="blue",label="$30",style="solid"];
}
</graph>

Конечно, разработаны различные методы сокращения перебора, кроме того, переборные задачи допускают эффективное распараллеливание на многопроцессорную технику или вычисление сетью обычных компьютеров (см. например, [http://www.tsp.gatech.edu/d15sol/ отчет]), но это не отменяет невозможности точного решения этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является NP-полной, и общепринятой гипотезы о несовпадении классов '''P''' и '''NP'''.

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

==Метрическая задача коммивояжера==

Задача коммивояжера называется '''метрической''',
если для матрицы расстояний выполнено неравенство треугольника:

<math>
\forall i,j,k \ \ d_{ik} \leq d_{ij} + d_{jk}
</math>

Для метрической задачи коммивояжера существует приближенный [[алгоритм Кристофидеса]].

[[Category:Задачи]]
{{replicate-from-custiswiki-to-lib}}

StasFomin в 16:19, 19 апреля 2006

2006-04-19T16:19:47Z

BenderBot: реплицировано из внутренней CustisWiki

2005-12-08T04:41:40Z

реплицировано из внутренней CustisWiki

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая		Версия 16:19, 19 апреля 2006
Строка 1:		Строка 1:
−	Задача коммивояжера (В англоязычной литературе — Traveling Salesman Problem, сокращенно TSP), заключается в следующем:	+	Задача коммивояжера (В англоязычной литературе — [[Traveling Salesman Problem]], сокращенно TSP), заключается в следующем:

	Заданы ''n'' городов <math>v_1,v_2,\ldots,v_n</math>		Заданы ''n'' городов <math>v_1,v_2,\ldots,v_n</math>

← Предыдущая		Версия 04:41, 8 декабря 2005
(не показана 1 промежуточная версия 1 участника)
Строка 1:		Строка 1:
−	Задача коммивояжера (В англоязычной литературе — [[Traveling Salesman Problem]], сокращенно TSP), заключается в следующем:	+	Задача коммивояжера (В англоязычной литературе — Traveling Salesman Problem, сокращенно TSP), заключается в следующем:

	Заданы ''n'' городов <math>v_1,v_2,\ldots,v_n</math>		Заданы ''n'' городов <math>v_1,v_2,\ldots,v_n</math>

@@ Строка 1: / Строка 1: @@
-Задача коммивояжера (В англоязычной литературе — [[Traveling Salesman Problem]], сокращенно TSP), заключается в следующем:
+#REDIRECT [[discopal:{{PAGENAME}}]]
-−
-Заданы ''n'' городов <m>v_1,v_2,\ldots,v_n</m>
-и попарные расстояния <m>d_{ij} \equiv d(v_i,v_j)</m> между ними,
-являющиеся положительными целыми числами.
-−
-Чему равна наименьшая возможная длина кольцевого маршрута,
-проходящего по одному разу через все города? Иными словами, требуется
-найти минимально возможное значение суммы
-<m>\sum_{i=1}^{n-1} d_{\pi(i),\pi(i+1)} +d_{\pi(n),\pi(1)}</m>,
-где минимум берется по всем перестановкам <m>\pi(1),\ldots,\pi(n)</m> чисел
-''1,…,n''.
-−
-Приведенный ниже пример переборного алгоритма и его выполнения, демонстрирует его неэффективность, и невозможность нахождения точного решения для данных реальных объемов:
-−
-<code-python>
-# Находит и возвращает гамильтонов цикл минимального веса
-# в графе G. Использует перебор по всем вершинам кроме первой.
-def tsp_permutations(G):
-    min_path_length=1e300   # устанавливаем минимальную длину в бесконечность
-    min_path=[]
-    start_node=G.nodes()[0] # Фиксируем начальный узел (сокращаем перебор).
-    for path in xpermutations(G.nodes()[1:]): # перебор всех узлов кроме первого.
-        path.insert(0,start_node)    # добавляем в начало пути стартовый узел
-        path_length=0                # обнуляем длину текущего пути
-        path_is_ok=1                 # Сначала считаем, что путь проходим
-        for i in range(0,len(path)):
-            v1=path[i]   #выбираем ребро (v1,v2), для текущей вершины
-            if i<len(path)-1:
-                v2=path[i+1]
-            else:
-                v2=path[0]           # Если нода-последняя, то замыкаем путь.
-−
-            if G.has_edge(v1,v2):
-                path_length=path_length+G.get_edge(v1,v2)
-            else:
-                path_is_ok=0  # нет ребра (v1,v2) - путь непроходим.
-                break
-        if (path_is_ok):
-                print path, path_length
-                if min_path_length>path_length:
-                    min_path_length=path_length
-                    min_path=path
-    print "Optimal path:",min_path, min_path_length
-    return min_path
-</code-python>
-−
- ['NY', 'Moscow', 'Minsk', 'Berlin', 'Kiev'] 205
- ['NY', 'Moscow', 'Minsk', 'Kiev', 'Berlin'] 170
- ['NY', 'Moscow', 'Berlin', 'Minsk', 'Kiev'] 225
- ['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155
- ['NY', 'Berlin', 'Moscow', 'Minsk', 'Kiev'] 210
- ['NY', 'Berlin', 'Minsk', 'Moscow', 'Kiev'] 175
- ['NY', 'Berlin', 'Minsk', 'Kiev', 'Moscow'] 155
- ['NY', 'Berlin', 'Kiev', 'Minsk', 'Moscow'] 170
- ['NY', 'Kiev', 'Moscow', 'Minsk', 'Berlin'] 175
- ['NY', 'Kiev', 'Minsk', 'Moscow', 'Berlin'] 210
- ['NY', 'Kiev', 'Minsk', 'Berlin', 'Moscow'] 225
- ['NY', 'Kiev', 'Berlin', 'Minsk', 'Moscow'] 205
- Optimal path: ['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155
-−
-<graph>
- graph G{ rankdir=LR;
- NY -- Berlin[fontcolor="blue",label="$50",style="bold"];
- NY -- Moscow[fontcolor="blue",label="$60",style="bold"];
- NY -- Kiev[fontcolor="blue",label="$80",style="solid"];
- Moscow -- Berlin[fontcolor="blue",label="$50",style="solid"];
- Moscow -- Minsk[fontcolor="blue",label="$15",style="solid"];
- Moscow -- Kiev[fontcolor="blue",label="$10",style="bold"];
- Minsk -- Berlin[fontcolor="blue",label="$20",style="bold"];
- Minsk -- Kiev[fontcolor="blue",label="$15",style="bold"];
- Berlin -- Kiev[fontcolor="blue",label="$30",style="solid"];
-−
-</graph>
-−
-Конечно, разработаны различные методы сокращения перебора, кроме того, переборные задачи допускают эффективное распараллеливание на многопроцессорную технику или вычисление сетью обычных компьютеров (см. например, [http://www.tsp.gatech.edu/d15sol/ отчет]), но это не отменяет невозможности точного решения этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является NP-полной, и общепринятой гипотезы о несовпадении классов '''P''' и '''NP'''.
-−
-Существуют различные алгоритмы для приближенного решения этой задачи или ее частных случаев.
-−
-==Метрическая задача коммивояжера==
-−
-Задача коммивояжера называется '''метрической''',
-если для матрицы расстояний выполнено неравенство треугольника:
-−
-<m>
-   \forall i,j,k \ \  d_{ik} \leq d_{ij} + d_{jk}
-</m>
-−
-Для метрической задачи коммивояжера существует приближенный [[алгоритм Кристофидеса]].
-−
-[[Category:Задачи]]
-{{replicate-from-custiswiki-to-lib}}

← Предыдущая	Версия 16:48, 23 октября 2008
(нет различий)