{"entities":{"Q685539":{"pageid":687388,"ns":120,"title":"Item:Q685539","lastrevid":42641707,"modified":"2025-07-07T14:59:52Z","type":"item","id":"Q685539","labels":{"en":{"language":"en","value":"Linear-space best-first search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417431"}},"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":"Q685539$47BCBBB4-2F40-43CE-AD8B-9A6123001C25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d1ea9fc37bd94e409f15e614d33b0e600295caf","datavalue":{"value":{"text":"Linear-space best-first search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685539$5962118F-2FFD-4EC6-8920-2A3EBAE4EDCB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5bd548096a85af821f4b83a3af6d1640c4ed0eca","datavalue":{"value":"0778.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$425F0242-6B06-4144-9CEA-23AA69CA6BA9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"344c1d6dcc72dc5a76e9479d94311a5b18b763d0","datavalue":{"value":"10.1016/0004-3702(93)90045-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$4819DBE9-FEF4-481D-A09B-976FE9B2746D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"873c1941d921f032fdf9046ecf96aed64804fe9b","datavalue":{"value":{"entity-type":"item","numeric-id":235375,"id":"Q235375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$20132273-F0D4-4FF8-9E07-B55973E81AF5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$BCCCADFB-26FB-4CD1-B549-C9BF87102967","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a626d589150434ddedb6dea454b02c574516fd1d","datavalue":{"value":{"time":"+1994-01-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685539$A2F78815-756B-47BF-871E-BB1CAC8563DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5230ecda5b719548f6a2669b16466e69d742ad97","datavalue":{"value":"Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, \\textit{Dijkstra}'s single-source shortest-path algorithm, and the \\(A^*\\) algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do not expand nodes in best- first if the cost function can decrease along a path. We present a linear-space best-first search algorithm (RBFS) that always explores new nodes in best-first order, regardless of the cost function, and expands fewer nodes than iterative deepening with a nondecreasing cost function. On the sliding-tile puzzles, RBFS with a nonmonotonic weighted evaluation function dramatically reduces computation time with only a small penalty in solution cost. In general, RBFS reduces the space complexity of best- first search from exponential to linear, at the cost of only a constant factor in time complexity in our experiments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685539$2EA2F35E-0068-4635-8979-44B0EF58163B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$83739A3F-C83C-42A8-84D4-DDCAD8D095BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$1686D774-5627-4B58-82B5-5FEFE9386737","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a1eb9f517bee5749a35ef0ac5357794a861962ee","datavalue":{"value":"417431","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$9FD13A5A-9BE1-463D-9807-C0DCAE862FA2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"877fec54565dbac59617c065b95b230bc44e33b3","datavalue":{"value":"Best-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q685539$17B66D43-4722-4EA0-9B62-B0FC1281C6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19b6ba98ff19f3860dca8d7a4e1436857f3fff49","datavalue":{"value":"heuristic search","type":"string"},"datatype":"string"},"type":"statement","id":"Q685539$AFEDF8AC-C040-4E1C-957B-8B4B194F639C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8ed407681407c1a56fe5b3313866a6cafcadd38","datavalue":{"value":"linear-space","type":"string"},"datatype":"string"},"type":"statement","id":"Q685539$C556801F-0878-4AB1-9910-B403EEF8FCCC","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":"Q685539$39864791-76A2-4864-9441-4233A60F80AD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5c4bd3590ca49c99159d3a7bd90a9f9b25220570","datavalue":{"value":"Q88963605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$BBC03381-D1EF-4BCF-8517-F506B9BD68E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"583f9b68893c77c87de93c60c31a63a3d9c2fd05","datavalue":{"value":{"entity-type":"item","numeric-id":3735050,"id":"Q3735050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$8B364BFE-821C-4E63-8948-934DFF390D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"721476372186597fdb291188957347cd47a79e12","datavalue":{"value":{"entity-type":"item","numeric-id":1263290,"id":"Q1263290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$EFE9DF26-9E0B-481E-8EA1-9F625209194B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c96fb590a8a14ff5629ca877091a92ef28bc5c3","datavalue":{"value":{"entity-type":"item","numeric-id":3768428,"id":"Q3768428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$BBC994CF-002B-4C62-BA30-C9A7DDF66D65","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":"Q685539$B22CA72B-FF0C-4AF0-A084-08BB8BBADB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$C7F6F693-0860-4640-B037-CAFFB6F0633F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1f0b5c5d1ef7da893967c1b74defc4984f71dee","datavalue":{"value":{"entity-type":"item","numeric-id":1062761,"id":"Q1062761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$0B030A5A-1A0C-48A0-B545-5B71D91ABD24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5e962078ce73e91a0af0844091c4c5e70af651e","datavalue":{"value":{"entity-type":"item","numeric-id":2639648,"id":"Q2639648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$6E0B2950-494C-40CF-8FFB-1C759CBF1005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83032ead213a65cd81335d927bee6d5ce21c2490","datavalue":{"value":{"entity-type":"item","numeric-id":1354042,"id":"Q1354042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$6214222C-A245-4071-B196-783806AEDE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63246c1bfd916b7347bc2a4bda01d853cb6c06a7","datavalue":{"value":{"entity-type":"item","numeric-id":2542693,"id":"Q2542693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$6E26995D-D7A3-4D85-954E-C03410987B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b28fc56f37d0e5db9ef3237e83a36a85de5deaba","datavalue":{"value":{"entity-type":"item","numeric-id":3491026,"id":"Q3491026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$F4A1821A-95B8-48F6-9AE8-BEA2FE1CC61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e44edec21c2364c7ff38b1ffa3f79c93924bd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1187216,"id":"Q1187216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$BD504B92-F647-45DB-9C00-CD8778787F38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0a11637efa6d0f3c2082a45485189f1b8ffd081","datavalue":{"value":{"entity-type":"item","numeric-id":3489496,"id":"Q3489496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685539$8DC79C1A-189C-4F3D-B99C-9A553B2897A7","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"61854b860df12d0dd9914cde3c7ed86c9bfa3fce","datavalue":{"value":"journals/ai/Korf93","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685539$9AA1431A-E8EB-489F-A45C-0BA261589AA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7760566dfc0c2ef4fc81037dfb3b9accb8b9269","datavalue":{"value":{"entity-type":"item","numeric-id":4282752,"id":"Q4282752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5012b7112b633b51fbf0ed05670635928efb39f4","datavalue":{"value":{"amount":"+0.8905916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$2D8C2BA7-7556-455F-8403-C99C40C14747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edd42a4cb6c10bb914e249a534aac722395f164a","datavalue":{"value":{"entity-type":"item","numeric-id":5917443,"id":"Q5917443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c0f41d7faea44403524ffb9e3829f6e7165c799","datavalue":{"value":{"amount":"+0.8823698","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$D4B098E6-2C95-4CFA-8075-5F342D0C8D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccbb1cf68e69e53f6aa787ce388b303eb690c082","datavalue":{"value":{"entity-type":"item","numeric-id":3359984,"id":"Q3359984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13a091977d5efd5599157a37a488f72e7a1ee5d2","datavalue":{"value":{"amount":"+0.8765378","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$D8220EE4-E65B-44B7-8723-6C49446C48E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f975db72a31659ecb19a71bae1934ea3fc28af80","datavalue":{"value":{"entity-type":"item","numeric-id":1114411,"id":"Q1114411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2b440e373e09a5f8d7e0e331047d91c337cf50c","datavalue":{"value":{"amount":"+0.87290144","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$67390B38-79B4-4D11-84DC-071D1F45C61C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d34544ae9c141a2e210c9beeab934df1e4a967a","datavalue":{"value":{"entity-type":"item","numeric-id":4418392,"id":"Q4418392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db8b89e31b2b0da78d590c5db348657dcc186619","datavalue":{"value":{"amount":"+0.8608968","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$93FEDE69-3BC9-4ECF-8BF9-D221F9F948CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54286e15424768a72221632886f9f50c2cbf802c","datavalue":{"value":{"entity-type":"item","numeric-id":1591152,"id":"Q1591152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1f42d9b3b6d114a00f11470be968b74d19adee1","datavalue":{"value":{"amount":"+0.8564879","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$EE654D2F-8B12-471D-BB36-0B72D9889FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"686caa6cf59fa6d8686f1731548b13161302312c","datavalue":{"value":{"entity-type":"item","numeric-id":2171269,"id":"Q2171269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47fbd47af8bcd9b93587b64f3900689c37ad9607","datavalue":{"value":{"amount":"+0.8536692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$A304296F-A30A-4411-A17B-FF1312AF39D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3f744223b940492b54ad1277e8a052d6a3a09d8","datavalue":{"value":{"entity-type":"item","numeric-id":1101217,"id":"Q1101217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3035b4a2e57e461b9eccb8f30f919dcb381c524","datavalue":{"value":{"amount":"+0.8533954","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685539$D522B1B8-B051-4C6A-8915-6C7349EEE397","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685539","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685539"}}}}}