| http://dbpedia.org/ontology/abstract
|
In computer science and graph theory, the … 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).rtest Path Problem with Recourse" (SSPPR).
, Задача канадского путешественника (ЗКП) (а … Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы. Другими словами, граф раскрывается по мере его изучения, а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути. Эту задачу оптимизации предложили в 1989 году Христос Пападимитриу и Михалис Яннакакис и с тех пор было изучено много её вариантов. Название, предположительно, возникло из разговора авторов, обсуждавших проблемы канадских водителей, регулярно попадающих на заблокированные в результате снегопада улицы. Стохастическая версия, где каждое ребро ассоциировано с вероятностью принадлежать графу, получила особое внимание в исследовании операций под именем «Стохастическая задача о кратчайшем пути с рекурсией» (англ. Stochastic Shortest Path Problem with Recourse, SSPPR).ortest Path Problem with Recourse, SSPPR).
|
| http://dbpedia.org/ontology/wikiPageID
|
18210373
|
| http://dbpedia.org/ontology/wikiPageLength
|
11256
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1123137924
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Competitive_ratio +
, http://dbpedia.org/resource/Artificial_intelligence +
, http://dbpedia.org/resource/Worst_case +
, http://dbpedia.org/resource/Hitting_time +
, http://dbpedia.org/resource/Category:Computational_problems_in_graph_theory +
, http://dbpedia.org/resource/Powerset +
, http://dbpedia.org/resource/Sharp_P +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Machine_learning +
, http://dbpedia.org/resource/Category:PSPACE-complete_problems +
, http://dbpedia.org/resource/APX +
, http://dbpedia.org/resource/PSPACE-complete +
, http://dbpedia.org/resource/Graph_traversal +
, http://dbpedia.org/resource/Glossary_of_graph_theory +
, http://dbpedia.org/resource/Springer-Verlag +
, http://dbpedia.org/resource/A_priori_and_a_posteriori +
, http://dbpedia.org/resource/Canadians +
, http://dbpedia.org/resource/Game_theory +
, http://dbpedia.org/resource/Optimization_problem +
, http://dbpedia.org/resource/Christos_Papadimitriou +
, http://dbpedia.org/resource/Computer_science +
, http://dbpedia.org/resource/Category:Travelling_salesman_problem +
, http://dbpedia.org/resource/Mihalis_Yannakakis +
, http://dbpedia.org/resource/Sharp-P +
, http://dbpedia.org/resource/Shortest_path_problem +
, http://dbpedia.org/resource/Operations_research +
, http://dbpedia.org/resource/Average_case +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Cite_document +
, http://dbpedia.org/resource/Template:Cite_conference +
, http://dbpedia.org/resource/Template:Expand_section +
, http://dbpedia.org/resource/Template:Technical +
, http://dbpedia.org/resource/Template:Cite_journal +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:PSPACE-complete_problems +
, http://dbpedia.org/resource/Category:Travelling_salesman_problem +
, http://dbpedia.org/resource/Category:Computational_problems_in_graph_theory +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Generalization +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Canadian_traveller_problem?oldid=1123137924&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Canadian_traveller_problem +
|
| owl:sameAs |
http://fa.dbpedia.org/resource/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D9%85%D8%B3%D8%A7%D9%81%D8%B1_%DA%A9%D8%A7%D9%86%D8%A7%D8%AF%D8%A7%DB%8C%DB%8C +
, http://yago-knowledge.org/resource/Canadian_traveller_problem +
, https://global.dbpedia.org/id/4ewpG +
, http://www.wikidata.org/entity/Q5030897 +
, http://dbpedia.org/resource/Canadian_traveller_problem +
, http://ru.dbpedia.org/resource/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%B0%D0%BD%D0%B0%D0%B4%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%BF%D1%83%D1%82%D0%B5%D1%88%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B8%D0%BA%D0%B0 +
, http://rdf.freebase.com/ns/m.04ctl_b +
|
| rdf:type |
http://dbpedia.org/class/yago/Difficulty114408086 +
, http://dbpedia.org/class/yago/Algorithm105847438 +
, http://dbpedia.org/class/yago/Procedure101023820 +
, http://dbpedia.org/class/yago/Activity100407535 +
, http://dbpedia.org/class/yago/Event100029378 +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
, http://dbpedia.org/class/yago/Act100030358 +
, http://dbpedia.org/class/yago/Condition113920835 +
, http://dbpedia.org/class/yago/WikicatPSPACE-completeProblems +
, http://dbpedia.org/class/yago/Problem114410605 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/class/yago/WikicatComputationalProblemsInGraphTheory +
, http://dbpedia.org/class/yago/WikicatGraphAlgorithms +
, http://dbpedia.org/class/yago/Attribute100024264 +
, http://dbpedia.org/class/yago/State100024720 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Rule105846932 +
|
| rdfs:comment |
Задача канадского путешественника (ЗКП) (а … Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы. Другими словами, граф раскрывается по мере его изучения, а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути.же если они не принадлежат конечному пути.
, In computer science and graph theory, the … 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. they do not contribute to the final path.
|
| rdfs:label |
Задача канадского путешественника
, Canadian traveller problem
|
