.png){kind=icon}
Return
Enhanced discrete dragonfly algorithm for solving four-color map problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-022-03791-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The classic combinatorial optimization problem of graph coloring is one of the most famous NP-complete problems. One example of the graph coloring problem is the four-color map problem. There have been many applications of swarm intelligence optimization algorithms to this problem, but to date, such algorithms can only solve the four-color map problem with fewer than 100 regions. This article proposes an enhanced discrete dragonfly algorithm (EDDA) for four-color map problems. We use global and local discrete alternate search strategies-when there is at least one adjacent dragonfly around the i-th dragonfly, a global search is performed; when there are no other dragonflies around, a local search is performed. A greedy strategy, local differential cross strategy, and single-point switching strategy are then used to solve the problem of conflicts among adjacent nodes. Finally, six real-life maps are colored to verify the effectiveness of the proposed algorithm. The experimental results show that the proposed EDDA algorithm can solve the four-color map problem with more than 100 regions.
Keywords:
Discrete dragonfly algorithm
Global and local discrete alternate search
Four-coloring map problem
Swarm intelligence
Journal
IF:
3.5
Papers:
7.6K
Citations:
1.7W
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSaveShareSave
ShareSave
View more