{"entities":{"Q761039":{"pageid":762888,"ns":120,"title":"Item:Q761039","lastrevid":64170927,"modified":"2026-04-11T18:07:01Z","type":"item","id":"Q761039","labels":{"en":{"language":"en","value":"A result on the computational complexity of heuristic estimates for the \\(A^*\\) algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3887071"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$3CC96C11-9E16-4292-AE1D-CF8CEC29EC04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"850f9ff02caceeea398faf668f98d5fec6acdb49","datavalue":{"value":{"text":"A result on the computational complexity of heuristic estimates for the \\(A^*\\) algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q761039$62E75B19-E7E6-438B-AF5E-AEE0A00C5232","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7a6e7577692e9445d7f3b6a67cd6083f5d1902b","datavalue":{"value":"0556.68013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$DB579732-DB0F-4123-B85B-A3061CCEF9C2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39643f80c4f2c4d0f24ca6f4d4418cda99c9cf98","datavalue":{"value":"10.1016/0020-0255(84)90009-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$90F9ED7D-B91D-45ED-B798-875554E094F0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"360122deef6e82cd7feb2a4032e49e1f17b32482","datavalue":{"value":{"entity-type":"item","numeric-id":702797,"id":"Q702797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$828C22E7-0722-4B69-A3F5-70D8E89375DC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$57ED51F1-510A-42F8-8C40-D569AA1E07CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q761039$87F9E479-9279-4CF9-8F3D-31005957C651","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d984da0ff7a532b1931ea7181c68b790589c3b9e","datavalue":{"value":"The performance of a new heuristic search algorithm is analyzed. The algorithm uses a formal representation (semantic representation) that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of \\(A^*\\), without requiring a human expert to provide it. The heuristic is computed by solving less constrained subproblems (auxiliary problems) of the given problem. The new algorithm is shown to be less efficient than the Dijkstra algorithm, according to the complexity measure ''number of node expansion.'' This proves that it is not efficient to compute heuristics for \\(A^*\\) by solving auxiliary problems with backtracking.","type":"string"},"datatype":"string"},"type":"statement","id":"Q761039$92EF10D4-B7A8-4054-9230-E03785D55826","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$78498517-CA09-447E-A515-F51846086100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$CADD29A3-B73F-40A2-B011-6E282202D2BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c68079811f759911748f9a7c195c1f310f8d18c8","datavalue":{"value":"3887071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$59D423A1-6AE6-4F74-A76E-AECBB8C09AE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80189c63e1dfa18f0d828865788879168d99fc2b","datavalue":{"value":"heuristic search algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q761039$A79C1E7C-7E49-4811-879B-BCEA7712606B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5afb3d0e8f387dda4b2918693ed99255b0de708e","datavalue":{"value":"semantic representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q761039$56A4D639-11E8-4D00-8F9B-71EB169A5D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58d96616ce5734e26f2533718421edfc9394b018","datavalue":{"value":"heuristic evaluation function","type":"string"},"datatype":"string"},"type":"statement","id":"Q761039$3D122AFA-550B-450C-9CCC-42F4A3AF894B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$5C4F3030-54F5-4ACB-97F7-FDC6943B1D7E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4b7e650d7b445299df2125ec016c804980b66e4a","datavalue":{"value":"https://doi.org/10.1016/0020-0255(84)90009-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q761039$D88B8708-B2A0-4059-B0E7-1EE92B5DCC2C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1af48fea6a8fe7394725ccbbbe1f666f5deb4e6b","datavalue":{"value":"W2048550374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761039$465221A0-76E8-4803-9C0F-C81B130887B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b21a7d79ff79f561ad9d7d2fc53dbd039ac7eea2","datavalue":{"value":{"entity-type":"item","numeric-id":5594195,"id":"Q5594195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$DFAA05CA-BE81-47D9-B830-71618750CE6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$50ADACEC-2CCD-43B1-BD34-21F59A9009E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66672bcf0c5b18a6d0eb6d600958e53e4799f9d3","datavalue":{"value":{"entity-type":"item","numeric-id":1232905,"id":"Q1232905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$117705BA-0E1F-427D-9FCB-4906D853E374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b5e55dc0464062c43e31d144e35e78c7868c2e","datavalue":{"value":{"entity-type":"item","numeric-id":1143823,"id":"Q1143823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$0AE70524-4553-41C4-A385-00CBE40C70EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5c9250f55330f5cd1601b40853c61ae72bb2319","datavalue":{"value":{"entity-type":"item","numeric-id":1146526,"id":"Q1146526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$202B181C-BD10-457E-90D5-DEA3CEAC05DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9a872690aae65aa8cbfced9522c07629e0a8e21","datavalue":{"value":{"entity-type":"item","numeric-id":3862380,"id":"Q3862380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$FFFC07AD-DA90-4BB3-BEC1-8752AA864EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7bb6a18ab199f315a56a5139d99c89f6a624745","datavalue":{"value":{"entity-type":"item","numeric-id":5180873,"id":"Q5180873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$F98979B9-D219-4586-A1DA-88623957BBFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7e5b329ed8dddafe42b0a06d000965c54630a55","datavalue":{"value":{"entity-type":"item","numeric-id":1232903,"id":"Q1232903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$4E2BA566-44C4-4F33-ABF0-88651F6B8D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eb2c8bf25e71fadc8773e6f4dcf6365364148f0","datavalue":{"value":{"entity-type":"item","numeric-id":2542412,"id":"Q2542412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$7525950D-79F9-4F6D-B5EE-0697B8BBAA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3c8227370b23a709289df885ca01c57567c658f","datavalue":{"value":{"entity-type":"item","numeric-id":3856120,"id":"Q3856120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$C52408FE-ED93-4072-8641-D67631DCDC41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33e9f6df587cf346d729bfaec1cc91bac17b80f7","datavalue":{"value":{"entity-type":"item","numeric-id":3042449,"id":"Q3042449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$D479297C-4ECC-4E95-B0AF-4AA73005A25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34f5d12f62130aa1a95ec02f0f12280b3370992","datavalue":{"value":{"entity-type":"item","numeric-id":5626306,"id":"Q5626306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$0EBDC779-FB97-486A-A776-EBCF73B77E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7162e5630fb1386e87f2820087e237e4fa539756","datavalue":{"value":{"entity-type":"item","numeric-id":761039,"id":"Q761039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$1E4ED0C7-6BB0-4C64-9E2D-CAA6D9D31301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccacce81d4e166ed1ff31e93c31b6116d857759","datavalue":{"value":{"entity-type":"item","numeric-id":1238643,"id":"Q1238643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761039$54842266-299C-40CB-B954-33849FA2AF22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4392ee0c1ba9a471f343d48b0aad1c92c891b67d","datavalue":{"value":{"entity-type":"item","numeric-id":1193486,"id":"Q1193486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"151eb01450c09fdd458d5434a3628859bc1a5c79","datavalue":{"value":{"amount":"+0.8453371524810791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761039$080559EA-B15E-4583-841D-AF977A7B7C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d5fdbf84ec1d8cb17cfbf12748ec41094e0861","datavalue":{"value":{"entity-type":"item","numeric-id":2770733,"id":"Q2770733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33cc5061dd7ab7617e8e0d3ffa01e447d328de81","datavalue":{"value":{"amount":"+0.8330528736114502","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761039$A4C0FB5E-8E29-4B56-B4E8-08A2CD210242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2fcbd0d37f38c52113bb21a0837116b46f27a5a","datavalue":{"value":{"entity-type":"item","numeric-id":792766,"id":"Q792766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea9f8b170c71fcde43e3c27421944a9e638e7d89","datavalue":{"value":{"amount":"+0.8290446996688843","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761039$07B786AF-156B-41B6-BFBE-7B043655370E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61b019c4e54a55d7a8f3bf1c70f4310c8ffa932","datavalue":{"value":{"entity-type":"item","numeric-id":1354031,"id":"Q1354031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b986abe9e7cb3bce636872b1db7b850b100b849","datavalue":{"value":{"amount":"+0.8019741177558899","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761039$23418378-E3CB-4DD9-8A06-15C3B67138FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f56b7a66b3780f2af2ed964d22cc94a3943000b","datavalue":{"value":{"entity-type":"item","numeric-id":3210918,"id":"Q3210918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15e313d48424c2f6590d9bd5c5d2fa6974631d4d","datavalue":{"value":{"amount":"+0.8006806373596191","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q761039$1E1811B2-A6C0-4E18-B5E0-B667E8C5F301","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A result on the computational complexity of heuristic estimates for the \\(A^*\\) algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_result_on_the_computational_complexity_of_heuristic_estimates_for_the_%5C(A%5E*%5C)_algorithm"}}}}}