{"entities":{"Q790720":{"pageid":792568,"ns":120,"title":"Item:Q790720","lastrevid":48688087,"modified":"2026-01-05T15:02:35Z","type":"item","id":"Q790720","labels":{"en":{"language":"en","value":"Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3849000"}},"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":"Q790720$20BDACB5-2F38-4DF8-B88F-3759C7AC7DFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"87295c7d1b875cabc6805dbaefa7cf9ef6e3ab29","datavalue":{"value":{"text":"Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790720$632D8AB3-D0EF-4FA1-8191-379B43E579ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98988af50456b231aa47d69f3af5365b8ab3f2d4","datavalue":{"value":"0534.90091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$61450A2B-ED17-4DA3-99D7-F3D8867B1F55","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e341a00b81c76bb8963439bfe6d692c55b472f47","datavalue":{"value":"10.1007/BF00940812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$8CBB0071-7EB5-42EC-B4D9-A9D5AEBD0614","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2eeaa416f18a10ad0bdbb9aa765a3c75e1023ede","datavalue":{"value":{"entity-type":"item","numeric-id":790719,"id":"Q790719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790720$E8D360CA-8633-4C89-9237-395D4C22D9CD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a3c8bf4d8569c126380a9fc42f55609089e776fb","datavalue":{"value":{"entity-type":"item","numeric-id":82026,"id":"Q82026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790720$174416A6-6820-4548-9453-CC1E3B60B028","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q790720$1A309B9B-0A5A-4BFF-A5BE-6A36F751795E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f8fa350ff4cd22254e76516c93f985eda6bcdd42","datavalue":{"value":"We present a Monte Carlo algorithm to find approximate solutions of the travelling salesman problem. The algorithm generates randomly the permutations of the stations of the travelling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one cat get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.    We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$C5B4EEB5-F31F-4506-8469-B4D1B4E78629","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$307F14E5-3AE6-4C11-B324-0744A6161798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63aec181f5f25f527f4a50518ef030353abadcda","datavalue":{"value":"65C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$957F4463-7A59-4EE1-8153-09F895093F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d3a2d1240164c8ddd5866f2ec6f6efc3a286b899","datavalue":{"value":"80A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$C4C632DE-25CD-4F3F-93DC-FB3F4D7F0610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$904905DC-AB22-46EC-8917-0A23D3B244BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb7d7aafa6d19e14639eb9d4684a5929520cc740","datavalue":{"value":"3849000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$B8B8E74B-D255-4365-B4F1-5C5404B51342","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3b9a2c122dd89be72ecbd4dd046019cd3c25be","datavalue":{"value":"importance sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$B9A1D62D-4A58-47BD-B632-23323C14D59F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2db315b3ab4cda7112b8cbdb5a03468757139db","datavalue":{"value":"Monte Carlo algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$BC7BBD6A-734A-4D56-BA52-46E3EF4B4772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8205005c0975ece57da73400ce9be01687bc47fd","datavalue":{"value":"approximate solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$BEB43866-2436-4629-BA9A-B14279B21A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$DF63B63D-6435-4D69-A36A-A021DFD174DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f272abd1f0cd89ce062c17298ce76d64644e512","datavalue":{"value":"Boltzmann-Gibbs distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$A75D2D49-06FA-402F-9BAD-EF41B1E57E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51db2eaed8cf85cc810ab4980fab910ab6706218","datavalue":{"value":"analogy with thermodynamics","type":"string"},"datatype":"string"},"type":"statement","id":"Q790720$D0EA68AC-1EB8-448F-A5FE-B05D2354B89E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"30be395606de165206c2d3a72c7e2b6e5749a8f8","datavalue":{"value":"Q55967971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790720$CA5B03A8-F505-4E54-B9F8-9E56A2C8B56C","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":"Q790720$A5C652C5-FB2A-4E3A-BB0E-B0667062FFE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfbf6b35b4e6c765ecd0deefbde760aa00f45645","datavalue":{"value":{"entity-type":"item","numeric-id":3343803,"id":"Q3343803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73431c13e2df09e631451c549367b1dbf8460e38","datavalue":{"value":{"amount":"+0.8895996809005737","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":"Q790720$C732D508-4466-4D8B-8F15-FE556E70E7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cce8cd020e2137b44478fcda314eb26f5f91c741","datavalue":{"value":{"entity-type":"item","numeric-id":82025,"id":"Q82025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df1e2f49f6051e473553a401ee9f9b73210a961b","datavalue":{"value":{"amount":"+0.8570065498352051","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":"Q790720$44C01251-FC40-4B8E-8859-ADC52152C17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16db23b0dd52dbde3fe1117759ca993a4c5c3a67","datavalue":{"value":{"entity-type":"item","numeric-id":499569,"id":"Q499569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f338bba17e33610620ab2b6faaf7a6184d0a5e","datavalue":{"value":{"amount":"+0.8252466320991516","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":"Q790720$DFB2211B-66A3-460C-9806-10E600D4818A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d076c37711cfad2f50fedfc4f2ddb881280ce4e6","datavalue":{"value":{"entity-type":"item","numeric-id":3106663,"id":"Q3106663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3c9cf050897ad58077da5150dd54315a69a4afe","datavalue":{"value":{"amount":"+0.8242910504341125","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":"Q790720$655A82E4-138B-45CF-8825-F6452B33435C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39a08ebeba81a2f8c184495fff22090b1113fa25","datavalue":{"value":{"entity-type":"item","numeric-id":3801369,"id":"Q3801369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a69fa26fa36b9ed97cf27e5af2fbaebf96e2b04","datavalue":{"value":{"amount":"+0.8242785930633545","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":"Q790720$57D3CC11-CB30-4189-9286-2CAAAF1ADFCF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790720","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790720"}}}}}