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

Ответ 1

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

Проблема китайского почтальона - это путь от каждого города к другому городу.

например. с точками A, B, C и D коммивояжер мог пойти A-B-C-D-A, но китайскому почтальону понадобился маршрут с A-B и A-C и A-D и т.д.

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

EDIT:
Каждый город - это вершина, и каждая межгородская связь - это край. Итак, я думаю, что просто возвращаю @Xodarap ответ.

Ответ 2

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

Ответ 3

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

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

Ответ 4

Сохранение ультрасовременности:

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

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

Ответ 5

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

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

Ответ 6

Ключевое различие между ними:

Проблема с продавцом не может посещать node более одного раза. Созданный путь будет состоять из всех разных узлов/городов.

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

Ответ 7

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

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