假设有一个网格包含两个墙(被阻塞的单元格)以及放置在网格上任何位置的食物。最优蚁群定位算法
现在假设我们正试图决定最佳的位置来放置蚁群在这个电网,使得蚂蚁有旅游的最小距离(在任何方向往/返的起点殖民地)获得最大数量的食物。
到目前为止,我已经想出最好的办法是:
for each square on the grid
use a shortest path algorithm to find the distance to/from each food source from this square
sum these distances to find a number and put the number in that square
select the square with the smallest number
请问这种方法甚至工作?有没有更有效的解决方案?
优化是跟踪最短距离,并停止计算任何超过最短路径的总和。 – tofi9 2015-02-07 06:33:33
目前还不清楚你想在这里优化哪些功能。食物颗粒是否都是相同的大小?假设在(0,0)和(4,0)有一个粒子。 (0,0)(在一个颗粒上面,另一个颗粒在4个单位上)或者在(2,0)上(两个颗粒之间的中间位置)有个菌落?如果你认为颗粒食物的价值/距离,第一个更好。如果您将颗粒作为食物的价值 - 距离,颗粒之间的所有位置都同样好。一只蚂蚁能在一次旅行中将整个小球带回殖民地吗? – 2015-02-07 06:48:38
@robmayoff我认为“让蚂蚁走得最远”这一点非常清楚--OP正试图将一个特定点与所有含有食物的细胞之间的距离总和最小化。 – 2015-02-07 10:45:18