В чем разница между путешествующим продавцом и китайским путешествием?

Question

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

Answer 1

Графики сделаны из ребер и вершин.CPP требует посещения всех краев.TSP требует посещения всех вершин.

Answer 2

Путешествующий продавец собирается поехать в каждый город по кратчайшему маршруту.

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

Например, св точках A, B, C и D коммивояжер мог бы пойти в ABCDA, но китайскому почтальону понадобится маршрут, который имеет AB и AC и AD и т. д.

Маршрут коммивояжера не имеет прямой связи между каждой точкой (в приведенном выше примере отсутствует ссылка AC).

РЕДАКТИРОВАТЬ:
Каждый город является вершиной и каждыймеждугородняя связь - это край.Итак, я думаю, что просто повторяю ответ @ Xodarap.

Answer 3

Сохраняя это очень просто:

Задача коммивояжера состоит в том, чтобы идти в каждый город ровно один раз, возвращаясь в исходный город (таким образом, идя по гамильтонову циклу 1006 *), а также выбирая кратчайший маршрут из всех возможных маршруты, которые соответствуют этому критерию (если такой маршрут существует). Найти такой цикл, выполнить поиск возможно уникального оптимального цикла с кратчайшим расстоянием - это «сложно».

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

Answer 4

• Китайский почтальон: http://en.wikipedia.org/wiki/Route_inspection_problem
• Путешествующий продавец: http://en.wikipedia.org/wiki/Travelling_salesman_problem

Из краткого прочтения двух статей (и я никогда не проходил курс по графикутеория, так что я мог бы говорить через мою шляпу), кажется, что "CPP" включает в себя посещение всех ребер, а "TSP" предполагает посещение всех узлов.

Answer 5

Задача коммивояжера: Учитывая города и расстояние между городами, найдите кратчайший маршрутный маршрут так, чтобы он посещал каждый город ровно по одному.Визуализируя это в виде графика и стоимости или веса, связанных с каждым ребром, найдите самый дешевый или наименее весовой маршрут (гамильтонов путь), чтобы каждая вершина или узел посещались ровно один раз.Мы можем думать об этом как о том, чтобы найти все возможные гамильтоновы пути, а затем найти лучший среди них.Поиск всех возможных маршрутов является задачей оптимизации, а в NP - Complete означает, что для этой задачи не существует решения за полиномиальное время

Проблема китайского почтальона: В отличие от задачи коммивояжера, CPP требует найти минимумСтоимость или минимальный вес обходят график таким образом, чтобы каждое ребро посещалось хотя бы один раз.Задача имеет полиномиальное решение, и для оптимального решения требуется найти обход Эйлера по графу, если граф эйлеров.Еще измените график, чтобы он стал эйлеровым, и определите тур Эйлера.Особый случай китайской проблемы почтальона - это то, что нам не нужно путешествовать по всем ребрам графа, а только по некоторым из них (обязательные ребра).Эта вариация называется Сельская проблема почтальона и является NP-полной.Другими словами, учитывая график, найдите обход с наименьшей стоимостью / минимальным весом, чтобы все требуемые ребра были покрыты хотя бы один раз, возможно, используются ненужные ребра.

Answer 6

Основное различие между ними:

Задача коммивояжера не может посетить узел более одного раза. Созданный путь будет состоять из всех разных узлов / городов.

Задача китайского почтальона / проверки маршрута может иметь дублирующиеся узлы на полученном пути (но не дублирующие ребра) То есть узлы можно посещать более одного раза, если вы выбираете другой маршрут, отличный от выбранного.

Answer 7

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

Китайская задача коммивояжера (C-TSP) является типичной симметричной проблемой TSP.Его простое описание: учитывая 31 столицу Китая и их попарные расстояния, задача состоит в том, чтобы найти кратчайший тур, который посещает каждый город ровно один раз.C-TSP - это проблема TSP среднего масштаба, которая имеет (31−1)! / 2 = 1,326 * 1032 возможных маршрутов.