| dbo:abstract
|
- Problém čínského listonoše je úloha z teorie grafů, která spadá do problematiky optimalizace cesty v grafu. Tuto úlohu formuloval čínský matematik M.-K. Kwan roku 1960. (cs)
- In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time. The problem was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962. The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to Alan J. Goldman or Jack Edmonds, both of whom were at the U.S. National Bureau of Standards at the time. A generalization is to choose any set T of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of T. Such a set is called a T-join. This problem, the T-join problem, is also solvable in polynomial time by the same approach that solves the postman problem. (en)
- Das Briefträgerproblem ist ein Modell aus der Graphentheorie, bei welchem man sich des übertragenen Bildes eines Postboten, der auf dem kürzesten Weg Briefe austrägt, bedient: Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen. Seinen englischen Namen (Chinese postman problem) erhielt das Briefträgerproblem durch nach dem chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte. Eine Lösung wurde 1973 durch Jack Edmonds und Ellis L. Johnson angegeben. (de)
- En teoría de grafos (una rama de la matemática), el problema del cartero chino (PCC), o problema del circuito del cartero, o problema de la inspección y selección de rutas, consiste en encontrar el camino más corto o circuito cerrado, que visite cada arista de un grafo (conectado) no direccionado, o sea, que pase al menos una vez por cada arista del grafo, volviendo al punto (o nodo) de partida. Cuando el grafo posee un circuito euleriano (un paseo cerrado que alcance toda arista solamente una vez), ese circuito es una solución óptima. Alan J. Goldman del Instituto Nacional de Estándares y Tecnología (EE. UU.), usó por primera vez la denominación 'problema del cartero chino' para este problema, ya que originalmente fue estudiado por el matemático chino Mei-Ko Kuan en 1962, quien precisamente era cartero. (es)
- Grafo-teorian, postari txinatarraren ebazkizuna edo bide ikuskapen ebazkizuna noranzkorik gabeko grafo haztatu batean ertz edo lokarri guztiak zeharkatzen dituen ibilbide itxi edo zirkuitu laburrena bilatzeko ebazkizuna da. (eu)
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. Le problème peut être réduit à la recherche d'un couplage maximal de poids minimum, et ainsi être résolu en temps polynomial dans le cas général. (fr)
- Il problema del postino cinese è un problema della teoria dei grafi formulato dal matematico cinese Mei-Ku Kwan (o Kuan) nel 1962. Consiste nella creazione di un cammino ciclico di lunghezza minima in un grafo non orientato che ne attraversi tutti i suoi archi. Il nome del problema ("postino cinese") fu coniato da Alan Goldman del NIST. In un grafo euleriano, la soluzione è rappresentata da un cammino euleriano, e la lunghezza del cammino più corto equivale al numero degli archi presenti. Costruzione di grafo euleriano ottenuta a partire dal grafo precedente Se un grafo non è euleriano deve contenere vertici di grado dispari. Per via del lemma della stretta di mano, devono esserci un numero pari di questo tipo di vertici. Si noti che si devono visitare archi che escono da questi vertici di grado dispari per risolvere il problema. La soluzione consiste nel rendere il grafo euleriano, raddoppiando gli archi che connettono coppie di vertici di grado dispari. Si scelgano coppie tali per cui la distanza complessiva coperta da tutti i percorsi che connettono questi vertici sia la minore possibile; ora che il grafo è euleriano, la soluzione del problema del postino cinese è quindi un suo percorso euleriano. (it)
- Problem chińskiego listonosza (ang. Chinese postman problem, route inspection problem) – zadanie znalezienia ścieżki zamkniętej (wracającej do wierzchołka początkowego), zawierającej każdą krawędź grafu co najmniej raz i mającej minimalny koszt (sumę wag krawędzi). Problem został pierwszy raz sformułowany w 1962 roku w języku chińskim. Złożoność obliczeniowa problemu uzależniona jest od rodzaju grafu, na którym jest on rozpatrywany. W przypadku grafów w całości skierowanych albo nieskierowanych, problem chińskiego listonosza można rozwiązać w czasie wielomianowym. W przypadku grafów mieszanych (częściowo skierowanych, częściowo nieskierowanych) problem zalicza się do klasy NP-trudnych. (pl)
- 中国人郵便配達問題（ちゅうごくじんゆうびんはいたつもんだい、英: Chinese postman problem）とは、グラフ理論における問題の一つであり、以下のように定義される。 Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。 (ja)
- Het Chinese postbodeprobleem is een veelgebruikte metafoor om een bekende probleemstelling in de grafentheorie duidelijk te maken. Een postbode moet brieven bezorgen in een bepaalde stad. Hij moet daarbij vertrekken vanuit het postkantoor, alle straten doorlopen om vervolgens weer in het postkantoor te eindigen. Daarbij is het de bedoeling om de totaal afgelegde afstand minimaal te houden. Vertaald naar de grafentheorie komt dit hierop neer: zoek de kortst mogelijke route in een ongerichte graaf die vertrekt en eindigt in dezelfde knoop, en die alle verbindingen in de graaf bevat. Als er op ieder verkeersknooppunt een even aantal wegen uitkomt, hoeft hij volgens de grafentheorie iedere weg maar één keer langs te gaan en komt hij bij zijn beginpunt uit. De weg die hij dan aflegt, is een eulercykel. Dit probleem lijkt sterk op het handelsreizigersprobleem. Het handelsreizigersprobleem is echter NP-moeilijk, terwijl het Chinese postbodeprobleem in polynomiale tijd kan worden opgelost. De naam Chinese postman problem werd bedacht door Alan Goldman van het National Institute of Standards and Technology en verwijst naar het feit dat de Chinese wiskundige Mei Ko Kwan er in 1962 voor het eerst over publiceerde. (nl)
- Em teoria dos grafos, um ramo da matemática, o problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma solução ótima. Alan Goldman do U.S. National Bureau of Standards cunhou pela primeira vez o nome 'problema do carteiro chinês' para este problema, uma vez que foi originalmente estudado pelo matemático chinês Mei-Ku Kuan em 1962. (pt)
- Задача китайского почтальона (англ. Chinese postman problem, CPP), маршрут почтальона или задача инспекции дорог заключается в поиске кратчайшего замкнутого пути или цикла, который проходит через каждое ребро (связного) взвешенного неориентированного графа. Если граф имеет эйлеров цикл (замкнутый маршрут, который проходит любое ребро ровно один раз), тогда этот цикл служит оптимальным решением. В противном случае задачей оптимизации является поиск наименьшего числа рёбер графа с повторными проходами (или подмножество рёбер с минимальным возможным общим весом), так что получающийся мультиграф имеет эйлеров цикл. Эта задача может быть решена за полиномиальное время. Задачу первоначально изучал в 1960 году китайский математик , отсюда и её название — задача китайского почтальона. Статья Гуань Мэйгу была переведена с китайского на английский в 1962 году. Различные источники приписывают это название либо Алану Дж. Голдману, либо Джеку Эдмондсу, которые работали в Национальном институте стандартов и технологий в то время. (ru)
- 中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美國國家標準和技術研究院（NIST）的 Alan Goldman 首先將此問題命名为中国邮递员问题。 (zh)
- Задача (китайського) листоноші (англ. Chinese postman problem або англ. Route inspection problem) — задача пошуку найкоротшого циклу в графі, що включає всі ребра. Існують варіанти задачі для орієнтованих та неорієнтованих графів та для графів, частина ребер яких орієнтована, а частина — ні. Задача отримала назву завдяки Алану Голдману (англ. Alan Goldman) з NIST, оскільки першим дослідником цієї задачі був китайський математик (англ. Mei-Ku Kuan, 1962). (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9715 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:mode
| |
| dbp:title
|
- Chinese Postman Problem (en)
|
| dbp:urlname
|
- ChinesePostmanProblem (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- Problém čínského listonoše je úloha z teorie grafů, která spadá do problematiky optimalizace cesty v grafu. Tuto úlohu formuloval čínský matematik M.-K. Kwan roku 1960. (cs)
- Das Briefträgerproblem ist ein Modell aus der Graphentheorie, bei welchem man sich des übertragenen Bildes eines Postboten, der auf dem kürzesten Weg Briefe austrägt, bedient: Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen. Seinen englischen Namen (Chinese postman problem) erhielt das Briefträgerproblem durch nach dem chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte. Eine Lösung wurde 1973 durch Jack Edmonds und Ellis L. Johnson angegeben. (de)
- Grafo-teorian, postari txinatarraren ebazkizuna edo bide ikuskapen ebazkizuna noranzkorik gabeko grafo haztatu batean ertz edo lokarri guztiak zeharkatzen dituen ibilbide itxi edo zirkuitu laburrena bilatzeko ebazkizuna da. (eu)
- 中国人郵便配達問題（ちゅうごくじんゆうびんはいたつもんだい、英: Chinese postman problem）とは、グラフ理論における問題の一つであり、以下のように定義される。 Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。 (ja)
- 中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美國國家標準和技術研究院（NIST）的 Alan Goldman 首先將此問題命名为中国邮递员问题。 (zh)
- Задача (китайського) листоноші (англ. Chinese postman problem або англ. Route inspection problem) — задача пошуку найкоротшого циклу в графі, що включає всі ребра. Існують варіанти задачі для орієнтованих та неорієнтованих графів та для графів, частина ребер яких орієнтована, а частина — ні. Задача отримала назву завдяки Алану Голдману (англ. Alan Goldman) з NIST, оскільки першим дослідником цієї задачі був китайський математик (англ. Mei-Ku Kuan, 1962). (uk)
- In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time. (en)
- En teoría de grafos (una rama de la matemática), el problema del cartero chino (PCC), o problema del circuito del cartero, o problema de la inspección y selección de rutas, consiste en encontrar el camino más corto o circuito cerrado, que visite cada arista de un grafo (conectado) no direccionado, o sea, que pase al menos una vez por cada arista del grafo, volviendo al punto (o nodo) de partida. Cuando el grafo posee un circuito euleriano (un paseo cerrado que alcance toda arista solamente una vez), ese circuito es una solución óptima. (es)
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. (fr)
- Il problema del postino cinese è un problema della teoria dei grafi formulato dal matematico cinese Mei-Ku Kwan (o Kuan) nel 1962. Consiste nella creazione di un cammino ciclico di lunghezza minima in un grafo non orientato che ne attraversi tutti i suoi archi. Il nome del problema ("postino cinese") fu coniato da Alan Goldman del NIST. In un grafo euleriano, la soluzione è rappresentata da un cammino euleriano, e la lunghezza del cammino più corto equivale al numero degli archi presenti. Costruzione di grafo euleriano ottenuta a partire dal grafo precedente (it)
- Problem chińskiego listonosza (ang. Chinese postman problem, route inspection problem) – zadanie znalezienia ścieżki zamkniętej (wracającej do wierzchołka początkowego), zawierającej każdą krawędź grafu co najmniej raz i mającej minimalny koszt (sumę wag krawędzi). Problem został pierwszy raz sformułowany w 1962 roku w języku chińskim. (pl)
- Het Chinese postbodeprobleem is een veelgebruikte metafoor om een bekende probleemstelling in de grafentheorie duidelijk te maken. Een postbode moet brieven bezorgen in een bepaalde stad. Hij moet daarbij vertrekken vanuit het postkantoor, alle straten doorlopen om vervolgens weer in het postkantoor te eindigen. Daarbij is het de bedoeling om de totaal afgelegde afstand minimaal te houden. Vertaald naar de grafentheorie komt dit hierop neer: zoek de kortst mogelijke route in een ongerichte graaf die vertrekt en eindigt in dezelfde knoop, en die alle verbindingen in de graaf bevat. (nl)
- Em teoria dos grafos, um ramo da matemática, o problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma solução ótima. (pt)
- Задача китайского почтальона (англ. Chinese postman problem, CPP), маршрут почтальона или задача инспекции дорог заключается в поиске кратчайшего замкнутого пути или цикла, который проходит через каждое ребро (связного) взвешенного неориентированного графа. Если граф имеет эйлеров цикл (замкнутый маршрут, который проходит любое ребро ровно один раз), тогда этот цикл служит оптимальным решением. В противном случае задачей оптимизации является поиск наименьшего числа рёбер графа с повторными проходами (или подмножество рёбер с минимальным возможным общим весом), так что получающийся мультиграф имеет эйлеров цикл. Эта задача может быть решена за полиномиальное время. (ru)
|
| rdfs:label
|
- Problém čínského listonoše (cs)
- Briefträgerproblem (de)
- Problema del cartero chino (es)
- Chinese postman problem (en)
- Postari txinatarraren ebazkizun (eu)
- Problema del postino cinese (it)
- Problème du postier chinois (fr)
- 中国人郵便配達問題 (ja)
- Chinees postbodeprobleem (nl)
- Problem chińskiego listonosza (pl)
- Problema da inspeção de rotas (pt)
- Задача китайского почтальона (ru)
- Задача листоноші (uk)
- 中国邮递员问题 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
