Consistent heuristic (original) (raw)
In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour. Formally, for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. That is: and where
| Property | Value |
|---|---|
| dbo:abstract | In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour. Formally, for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. That is: and where * h is the consistent heuristic function * N is any node in the graph * P is any descendant of N * G is any goal node * c(N,P) is the cost of reaching node P from N Informally, every node i will give an estimate that, accounting for the cost to reach the next node, is always lesser than the estimate at node i+1. A consistent heuristic is also admissible, i.e. it never overestimates the cost of reaching the goal (the converse, however, is not always true). Assuming non negative edges, this can be easily proved by induction. Let be the estimated cost for the goal node. This implies that the base condition is trivially true as 0 ≤ 0. Since the heuristic is consistent, . The given terms are equal to the true cost, , so any consistent heuristic is also admissible since it is upperbounded by the true cost. The converse is clearly not true as we can always construct a heuristic that is always below the true cost but is nevertheless inconsistent by, for instance, increasing the heuristic estimate from the farthest node as we get closer and, when the estimate becomes at most the true cost , we make . (en) У задачах на пошук шляху за допомогою штучного інтелекту, узгоджена (або монотонна) евристична функція — це функція, яка оцінює відстань від певного стану до цільового стану, і при цьому оцінена відстань не більша ніж оцінена відстань від будь-якого з сусідніх станів плюс ціна кроку до цього сусіда. Формально, для кожного вузла N і кожного його можливого наступника P утвореного будь-якою дією a, оцінена ціна досягнення цілі з N є не більшою ніж ціна кроку діставання до P плюс оцінена ціна досягнення цілі з P. Інакше кажучи: і де * h — узгоджена увристична функція * N — будь-який вузол у графі * P — будь-який спадкоємець N * G — будь-який цільовий вузол * c(N,P) — ціна діставання від P до N Узгоджена евристика також прийнятна, тобто вона ніколи не переоцінює ціну досягнення цілі (зворотнє не завжди правильно!). Це доведено за допомогою індукції по довжині накращого шляху від вузла до цілі. За припущенням, де позначає ціну найкоротшого шляху з n до цілі. Отже, , роблячи її прийнятною. ( є будь-яким вузлом чий найкращий шлях до цілі має довжину m+1, пролягає через деякий безпосередньо дочірній вузол чий найкращий шлях до цілі має довжину m.) Однак, прийнятну евристику майже завжди можна перетворити в узгоджену евристику, , через таке підлаштування: (Відоме як рівняння pathmax) Хоча це й можливо отримати прийнятну і неузгоджену евристику, але це потребувало б багато зусиль. Багато дослідників працюють із припущенням, що майже всі прийнятні евристики є узгодженими. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Heuristics_Comparison.png?width=300 |
| dbo:wikiPageID | 9304783 (xsd:integer) |
| dbo:wikiPageLength | 5580 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116114302 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mathematical_induction dbr:Converse_(logic) dbr:Shortest_path_problem dbr:Successor_(graph_theory) dbr:Admissible_heuristic dbc:Heuristics dbr:Triangle_inequality dbr:A*_search_algorithm dbr:Artificial_intelligence dbr:Dijkstra's_algorithm dbr:Heuristic_function dbr:File:Heuristics_Comparison.png |
| dct:subject | dbc:Heuristics |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Event100029378 yago:Heuristic105847956 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatHeuristics yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour. Formally, for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. That is: and where (en) У задачах на пошук шляху за допомогою штучного інтелекту, узгоджена (або монотонна) евристична функція — це функція, яка оцінює відстань від певного стану до цільового стану, і при цьому оцінена відстань не більша ніж оцінена відстань від будь-якого з сусідніх станів плюс ціна кроку до цього сусіда. Формально, для кожного вузла N і кожного його можливого наступника P утвореного будь-якою дією a, оцінена ціна досягнення цілі з N є не більшою ніж ціна кроку діставання до P плюс оцінена ціна досягнення цілі з P. Інакше кажучи: і де , (Відоме як рівняння pathmax) (uk) |
| rdfs:label | Consistent heuristic (en) Узгоджена евристика (uk) |
| owl:sameAs | freebase:Consistent heuristic yago-res:Consistent heuristic wikidata:Consistent heuristic dbpedia-uk:Consistent heuristic https://global.dbpedia.org/id/4iJrb |
| prov:wasDerivedFrom | wikipedia-en:Consistent_heuristic?oldid=1116114302&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Heuristics_Comparison.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Consistent_heuristic |
| is dbo:wikiPageWikiLink of | dbr:Glossary_of_artificial_intelligence dbr:Shortest_path_problem dbr:Admissible_heuristic dbr:A*_search_algorithm dbr:Dijkstra's_algorithm dbr:Consistency_(disambiguation) |
| is foaf:primaryTopic of | wikipedia-en:Consistent_heuristic |
