本题的代价函数为 w(j,i)=i−jw(j,i)=\sqrt{i-j}w(j,i)=i−j,令 a,b,c,da,b,c,da,b,c,d 分别为 1,2,3,41,2,3,41,2,3,4,那么:
w(a,c)+w(b,d)=22≈2.8w(a,c)+w(b,d)=2\sqrt 2 \approx 2.8w(a,c)+w(b,d)=22≈2.8
w(a,d)+w(b,c)=3+1≈2.7w(a,d)+w(b,c)=\sqrt 3+1 \approx 2.7w(a,d)+w(b,c)=3+1≈2.7
前者大于后者,不满足四边形不等式。但为什么仍然能用基于其的优化?