java 实现 最优路径算法 ？？？

Question

提个需求：即在一个超市的购物系统中，你选择了多种商品，要求你设计条最优路线（用时最短或线路最近，要考虑超市货架的实际情况，不能斜着走，只能按实际能够通过的通道去选购）包含你所有选购的商品（可以回头），用java实现这个算法？（提示：哈密尔顿图或欧拉图）哪位大神有思路的啊 ？

Answer 1

状压DP，定义f[i][s]表示走到第i个点，状态是S最小花费，时间复杂度N*2^N，每个点就是一个商品，S用二进制表示，10011表示购买到了第1，2，5个商品，3，4没买到，最后F[i][s']是答案， s'=111111(N个1)，枚举i

Answer 2

用DP无异于搜索所有排列组合，效率还不如A*。