最小化顶点距离的算法 - 矮人要塞
jno*_*cho 12 algorithm optimization graph graph-layout
我玩Dwarf Fortress游戏.对我来说,主要的挑战是有效地设计堡垒的布局.意思是,每个行业流程应尽可能密集,以尽量减少行程距离.
一个例子可能是食品工业 
.每个灰色椭圆代表一个建筑物.每个白色矩形代表建筑物的产品.
我的目标是找到将建筑物分布在2D网格上的算法,使得这些建筑物之间的距离在它们如何连接的意义上是最小的.这意味着fishery和loom可相距甚远,但loom并farmer's应尽可能接近.
目前我已经考虑过使用一些现成的软件来模拟布局,但算法的一些技巧会很好.
目前我正在考虑一些力导向算法,但我不确定离散网格要求.
问题的形式化:是否存在一种在离散坐标下工作的强制绘制图算法？
更新:我已经在AS3中找到了Force绘制算法的实现(web也包含JS版本).我会尝试将其转换为离散版本.但我怀疑它会起作用......
更新2:评论中要求进一步限制.它们是:每个建筑物占据虚拟网格上的单个单元格.建筑物可以在相邻的单元格上.建筑物不能堆叠/重叠.(PS:在游戏中,每个建筑都有规模,通常为3x3,但我想让问题更加通用,以便采用更多方法).