MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications
Zike Yuan, Ming Liu, Hui Wang, Bing Qin
图形理论问题出现在物流、通信网络和流量优化等实际应用中。 这些问题往往是复杂的、嘈杂的和不规则的,给传统算法带来了挑战。 大型语言模型(LLM)提供潜在的解决方案,但面临挑战,包括有限的准确性和输入长度限制。 为了应对这些挑战,我们提出了MA-GTS(Multi-Agent Graph Theory Solver),这是一个多代理框架,通过代理协作分解这些复杂的问题。 MA-GTS将隐式表示的基于文本的图形数据映射到清晰的、结构化的图形表示中,并根据问题约束和图形结构尺度动态选择最合适的算法。 这种方法确保解决方案过程保持高效,由此产生的推理路径是可解释的。 我们使用G-REAL数据集验证MA-GTS,这是我们创建的现实启发的图论数据集。 实验结果表明,MA-GTS在效率、准确性和可扩展性方面优于最先进的方法,在多个基准(G-REAL 94.2%,GraCoRe 96.9%,NLGraph 98.4%)中取得了强劲的成果。MA-GTS在https://github.com/ZIKEYUAN/MA-GTS.git上开源。
Graph-theoretic problems arise in real-world applications like logistics, communication networks, and traffic optimization. These problems are often complex, noisy, and irregular, posing challenges for traditional algorithms. Large language models (LLMs) offer potential solutions but face challenges, including limited accuracy and input length constraints. To address these challenges, we propose MA-GTS (Multi-Agent Graph Theory Solver), a multi-agent framework that decomposes these complex probl...