| dbo:abstract
|
- In computer science and graph theory, the Canadian traveller problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable. In other words, the graph is revealed while it is being explored, and explorative edges are charged even if they do not contribute to the final path. This optimization problem was introduced by Christos Papadimitriou and Mihalis Yannakakis in 1989 and a number of variants of the problem have been studied since. The name supposedly originates from conversations of the authors who learned of a difficulty Canadian drivers had: traveling a network of cities with snowfall randomly blocking roads. The stochastic version, where each edge is associated with a probability of independently being in the graph, has been given considerable attention in operations research under the name "the Stochastic Shortest Path Problem with Recourse" (SSPPR). (en)
- Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы. Другими словами, граф раскрывается по мере его изучения, а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути. Эту задачу оптимизации предложили в 1989 году Христос Пападимитриу и Михалис Яннакакис и с тех пор было изучено много её вариантов. Название, предположительно, возникло из разговора авторов, обсуждавших проблемы канадских водителей, регулярно попадающих на заблокированные в результате снегопада улицы. Стохастическая версия, где каждое ребро ассоциировано с вероятностью принадлежать графу, получила особое внимание в исследовании операций под именем «Стохастическая задача о кратчайшем пути с рекурсией» (англ. Stochastic Shortest Path Problem with Recourse, SSPPR). (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11256 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science and graph theory, the Canadian traveller problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable. In other words, the graph is revealed while it is being explored, and explorative edges are charged even if they do not contribute to the final path. (en)
- Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы. Другими словами, граф раскрывается по мере его изучения, а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути. (ru)
|
| rdfs:label
|
- Canadian traveller problem (en)
- Задача канадского путешественника (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
