Amoeba-Inspired All-Analog Electronic Computing System Integrating Crossbar Circuit That Solves Maximum Cut Problem

DOI Open Access

Bibliographic Information

Other Title
  • 抵抗クロスバー回路を備えた粘菌型アナログ電子解探索システムにおける最大カット問題解法

Abstract

We propose an asynchronous analog electronic circuit, named “electronic amoeba,” for searching for a solution to an NP-hard combinatorial optimization problem, the maximum cut problem (Max-Cut). We experimentally demonstrate that a breadboard-fabricated circuit certainly finds an optimal solution for a minimal-sized Max-Cut instance. Further investigating the search performance of the electronic amoeba for larger-sized Max-Cut instances with the number of nodes up to 5000 based on numerical simulations, we show that it converges to a local minimum solution in an approximately constant time independent of the problem size, although its optimality (cut size) is not impressively high.

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top