我正在寻找一种算法来解决这个问题.我必须实现它(所以我需要一个非np解决方案XD)
我有一个完整的图表,每个拱门都有成本,每个顶点都有奖励.我只有一个起点,但终点并不重要,因为问题是要找到一条路径尽可能多地查看顶点,以便尽可能获得最大奖励,但要受到最大成本限制.(因此,最终位置并不重要).
我认为找到最佳解决方案是一个难以解决的问题,但也是一个近似的解决方案:D
谢谢
我正在尝试研究如何用分支和绑定解决问题...
更新:完整问题dscription
我有一个区域,其中有几个区域通过其id和x,y,z位置来识别.每个顶点标识这些区域中的一个.最大的ares数是200.从起点S开始,我知道成本,以秒为单位并插入拱(因此只是整数值),从每个其他顶点到达每个顶点(一个完整的图).当我访问一个顶点时,我得到一个奖励(浮动valiues).
我的目标是在图表中找到最大化奖励的路径,但我受到路径上的成本约束.事实上,我只有有限的时间来完成路径(例如600秒).
该图表是作为成本和奖励的矩阵邻接矩阵(但如果有用,我可以更改表示).
我可以访问顶点更多的时间,但只有一个奖励!
像compareTo,必须是"反身,反对称和传递",是否有任何规则来实现比较方法？谢谢