{"schema_version":"4ort.packet/1","entity":{"entity_id":"a-search-algorithm","kg_uuid":"dff27591-36f7-4c7f-93bf-168eea80ac24","wikidata_id":"Q277680","name":"A* search algorithm","description":"algorithm used for pathfinding and graph traversal","type":"Place","url":"https://4ort.xyz/entity/a-search-algorithm"},"status":"complete","as_of":{"copy_written_at":"2026-11-19T15:21:57Z","last_source_edit_seen":"2026-07-01T12:14:57Z","stale_possible":false,"claims_refreshed_at":"2026-10-25T07:34:05Z","source_revision":2542395261},"facts":[{"field":"P31","label":"instance of","value":"pathfinding algorithm","value_id":"Q21595855","value_raw":"Q21595855","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P31","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"graph algorithm","value_id":"Q30503704","value_raw":"Q30503704","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P31","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"complete search algorithm","value_id":"Q130370792","value_raw":"Q130370792","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P31","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://cs.stanford.edu/people/eroberts/courses/soco/projects/2003-04/intelligent-search/astar.html","retrieved":"2024-09-27"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"admissible search algorithm","value_id":"Q130370867","value_raw":"Q130370867","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P31","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://ieeexplore.ieee.org/document/10050009","retrieved":"2024-09-27"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"best-first search","value_id":"Q830527","value_raw":"Q830527","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P279","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P577","label":"publication date","value":"1968","value_id":null,"value_raw":"+1968-00-00T00:00:00Z","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P577","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P10","label":"video","value":"Astar progress animation.gif","value_id":null,"value_raw":"Astar progress animation.gif","rank":"normal","current":null,"qualifiers":[{"field":"P2096","label":"media legend","value":"Illustration d'une recherche A* pour trouver le chemin le plus court entre 2 nœuds"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P10","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Peter E. Hart","value_id":"Q7173787","value_raw":"Q7173787","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P61","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Nils John Nilsson","value_id":"Q7037360","value_raw":"Q7037360","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P61","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Bertram Raphael","value_id":"Q4895807","value_raw":"Q4895807","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P61","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P144","label":"based on","value":"Dijkstra's algorithm","value_id":"Q8548","value_raw":"Q8548","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P144","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1343","label":"described by source","value":"Artificial Intelligence: A Modern Approach","value_id":"Q20049394","value_raw":"Q20049394","rank":"normal","current":null,"qualifiers":[{"field":"P304","label":"page(s)","value":"93"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P1343","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1552","label":"has characteristic","value":"optimal","value_id":"Q119984354","value_raw":"Q119984354","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P1552","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://cs.stanford.edu/people/eroberts/courses/soco/projects/2003-04/intelligent-search/astar.html","retrieved":"2024-09-27"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2159","label":"computes solution to","value":"pathfinding","value_id":"Q1969601","value_raw":"Q1969601","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P2159","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2159","label":"computes solution to","value":"shortest path problem","value_id":"Q1058754","value_raw":"Q1058754","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P2159","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2283","label":"uses","value":"graph data structure","value_id":"Q2479726","value_raw":"Q2479726","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P2283","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"\\mathcal{O}(|A|log(|S|)) = \\mathcal{O}(b^d)","value_id":null,"value_raw":"\\mathcal{O}(|A|log(|S|)) = \\mathcal{O}(b^d)","rank":"normal","current":null,"qualifiers":[{"field":"P518","label":"applies to part","value":"patch release"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P3752","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"\\mathcal{O}(2^{|S|})","value_id":null,"value_raw":"\\mathcal{O}(2^{|S|})","rank":"normal","current":null,"qualifiers":[{"field":"P518","label":"applies to part","value":"prime version"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P3752","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://doi.org/10.1016/0004-3702(77)90002-9"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3755","label":"worst-case space complexity","value":"\\mathcal{O}(|S|) = \\mathcal{O}(b^d)","value_id":null,"value_raw":"\\mathcal{O}(|S|) = \\mathcal{O}(b^d)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P3755","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P4969","label":"derivative work","value":"jump point search","value_id":"Q17037441","value_raw":"Q17037441","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P4969","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5047","label":"Rosetta Code page ID","value":"A*_search_algorithm","value_id":null,"value_raw":"A*_search_algorithm","rank":"normal","current":null,"qualifiers":[{"field":"P9675","label":"MediaWiki page ID","value":"11535"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P5047","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"103578098","value_id":null,"value_raw":"103578098","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P6366","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6564","label":"Brilliant Wiki ID","value":"a-star-search","value_id":null,"value_raw":"a-star-search","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P6564","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P8669","label":"Encyclopaedia Beliana ID","value":"algoritmus-1","value_id":null,"value_raw":"algoritmus-1","rank":"normal","current":null,"qualifiers":[{"field":"P407","label":"language of work or name","value":"Slovak"},{"field":"P577","label":"publication date","value":"1999-08"},{"field":"P813","label":"retrieved","value":"2026-01-22"},{"field":"P1810","label":"subject named as","value":"algoritmus A*"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P8669","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P12946","label":"FOLDOC ID","value":"A*+search","value_id":null,"value_raw":"A*+search","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q277680#P12946","source_edition":"2026-10-25T07:34:05Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P279","P577","P10","P61","P144","P1343","P1552","P2159","P2283","P3752","P3755","P4969","P5047","P6366","P6564","P8669","P12946"]}],"routes":{"entity_page":"https://4ort.xyz/entity/a-search-algorithm","packet_api":"https://4ort.xyz/api/v1/entities/a-search-algorithm/packet","facts_jsonld":"https://4ort.xyz/entity/a-search-algorithm/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=a-search-algorithm","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=a-search-algorithm","wikidata":"https://www.wikidata.org/wiki/Q277680","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":[]}