1473:. This idea is due to László Mérō and is now known as pathmax. Contrary to common belief, pathmax does not turn an admissible heuristic into a consistent heuristic. For example, if A* uses pathmax and a heuristic that is admissible but not consistent, it is not guaranteed to have an optimal path to a node when it is first expanded.
814:
539:
620:
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
1183:, then A* is equivalent to best-first search on that graph using Dijkstra's algorithm. In the unusual event that an admissible heuristic is not consistent, a node will need repeated expansion every time a new best (so-far) cost is achieved for it.
1306:
997:
803:
288:
615:
1161:
899:
1471:
135:
698:
283:
173:
655:
1051:
1024:
1358:
1398:
1378:
1329:
1204:
1181:
39:, 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.
1064:, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that
285:
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,
1206:
is admissible but not consistent, one can artificially force the heuristic values along a path to be monotonically non-decreasing by using
1600:
221:
will give an estimate that, accounting for the cost to reach the next node, is always lesser than or equal to the estimate at node
904:
1556:
703:
534:{\displaystyle h(N_{i+1})\leq c(N_{i+1},N_{i})+h(N_{i})\leq c(N_{i+1},N_{i})+c(N_{i},N_{i-1})+...+c(N_{1},N_{0})+h(N_{0})}
1212:
1531:
544:
824:
1075:
47:
75:
1403:
1501:
821:
Consistent heuristics are called monotone because the estimated final cost of a partial solution,
660:
1065:
24:
246:
237:
142:
624:
1608:
1069:
617:, so any consistent heuristic is also admissible since it is upperbounded by the true cost.
20:
817:
Comparison of an admissible but inconsistent and a consistent heuristic evaluation function.
1482:
1029:
1002:
229:
1334:
236:, however, is not always true). Assuming non negative edges, this can be easily proved by
8:
1634:
1061:
1054:
1383:
1363:
1314:
1189:
1166:
28:
1585:
1552:
1527:
1520:
1581:
233:
1572:
Mérō, László (1984). "A Heuristic Search
Algorithm with Modifiable Estimate".
1628:
1605:
Proceedings of the Third Annual
Symposium on Combinatorial Search (SoCS)
813:
541:
by expansion of each term. The given terms are equal to the true cost,
1522:
Heuristics: Intelligent Search
Strategies for Computer Problem Solving
1072:(no negative cost edges). In fact, if the search graph is given cost
232:, i.e. it never overestimates the cost of reaching the goal (the
1053:. It's necessary and sufficient for a heuristic to obey the
992:{\displaystyle g(N_{j})=\sum _{i=2}^{j}c(N_{i-1},N_{i})}
901:
is monotonically non-decreasing along any path, where
1406:
1386:
1366:
1337:
1317:
1215:
1192:
1169:
1078:
1032:
1005:
907:
827:
706:
663:
627:
547:
291:
249:
145:
78:
798:{\displaystyle h(N_{i-1})=h(N_{i})-c(N_{i},N_{i-1})}
1601:"Common Misconceptions Concerning Heuristic Search"
1519:
1465:
1392:
1372:
1352:
1323:
1301:{\displaystyle h'(P)\gets \max(h(P),h'(N)-c(N,P))}
1300:
1198:
1175:
1155:
1045:
1018:
991:
893:
797:
692:
649:
609:
533:
277:
167:
129:
65:plus the estimated cost of reaching the goal from
1626:
1236:
1546:
808:
610:{\displaystyle \sum _{i=1}^{n}c(N_{i},N_{i-1})}
61:is no greater than the step cost of getting to
57:, the estimated cost of reaching the goal from
1592:
999:is the cost of the best path from start node
1540:
211:c(N,P) is the cost of reaching node P from N
1547:Edelkamp, Stefan; Schrödl, Stefan (2012).
1502:"Designing & Understanding Heuristics"
894:{\displaystyle f(N_{j})=g(N_{j})+h(N_{j})}
16:Type of heuristic in path-finding problems
1549:Heuristic Search: Theory and Applications
164:
1156:{\displaystyle c'(N,P)=c(N,P)+h(P)-h(N)}
812:
1627:
1598:
1517:
1571:
187:is the consistent heuristic function
130:{\displaystyle h(N)\leq c(N,P)+h(P)}
1565:
13:
1466:{\displaystyle h'(start)=h(start)}
1380:is the node immediately preceding
14:
1646:
228:A consistent heuristic is also
1511:
1494:
1460:
1442:
1433:
1415:
1347:
1341:
1295:
1292:
1280:
1271:
1265:
1251:
1245:
1239:
1233:
1230:
1224:
1150:
1144:
1135:
1129:
1120:
1108:
1099:
1087:
986:
954:
924:
911:
888:
875:
866:
853:
844:
831:
792:
760:
751:
738:
729:
710:
687:
674:
657:becomes at most the true cost
644:
631:
604:
572:
528:
515:
506:
480:
459:
427:
418:
386:
377:
364:
355:
323:
314:
295:
266:
253:
155:
149:
124:
118:
109:
97:
88:
82:
1:
1488:
1586:10.1016/0004-3702(84)90003-1
809:Consequences of monotonicity
693:{\displaystyle h^{*}(N_{i})}
7:
1476:
1311:as the heuristic value for
1057:in order to be consistent.
10:
1651:
278:{\displaystyle h(N_{0})=0}
168:{\displaystyle h(G)=0.\,}
42:Formally, for every node
1068:requires in solving the
650:{\displaystyle h(N_{i})}
193:is any node in the graph
1574:Artificial Intelligence
1186:If the given heuristic
217:Informally, every node
25:artificial intelligence
1599:Holte, Robert (2005).
1467:
1394:
1374:
1354:
1325:
1302:
1200:
1177:
1157:
1047:
1020:
993:
950:
895:
818:
799:
694:
651:
611:
568:
535:
279:
169:
131:
1518:Pearl, Judea (1984).
1468:
1395:
1375:
1355:
1326:
1303:
1201:
1178:
1158:
1070:shortest path problem
1048:
1046:{\displaystyle N_{j}}
1021:
1019:{\displaystyle N_{1}}
994:
930:
896:
816:
800:
695:
652:
612:
548:
536:
280:
199:is any descendant of
170:
132:
21:path-finding problems
1483:Admissible heuristic
1404:
1384:
1364:
1353:{\displaystyle h(P)}
1335:
1315:
1213:
1190:
1167:
1076:
1066:Dijkstra's algorithm
1030:
1003:
905:
825:
704:
661:
625:
545:
289:
247:
143:
76:
1551:. Morgan Kaufmann.
1062:A* search algorithm
1055:triangle inequality
1526:. Addison-Wesley.
1463:
1390:
1370:
1350:
1321:
1298:
1196:
1173:
1153:
1043:
1016:
989:
891:
819:
795:
690:
647:
607:
531:
275:
165:
127:
29:heuristic function
1558:978-0-12-372512-7
1393:{\displaystyle P}
1373:{\displaystyle N}
1324:{\displaystyle P}
1199:{\displaystyle h}
1176:{\displaystyle h}
1163:for a consistent
1642:
1620:
1619:
1617:
1616:
1607:. Archived from
1596:
1590:
1589:
1569:
1563:
1562:
1544:
1538:
1537:
1525:
1515:
1509:
1508:
1506:
1498:
1472:
1470:
1469:
1464:
1414:
1400:on the path and
1399:
1397:
1396:
1391:
1379:
1377:
1376:
1371:
1359:
1357:
1356:
1351:
1330:
1328:
1327:
1322:
1307:
1305:
1304:
1299:
1264:
1223:
1205:
1203:
1202:
1197:
1182:
1180:
1179:
1174:
1162:
1160:
1159:
1154:
1086:
1052:
1050:
1049:
1044:
1042:
1041:
1025:
1023:
1022:
1017:
1015:
1014:
998:
996:
995:
990:
985:
984:
972:
971:
949:
944:
923:
922:
900:
898:
897:
892:
887:
886:
865:
864:
843:
842:
804:
802:
801:
796:
791:
790:
772:
771:
750:
749:
728:
727:
699:
697:
696:
691:
686:
685:
673:
672:
656:
654:
653:
648:
643:
642:
616:
614:
613:
608:
603:
602:
584:
583:
567:
562:
540:
538:
537:
532:
527:
526:
505:
504:
492:
491:
458:
457:
439:
438:
417:
416:
404:
403:
376:
375:
354:
353:
341:
340:
313:
312:
284:
282:
281:
276:
265:
264:
208:is any goal node
174:
172:
171:
166:
136:
134:
133:
128:
19:In the study of
1650:
1649:
1645:
1644:
1643:
1641:
1640:
1639:
1625:
1624:
1623:
1614:
1612:
1597:
1593:
1570:
1566:
1559:
1545:
1541:
1534:
1516:
1512:
1504:
1500:
1499:
1495:
1491:
1479:
1407:
1405:
1402:
1401:
1385:
1382:
1381:
1365:
1362:
1361:
1336:
1333:
1332:
1316:
1313:
1312:
1257:
1216:
1214:
1211:
1210:
1191:
1188:
1187:
1168:
1165:
1164:
1079:
1077:
1074:
1073:
1037:
1033:
1031:
1028:
1027:
1010:
1006:
1004:
1001:
1000:
980:
976:
961:
957:
945:
934:
918:
914:
906:
903:
902:
882:
878:
860:
856:
838:
834:
826:
823:
822:
811:
780:
776:
767:
763:
745:
741:
717:
713:
705:
702:
701:
681:
677:
668:
664:
662:
659:
658:
638:
634:
626:
623:
622:
592:
588:
579:
575:
563:
552:
546:
543:
542:
522:
518:
500:
496:
487:
483:
447:
443:
434:
430:
412:
408:
393:
389:
371:
367:
349:
345:
330:
326:
302:
298:
290:
287:
286:
260:
256:
248:
245:
244:
144:
141:
140:
77:
74:
73:
17:
12:
11:
5:
1648:
1638:
1637:
1622:
1621:
1591:
1564:
1557:
1539:
1532:
1510:
1492:
1490:
1487:
1486:
1485:
1478:
1475:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1413:
1410:
1389:
1369:
1349:
1346:
1343:
1340:
1320:
1309:
1308:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1263:
1260:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1222:
1219:
1195:
1172:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1085:
1082:
1040:
1036:
1013:
1009:
988:
983:
979:
975:
970:
967:
964:
960:
956:
953:
948:
943:
940:
937:
933:
929:
926:
921:
917:
913:
910:
890:
885:
881:
877:
874:
871:
868:
863:
859:
855:
852:
849:
846:
841:
837:
833:
830:
810:
807:
794:
789:
786:
783:
779:
775:
770:
766:
762:
759:
756:
753:
748:
744:
740:
737:
734:
731:
726:
723:
720:
716:
712:
709:
689:
684:
680:
676:
671:
667:
646:
641:
637:
633:
630:
606:
601:
598:
595:
591:
587:
582:
578:
574:
571:
566:
561:
558:
555:
551:
530:
525:
521:
517:
514:
511:
508:
503:
499:
495:
490:
486:
482:
479:
476:
473:
470:
467:
464:
461:
456:
453:
450:
446:
442:
437:
433:
429:
426:
423:
420:
415:
411:
407:
402:
399:
396:
392:
388:
385:
382:
379:
374:
370:
366:
363:
360:
357:
352:
348:
344:
339:
336:
333:
329:
325:
322:
319:
316:
311:
308:
305:
301:
297:
294:
274:
271:
268:
263:
259:
255:
252:
215:
214:
213:
212:
209:
203:
194:
188:
176:
175:
163:
160:
157:
154:
151:
148:
138:
126:
123:
120:
117:
114:
111:
108:
105:
102:
99:
96:
93:
90:
87:
84:
81:
31:is said to be
15:
9:
6:
4:
3:
2:
1647:
1636:
1633:
1632:
1630:
1611:on 2022-08-01
1610:
1606:
1602:
1595:
1587:
1583:
1579:
1575:
1568:
1560:
1554:
1550:
1543:
1535:
1533:0-201-05594-5
1529:
1524:
1523:
1514:
1503:
1497:
1493:
1484:
1481:
1480:
1474:
1457:
1454:
1451:
1448:
1445:
1439:
1436:
1430:
1427:
1424:
1421:
1418:
1411:
1408:
1387:
1367:
1344:
1338:
1318:
1289:
1286:
1283:
1277:
1274:
1268:
1261:
1258:
1254:
1248:
1242:
1227:
1220:
1217:
1209:
1208:
1207:
1193:
1184:
1170:
1147:
1141:
1138:
1132:
1126:
1123:
1117:
1114:
1111:
1105:
1102:
1096:
1093:
1090:
1083:
1080:
1071:
1067:
1063:
1058:
1056:
1038:
1034:
1011:
1007:
981:
977:
973:
968:
965:
962:
958:
951:
946:
941:
938:
935:
931:
927:
919:
915:
908:
883:
879:
872:
869:
861:
857:
850:
847:
839:
835:
828:
815:
806:
787:
784:
781:
777:
773:
768:
764:
757:
754:
746:
742:
735:
732:
724:
721:
718:
714:
707:
682:
678:
669:
665:
639:
635:
628:
618:
599:
596:
593:
589:
585:
580:
576:
569:
564:
559:
556:
553:
549:
523:
519:
512:
509:
501:
497:
493:
488:
484:
477:
474:
471:
468:
465:
462:
454:
451:
448:
444:
440:
435:
431:
424:
421:
413:
409:
405:
400:
397:
394:
390:
383:
380:
372:
368:
361:
358:
350:
346:
342:
337:
334:
331:
327:
320:
317:
309:
306:
303:
299:
292:
272:
269:
261:
257:
250:
241:
239:
235:
231:
226:
224:
220:
210:
207:
204:
202:
198:
195:
192:
189:
186:
183:
182:
181:
180:
179:
161:
158:
152:
146:
139:
121:
115:
112:
106:
103:
100:
94:
91:
85:
79:
72:
71:
70:
68:
64:
60:
56:
52:
49:
45:
40:
38:
34:
30:
26:
22:
1613:. Retrieved
1609:the original
1604:
1594:
1577:
1573:
1567:
1548:
1542:
1521:
1513:
1496:
1310:
1185:
1059:
820:
619:
242:
227:
222:
218:
216:
205:
200:
196:
190:
184:
177:
66:
62:
58:
54:
50:
43:
41:
36:
32:
18:
1331:instead of
69:. That is:
1635:Heuristics
1615:2019-07-10
1489:References
700:, we make
230:admissible
33:consistent
1580:: 13–27.
1275:−
1234:←
1139:−
966:−
932:∑
785:−
755:−
722:−
670:∗
597:−
550:∑
452:−
381:≤
318:≤
238:induction
92:≤
48:successor
46:and each
1629:Category
1477:See also
1412:′
1360:, where
1262:′
1221:′
1084:′
234:converse
37:monotone
1060:In the
1555:
1530:
178:where
1505:(PDF)
35:, or
1553:ISBN
1528:ISBN
243:Let
27:, a
1582:doi
1237:max
1026:to
223:i+1
137:and
53:of
23:in
1631::
1603:.
1578:23
1576:.
805:.
240:.
225:.
162:0.
1618:.
1588:.
1584::
1561:.
1536:.
1507:.
1461:)
1458:t
1455:r
1452:a
1449:t
1446:s
1443:(
1440:h
1437:=
1434:)
1431:t
1428:r
1425:a
1422:t
1419:s
1416:(
1409:h
1388:P
1368:N
1348:)
1345:P
1342:(
1339:h
1319:P
1296:)
1293:)
1290:P
1287:,
1284:N
1281:(
1278:c
1272:)
1269:N
1266:(
1259:h
1255:,
1252:)
1249:P
1246:(
1243:h
1240:(
1231:)
1228:P
1225:(
1218:h
1194:h
1171:h
1151:)
1148:N
1145:(
1142:h
1136:)
1133:P
1130:(
1127:h
1124:+
1121:)
1118:P
1115:,
1112:N
1109:(
1106:c
1103:=
1100:)
1097:P
1094:,
1091:N
1088:(
1081:c
1039:j
1035:N
1012:1
1008:N
987:)
982:i
978:N
974:,
969:1
963:i
959:N
955:(
952:c
947:j
942:2
939:=
936:i
928:=
925:)
920:j
916:N
912:(
909:g
889:)
884:j
880:N
876:(
873:h
870:+
867:)
862:j
858:N
854:(
851:g
848:=
845:)
840:j
836:N
832:(
829:f
793:)
788:1
782:i
778:N
774:,
769:i
765:N
761:(
758:c
752:)
747:i
743:N
739:(
736:h
733:=
730:)
725:1
719:i
715:N
711:(
708:h
688:)
683:i
679:N
675:(
666:h
645:)
640:i
636:N
632:(
629:h
605:)
600:1
594:i
590:N
586:,
581:i
577:N
573:(
570:c
565:n
560:1
557:=
554:i
529:)
524:0
520:N
516:(
513:h
510:+
507:)
502:0
498:N
494:,
489:1
485:N
481:(
478:c
475:+
472:.
469:.
466:.
463:+
460:)
455:1
449:i
445:N
441:,
436:i
432:N
428:(
425:c
422:+
419:)
414:i
410:N
406:,
401:1
398:+
395:i
391:N
387:(
384:c
378:)
373:i
369:N
365:(
362:h
359:+
356:)
351:i
347:N
343:,
338:1
335:+
332:i
328:N
324:(
321:c
315:)
310:1
307:+
304:i
300:N
296:(
293:h
273:0
270:=
267:)
262:0
258:N
254:(
251:h
219:i
206:G
201:N
197:P
191:N
185:h
159:=
156:)
153:G
150:(
147:h
125:)
122:P
119:(
116:h
113:+
110:)
107:P
104:,
101:N
98:(
95:c
89:)
86:N
83:(
80:h
67:P
63:P
59:N
55:N
51:P
44:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
