{"entities":{"Q2012868":{"pageid":2023610,"ns":120,"title":"Item:Q2012868","lastrevid":72367017,"modified":"2026-04-14T04:25:33Z","type":"item","id":"Q2012868","labels":{"en":{"language":"en","value":"Can the agent with limited information solve travelling salesman problem?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6756009"}},"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":"Q2012868$A7C9DFDD-5346-425A-859E-EF33F3CA6504","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d2e1d8e02a314f29eb9aa186d1ce6865c306d26","datavalue":{"value":{"text":"Can the agent with limited information solve travelling salesman problem?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2012868$DFBCEB0F-DA74-4BBA-8E65-10734BFF1D08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"45fb7fd84b54b5d5a434c077789d1a09a0557375","datavalue":{"value":"1367.90095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$29BC7364-95F0-4AB2-A52B-A5D05FC84478","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3af71281c105414b76156061f45b13c9bdc75451","datavalue":{"value":"10.1155/2017/9562125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$8E3B47B5-7E90-49FF-8CC7-2B0A6A23F813","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f65eef0d90d88c8e96ae89b4d0e8b99209cebae5","datavalue":{"value":{"entity-type":"item","numeric-id":2012866,"id":"Q2012866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$585B38F6-2110-4B90-BA70-6C009C492046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53ae06ae82884bcc9a37d2d82063032e7fef2e7e","datavalue":{"value":{"entity-type":"item","numeric-id":2012867,"id":"Q2012867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$A5133A4D-CF8F-403D-8CB5-08A9B989C63C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1dec05d6eca21826ddc25d78a5bfbbb3575f964c","datavalue":{"value":{"entity-type":"item","numeric-id":86231,"id":"Q86231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$DE661A8F-C38F-4811-B9F3-C3C59A0E7890","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b3a2783a955645e83aada5eb39ffa5fafcd7904","datavalue":{"value":{"time":"+2017-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2012868$9B14811C-252D-4B48-A158-E3695D49966C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e4aeb53174fbf652496fafe111a3339a74a016a","datavalue":{"value":"Summary: Here, we develop new heuristic algorithm for solving the Travelling Salesman Problem (TSP). In our proposed algorithm, the agent cannot estimate tour lengths but detect only a few neighbor sites. Under the circumstances, the agent occasionally ignores the NN method (choosing the nearest site from current site) and chooses the other site far from current site. It is dependent on relative distances between the nearest site and the other site. Our algorithm performs well in symmetric TSP and asymmetric TSP (time-dependent TSP) conditions compared with the NN algorithm using some TSP benchmark datasets from the TSPLIB. Here, symmetric TSP means common TSP, where costs between sites are symmetric and time-homogeneous. On the other hand, asymmetric TSP means TSP where costs between sites are time-inhomogeneous. Furthermore, the agent exhibits critical properties in some benchmark data. These results suggest that the agent performs adaptive travel using limited information. Our results might be applicable to non-clairvoyant optimization problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012868$B713660A-72A6-4B22-811A-CB7BD1519E22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$F3B95B6F-5A8D-4C08-AB54-0DA29C32C769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$89BAAF2A-F477-4BBA-A789-DF12C7BD63AC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf25cb5baded38bac609af8b356571a8c5b54b33","datavalue":{"value":"6756009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$8B57726B-A20E-4499-A53B-ADF928D7D767","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35b895add2c369818f40222891b2b94ed46d1ebf","datavalue":{"value":"Travelling Salesman Problem (TSP)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012868$5A9A94AC-1F18-493C-BB35-EBEF37DAA88C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2af51969b73542d6aab2bcded7015ec65969c29e","datavalue":{"value":"heuristic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012868$7BCF3C0A-2D41-4C5D-B060-C87311DE2C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f511e40fc7781da19250f6515ed0964aa12e1804","datavalue":{"value":"symmetric TSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012868$582C102D-3F0D-4744-9087-E44F69BA563B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c1d1893eb52f8cdfae358a278a3493a84220202","datavalue":{"value":"asymmetric TSP (time-dependent TSP)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012868$ED258687-1890-4F76-AD4A-ACD0F5440A3B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"45004ff55f83c485b6603dbaba26309aeb6bf75d","datavalue":{"value":"Q59142967","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$D602AF9C-074A-4BA9-95FD-E3F16C7BB18F","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7237258b836283bef33e897e128d37db9d627348","datavalue":{"value":{"entity-type":"item","numeric-id":13727,"id":"Q13727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$E5F0B532-9354-4072-A459-690D97535639","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":"Q2012868$A9F6194E-D584-47C5-B80A-A94F6570D2CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4bd3e55734ab1602746a1a9cbb5647e2723f4c5d","datavalue":{"value":"https://doi.org/10.1155/2017/9562125","type":"string"},"datatype":"url"},"type":"statement","id":"Q2012868$864EB49E-DFE9-4661-8143-F3510C255624","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d8bb46e2fd71e7d713e0ae1435baf03b7e6eba0","datavalue":{"value":"W2605641102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$BED5C984-8234-4FA6-BD17-2C0272A6F359","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"20838c914e1f937b42cff59e37bbc187d5db1a2b","datavalue":{"value":{"entity-type":"item","numeric-id":1806777,"id":"Q1806777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$54020C94-AE52-4FE1-B7F6-F48A9A1E3A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f030d49769421de93ba4d8c53706308a5ef4c44c","datavalue":{"value":{"entity-type":"item","numeric-id":5187226,"id":"Q5187226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$71452D9B-4F1C-4093-B11B-A7EFC3960BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d873be2e37264b27dcb309f649fb77ab43f8b78","datavalue":{"value":{"entity-type":"item","numeric-id":1348379,"id":"Q1348379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$379D93FD-B333-4AD5-9B46-E031DBC9F4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9bd33c3c85a0557c9486fc138eedf7d42b02dd8","datavalue":{"value":{"entity-type":"item","numeric-id":955327,"id":"Q955327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$41E9F4DA-DD65-4240-98F3-022524588B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f923e223ca714566805e6e0df441f8fac164c4a","datavalue":{"value":{"entity-type":"item","numeric-id":4066863,"id":"Q4066863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$8BD33B8E-A2A7-4B2B-8CFE-81073614EFE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$3682B5FD-39B2-4444-9910-497C133DADF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$7948E2AD-E646-40CE-B449-0B1B615846EE","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"030d30e36c7c107a7d104abf59aab99367b02d83","datavalue":{"value":"journals/complexity/SakiyamaA17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012868$51DA01C6-9130-4D9B-B233-7E62679943F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23e035eb6eeac243b49115e4047a8ee6a1dc0808","datavalue":{"value":{"entity-type":"item","numeric-id":3445983,"id":"Q3445983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49e86f16d20b5131fe3a805f67a4ecd8d4d68fb5","datavalue":{"value":{"amount":"+0.7439884543418884","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":"Q2012868$21C8D6C3-9704-4010-9A3F-B2AC6627555A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3789651bfd0b030dc613f13cea0a8b8186cdaf76","datavalue":{"value":{"entity-type":"item","numeric-id":3790960,"id":"Q3790960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0c8a879d15d4a08ddb2c8765ed39ac45917f9d4","datavalue":{"value":{"amount":"+0.7394636869430542","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":"Q2012868$2510ADFA-A8DF-4CC3-B551-FE5EBD95C3E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13a933ba5335a10abd90eb187841a92337eb8a6a","datavalue":{"value":{"entity-type":"item","numeric-id":4285557,"id":"Q4285557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f20f122beb6b68c5227e938cc6fbdb0b6a0691b6","datavalue":{"value":{"amount":"+0.7368830442428589","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":"Q2012868$A11FEE3D-3673-4FC8-B44F-24C3FE9BD74D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1359c85ca1b7688c90a16dae9d94902fa18fb5d","datavalue":{"value":{"entity-type":"item","numeric-id":5928379,"id":"Q5928379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30e98a7f6166a84134e8252d18081812edcf3623","datavalue":{"value":{"amount":"+0.7266702651977539","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":"Q2012868$BB59F462-B12E-4BE0-8581-75BA69F9279A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9720b0bd783898af86b5aa232e0f3bc2357493b2","datavalue":{"value":{"entity-type":"item","numeric-id":3812064,"id":"Q3812064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd4b37e7077395def7f61046eb3a5be83b5b3990","datavalue":{"value":{"amount":"+0.7250456213951111","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":"Q2012868$D0C7A9A8-FCF9-4CB6-9210-3ED0E33A49CD","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012868$813999D8-E78B-4E92-9536-F88B25FD1C0B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Can the agent with limited information solve travelling salesman problem?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Can_the_agent_with_limited_information_solve_travelling_salesman_problem%3F"}}}}}