{"id":116940,"date":"2020-12-10T15:27:24","date_gmt":"2020-12-10T23:27:24","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2020\/12\/electronic-amoeba-finds-approximate-solution-to-traveling-salesman-problem-in-linear-time"},"modified":"2020-12-11T04:24:24","modified_gmt":"2020-12-11T12:24:24","slug":"electronic-amoeba-finds-approximate-solution-to-traveling-salesman-problem-in-linear-time","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2020\/12\/electronic-amoeba-finds-approximate-solution-to-traveling-salesman-problem-in-linear-time","title":{"rendered":"\u2018Electronic amoeba\u2019 finds approximate solution to traveling salesman problem in linear time"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/electronic-amoeba-finds-approximate-solution-to-traveling-salesman-problem-in-linear-time.jpg\"><\/a><\/p>\n<p>Researchers at Hokkaido University and Amoeba Energy in Japan have, inspired by the efficient foraging behavior of a single-celled amoeba, developed an analog computer for finding a reliable and swift solution to the traveling salesman problem\u2014a representative combinatorial optimization problem.<\/p>\n<p>Many real-world application tasks such as planning and scheduling in logistics and automation are mathematically formulated as combinatorial optimization problems. Conventional digital computers, including supercomputers, are inadequate to solve these <a href=\"https:\/\/phys.org\/tags\/complex+problems\/\" rel=\"tag\" class=\"\">complex problems<\/a> in practically permissible time as the number of candidate solutions they need to evaluate increases exponentially with the problem size\u2014also known as combinatorial explosion. Thus new computers called Ising machines, including quantum annealers, have been actively developed in recent years. These machines, however, require complicated pre-processing to convert each task to the form they can handle and have a risk of presenting illegal solutions that do not meet some constraints and requests, resulting in major obstacles to the practical applications.<\/p>\n<p>These obstacles can be avoided using the newly developed \u2018electronic amoeba,\u2019 an <a href=\"https:\/\/phys.org\/tags\/analog+computer\/\" rel=\"tag\" class=\"\">analog computer<\/a> inspired by a single-celled amoeboid organism. The amoeba is known to maximize nutrient acquisition efficiently by deforming its body. It has shown to find an approximate solution to the <a href=\"https:\/\/phys.org\/tags\/traveling+salesman+problem\/\" rel=\"tag\" class=\"\">traveling salesman problem<\/a> (TSP), i.e., given a map of a certain number of cities, the problem is to find the shortest route for visiting each <a href=\"https:\/\/phys.org\/tags\/city\/\" rel=\"tag\" class=\"\">city<\/a> exactly once and returning to the starting city. This finding inspired Professor Seiya Kasai at Hokkaido University to mimic the dynamics of the amoeba electronically using an analog circuit, as described in the journal <i>Scientific Reports<\/i>. \u201cThe amoeba core searches for a solution under the electronic environment where resistance values at intersections of crossbars represent constraints and requests of the TSP,\u201d says Kasai. Using the crossbars, the city layout can be easily altered by updating the resistance values without complicated pre-processing.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Researchers at Hokkaido University and Amoeba Energy in Japan have, inspired by the efficient foraging behavior of a single-celled amoeba, developed an analog computer for finding a reliable and swift solution to the traveling salesman problem\u2014a representative combinatorial optimization problem. Many real-world application tasks such as planning and scheduling in logistics and automation are mathematically [\u2026]<\/p>\n","protected":false},"author":513,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1617,6,44],"tags":[],"class_list":["post-116940","post","type-post","status-publish","format-standard","hentry","category-quantum-physics","category-robotics-ai","category-supercomputing"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/116940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/513"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=116940"}],"version-history":[{"count":1,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/116940\/revisions"}],"predecessor-version":[{"id":116961,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/116940\/revisions\/116961"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=116940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=116940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=116940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}