{"entities":{"Q1102137":{"pageid":1112889,"ns":120,"title":"Item:Q1102137","lastrevid":42878769,"modified":"2025-07-15T15:59:08Z","type":"item","id":"Q1102137","labels":{"en":{"language":"en","value":"Network-based heuristics for constraint-satisfaction problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4049149"}},"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":"Q1102137$BB6185B5-0B66-430E-8E9C-5BF4E376F444","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b411ef715b7252a3c59c1e939976f77bc2a98d20","datavalue":{"value":{"text":"Network-based heuristics for constraint-satisfaction problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102137$551541F0-2E47-4CB9-BC77-20BEC171FD22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b949679ef3dac415dc3eafede012eb8a09eae96","datavalue":{"value":"0643.68156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102137$C674D803-18A8-4598-B129-B0E2FC204E60","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c01fbb391f2e0871a1439c01b6a248fa6d7d05d7","datavalue":{"value":"10.1016/0004-3702(87)90002-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102137$4046BD27-62CA-4886-B909-61689F9F9AA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"460eb0ad62dfb02500155a265d74683a6914d8f6","datavalue":{"value":{"entity-type":"item","numeric-id":513335,"id":"Q513335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$807CAFDB-BE0F-4E0C-9827-326E80D1AB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"adc1f8175fa525f7221022c17bdbb336b8b4861b","datavalue":{"value":{"entity-type":"item","numeric-id":252806,"id":"Q252806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$9A0532ED-89AF-42A0-A393-6E726EEF804F","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":"Q1102137$C58E845F-EE53-4C69-8299-15AAD75C4F72","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1102137$ECF7DBB3-0DE7-441B-8226-10F8B4480862","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"161e4275246e01f1a72844308a3e2506d0fda34a","datavalue":{"value":"Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree- structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102137$19C7EF9B-261E-4293-9746-61FAB8456562","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102137$092234ED-7B3C-4910-B96C-22BB22A40881","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fba4272029b53347d18f9bd28f55f342ba717c45","datavalue":{"value":"4049149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102137$7F1DE35D-4DDA-4345-895B-65787CAEE3A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"001b7e1d7a077a2f0647bbb31d32563fe2986b60","datavalue":{"value":"constraint-satisfaction problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102137$8E053ADD-EC34-43EF-AE7D-3FC36A80FA0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49698f26009d8ea8ba40e2c67b7e8fd704cf4848","datavalue":{"value":"sparse networks of constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102137$4B772D0B-5939-4E90-983B-8183EB17FB1E","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":"Q1102137$04EC78C5-201F-492D-8A6F-B0E9B753D7AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"608074c74e8c50a4cc0da8aeebad0a0a2a72891c","datavalue":{"value":"https://doi.org/10.1016/0004-3702(87)90002-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102137$DFE09895-3BC7-429E-A686-16850474C85E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"edd5ec0fc03aac8fe75dbc3655b579d46492feb3","datavalue":{"value":"W2061734130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102137$68FC5478-7DD6-4152-B57B-DDA37C4654A6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$395BF486-3C2A-4A12-AFD9-52A784B0E0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"678e7a4be408fd6129f52f04fe687f74c25ca083","datavalue":{"value":{"entity-type":"item","numeric-id":2554881,"id":"Q2554881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$6F701983-1189-4176-9D3C-967B4F95DC75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e75d71633d4d8b2c0b82c9e13cc6b17d5fc3d7bb","datavalue":{"value":{"entity-type":"item","numeric-id":3835053,"id":"Q3835053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$55D27A14-C3B2-4517-A0DA-29EA46804E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$E1F389A3-0AA1-41AC-B99B-0FD755CB1440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1958ff7e040b608ab81be40fc268247c86c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3933756,"id":"Q3933756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$FB3F2DE2-36E3-46DB-B439-441DC1C53E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e807cad96e78d6ed80e9767e538b1f542dbf4d4","datavalue":{"value":{"entity-type":"item","numeric-id":3771663,"id":"Q3771663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$410D7043-BD42-42D3-8277-5907409857AE","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":"Q1102137$C2AF11B5-DD82-4636-9DE7-E2B1708023D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f53310362b41756586f4a9ba11445f98bc084042","datavalue":{"value":{"entity-type":"item","numeric-id":4051599,"id":"Q4051599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$C385EDC3-8117-493C-8F03-A55E23EB5368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc7b0f82e42c56ee306811b6c3df8af19432e03","datavalue":{"value":{"entity-type":"item","numeric-id":1231783,"id":"Q1231783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$601745EE-2489-4923-98C0-B0B1FB17E7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e6120540464f464cc2d46003d13c44261ed5a2","datavalue":{"value":{"entity-type":"item","numeric-id":3727417,"id":"Q3727417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$0563FC1F-1155-4549-988E-D655A4E6890E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2c3619e54d23805be501ac56b166e67b0585f38","datavalue":{"value":{"entity-type":"item","numeric-id":5507983,"id":"Q5507983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$682494C9-997C-4DE1-8F88-A6CDE0A9BFE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8409c6b47904da9ba25328ffb35bebdb7d310a8","datavalue":{"value":{"entity-type":"item","numeric-id":1844713,"id":"Q1844713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$B0179E61-1BEB-4042-A63E-902B2441DE60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fee3290184e0240c1fcdc78a5c0bf709606b2b","datavalue":{"value":{"entity-type":"item","numeric-id":1846747,"id":"Q1846747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$2C35461E-E163-4786-93FC-608858DD05C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b266c721655122dbe400bbee292733bb46b20d","datavalue":{"value":{"entity-type":"item","numeric-id":1244202,"id":"Q1244202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$50BCC044-7EBC-4FD2-BB07-3BDDAD637DFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3dcaf481fbcf895d3c7f992268e153181a168d","datavalue":{"value":{"entity-type":"item","numeric-id":3776618,"id":"Q3776618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$1AA44C57-36CE-468B-B5DB-E4E9CECB343D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bba15cf4a9d2c986ffe8184ac3a6d051fff29cb","datavalue":{"value":{"entity-type":"item","numeric-id":3335007,"id":"Q3335007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102137$AFECD2DA-9E02-45E7-BA50-9E884223C4DD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7911782c7053f0927d638233b9ef886f09e15085","datavalue":{"value":{"entity-type":"item","numeric-id":1580446,"id":"Q1580446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8d2f80587f6184fc371caadbeaae58bfb647ca3","datavalue":{"value":{"amount":"+0.9053956","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":"Q1102137$9A01B174-A325-4D7E-B7BB-5D060D9B53CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e54f85699464d98dea3f54c1e231b57772df0ee3","datavalue":{"value":{"entity-type":"item","numeric-id":3481517,"id":"Q3481517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a643b70f0dbe285fa92455e09055573d10188b82","datavalue":{"value":{"amount":"+0.8801292","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":"Q1102137$BCEDF797-9004-4DFD-9715-8E3F904B5502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d00ab26221179f47c426be583fa2132e883e4a23","datavalue":{"value":{"entity-type":"item","numeric-id":3786030,"id":"Q3786030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab2a86f6ccd605f8f3d5178d16b60a96276d5fdb","datavalue":{"value":{"amount":"+0.8798208","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":"Q1102137$303916D9-5440-4C6B-8D70-AE7A181785B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2133866cf443b04d01ae60062561e9b8388628f","datavalue":{"value":{"entity-type":"item","numeric-id":281782,"id":"Q281782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3034c138a466b4ff56ed81936bb6b3d9ed6e2eb0","datavalue":{"value":{"amount":"+0.87971544","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":"Q1102137$64790CEE-4069-4F59-918D-5E22B2F48E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b1439876ffc1616b226e760331b9f5adc2caf40","datavalue":{"value":{"entity-type":"item","numeric-id":1951176,"id":"Q1951176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"702321b7b5395ab2f97fd121b357d0254800622f","datavalue":{"value":{"amount":"+0.8758281","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":"Q1102137$A9B01D29-A937-4F05-BEDA-BE107AF357F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66c556def582a23ed0aca1fc377976de310b661","datavalue":{"value":{"entity-type":"item","numeric-id":3401666,"id":"Q3401666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f0a109424490c4e941978b106212faa9b223143","datavalue":{"value":{"amount":"+0.8746636","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":"Q1102137$BFFF07B3-1DB3-48CA-857F-E5A993D1080A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8060118fe9b509f14bb6b552b51d39c96897492","datavalue":{"value":{"entity-type":"item","numeric-id":3199211,"id":"Q3199211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"666b5a55aefa097315994b95b1036a40d6ec811c","datavalue":{"value":{"amount":"+0.8693881","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":"Q1102137$AC841FD5-12B9-42E5-B773-4C5B27D56A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aacd6d2d5ce0fe8098b15f68b2b6096ec2b7026","datavalue":{"value":{"entity-type":"item","numeric-id":2027081,"id":"Q2027081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e0d7bb36c8b763a389a3f3e922db89bd5787ca2","datavalue":{"value":{"amount":"+0.86709374","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":"Q1102137$5284293C-CB42-4CD8-9961-DA61660D6351","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1102137","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1102137"}}}}}