Thắc mắc về TSP2 so với TSP1

[Anh_Tieng (Anh Tiếng)]

Cho e xin phép hỏi sự khác nhau giữa TSP2 so với TSP1 với ạ, tại sao từ đỉnh 7->4 thế ạ, e k hiểu là chọn ngược i gần j nhất là sao

[Sherly1001]

Như nó nói đó, là chọn j sao cho chi phí từ i đến j là nhỏ nhất so vói những đỉnh khác đến j. :v
Vd từ bước 7 -> 4

Màu xanh dương là những ô gần j nhất, còn màu lục là ô gần i nhất.
Theo greedy 1 thì sẽ chọn màu lục, còn greedy 2 sẽ chọn màu xanh dương. :v

Thử nhìn xem vd từ 4 -> 5 nữa nhá

Trong trường hợp này hơi đen, k có ô xanh dương nào nằm trên hàng khoanh đỏ, nên sẽ lấy theo greedy 1 (lấy ô lục). :v

P/S: Việc greedy 2 tốn ít hơn greedy 1 trong vd trên cũng chỉ là hên xui th, k có gì đảm bảo nó sẽ luôn nhỏ hơn cả. :v

[Anh_Tieng (Anh Tiếng)]

Xin lỗi vì đến bây giờ e mới vào xem, thật sự rất hay ạ, qua những lần này e mới hiểu đc rằng giải thuật tham lam cơ bản là đưa ra giải pháp tốt chứ không phải lúc nào cũng là giải pháp tối ưu nhất