Tìm lộ trình ngắn nhất

[gauchoigameonline]

Dear a/e



Hiện tại mình có bài toán như sau:

Cho n vị trí cộ định, biết trước khoảng cách giữa các điểm với nhau (mỗi điểm đều có khoảng cách đến tất cả các điểm còn lại)

Yêu cầu bài toán là tìm lộ trình ngắn nhất đi qua n điểm, cụ thể

1, Vị trí xuất phát, vị trí kết thúc? (thuộc n vị trí cố định)

2, Lộ trình di chuyển: thứ tự từng vị trí đi qua (tại mỗi Node, lộ trình có thể lặp lại - đi qua Node đó nhiều lần)

※ Map tuyến đường & ví dụ minh họa tham khảo file đính kèm!

>> A/e có cao kiến gì hỗ trợ mình cái nhé. Thank so much!

 

[CHAOQUAY]

Dear a/e



Hiện tại mình có bài toán như sau:

Cho n vị trí cộ định, biết trước khoảng cách giữa các điểm với nhau (mỗi điểm đều có khoảng cách đến tất cả các điểm còn lại)

Yêu cầu bài toán là tìm lộ trình ngắn nhất đi qua n điểm, cụ thể

1, Vị trí xuất phát? (thuộc n vị trí cố định)

2, Lộ trình di chuyển: thứ tự từng vị trí đi qua
※ Ví dụ tham khảo file đính kèm
>> A/e có cao kiến gì hỗ trợ mình cái nhé. Thank so much!

Bài toán của bạn có số nút max là khoảng bao nhiêu?

 

[gauchoigameonline]

Bài toán của bạn có số nút max là khoảng bao nhiêu?

Số nút max hiện tại khoảng 100 nhé bạn!

 

[Excel my love_1]

Cái này trước xem chương trình shark tank của VTV3 thấy có 1 đơn vị họ làm được (mà có tính phí), nghe nói thuật toán gì gì đó chỉ có 1-2 đơn vị có thể làm được

 

[gauchoigameonline]

Cái này trước xem chương trình shark tank của VTV3 thấy có 1 đơn vị họ làm được (mà có tính phí), nghe nói thuật toán gì gì đó chỉ có 1-2 đơn vị có thể làm được

Không phải là thật chứ, nếu thật chắc buồn lắm (

 

[thnghiachau]

Dear a/e



Hiện tại mình có bài toán như sau:

Cho n vị trí cộ định, biết trước khoảng cách giữa các điểm với nhau (mỗi điểm đều có khoảng cách đến tất cả các điểm còn lại)

Yêu cầu bài toán là tìm lộ trình ngắn nhất đi qua n điểm, cụ thể

1, Vị trí xuất phát? (thuộc n vị trí cố định)

2, Lộ trình di chuyển: thứ tự từng vị trí đi qua
※ Ví dụ tham khảo file đính kèm
>> A/e có cao kiến gì hỗ trợ mình cái nhé. Thank so much!

Bạn cho hỏi:
1/ việc đi có cần đi hết các nút không?
2/ có qui định vị trí cuối cùng không?
3/ có qui luật ràng buộc đi như thế nào không?

 

[gauchoigameonline]

Bạn cho hỏi:
1/ việc đi có cần đi hết các nút không?
2/ có qui định vị trí cuối cùng không?

Bạn ơi yêu cầu bài toán có ghi cụ thể mà:
1, Lộ trình phải đi qua tất cả các điểm (n điểm)
2, Không quy định vị trí xuất phát và vị trí kết thúc

 

[VetMini]

Hình như bạn giỏi tiếng Anh lắm thì phải.
Từ khoá để tra: heuristic

 

[batman1]

Hình như bạn giỏi tiếng Anh lắm thì phải.
Từ khoá để tra: heuristic

Bài này giống "chinese postman problem algorithm". Giống vì bài "người đưa thư TQ" đi và trở về điểm xuất phát.

Không biết có tam giác ABC như trong bài không nhỉ: AB + AC = BC.

1. Nhớ hồi học hình học thì biết: tổng 2 cạnh của tam giác bất kỳ luôn lớn hơn cạnh thứ ba.
2. Chắc chắn cả những người không đi học biết là "đường chim bay" luôn là con đường ngắn nhất giữa 2 điểm bất kỳ.

 

[VetMini]

Thôi lỡ gợi ý rồi, chỉ luôn cho tiện.
shortest path visiting all nodes
(Java, Python, C++ codes)

 

[CHAOQUAY]

Số nút max hiện tại khoảng 100 nhé bạn!

Bạn gửi mẫu vài chục nút bố trí theo cách của bạn lên để thử xem sao

 

[gauchoigameonline]

Bạn gửi mẫu vài chục nút bố trí theo cách của bạn lên để thử xem sao

Đây nhé bạn, mình chỉ lấy ví dụ thôi nhé!

Bài đã được tự động gộp: 11/9/20

Thôi lỡ gợi ý rồi, chỉ luôn cho tiện.
shortest path visiting all nodes
(Java, Python, C++ codes)

Mình có đọc qua mấy bài viết liên quan đến 「heuristic」như bạn gợi ý.
Hình như là đang nói đến việc tìm đường đi ngắn nhất giữa 2 điểm bất kỳ mà bạn (dùng giải thuật Dijkstra or Floyd)?

Bài đã được tự động gộp: 11/9/20

Hình như bạn giỏi tiếng Anh lắm thì phải.
Từ khoá để tra: heuristic

Có căn cứ nào mà bạn bảo mk giỏi tiếng anh thế ?

 

[tigertiger]

Đây là bài toán cổ điển rồi, Cứ tìm kiếm google là ra
Đường đi ngắn nhất
Thuật toán đồ thị
Thuật toán duyệt cây
....
Chỉ e rằng quy mô bài toán , khi lớn thì khó đạt kết quả tốt nhất
Và tính ứng dụng bài toán thường hạn hẹp

 

[gauchoigameonline]

Đây là bài toán cổ điển rồi, Cứ tìm kiếm google là ra
Đường đi ngắn nhất
Thuật toán đồ thị
Thuật toán duyệt cây
....
Chỉ e rằng quy mô bài toán , khi lớn thì khó đạt kết quả tốt nhất
Và tính ứng dụng bài toán thường hạn hẹp

Mấy thuật toán đó toàn là tìm đường đi ngắn nhất giữa 2 điểm bất kỳ, chứ không phải là tìm cả lộ trình ngắn nhất đi qua những điểm cố định cho trước, hjk!!

Thank bạn nhé!

 

[tigertiger]

Mấy thuật toán đó toàn là tìm đường đi ngắn nhất giữa 2 điểm bất kỳ, chứ không phải là tìm cả lộ trình ngắn nhất đi qua những điểm cố định cho trước, hjk!!

Thank bạn nhé!

Có nhé, 2 điểm thì đâu phải tìm nữa. Cứ tìm đi, ví dụ thuật toán Vét cạn sẽ bao hết các phương án

 

[gauchoigameonline]

Có nhé, 2 điểm thì đâu phải tìm nữa. Cứ tìm đi, ví dụ thuật toán Vét cạn sẽ bao hết các phương án

Okie bạn để mình thử tìm hiểu xem ntn!

 

[gauchoigameonline]

Bài này giống "chinese postman problem algorithm". Giống vì bài "người đưa thư TQ" đi và trở về điểm xuất phát.

Không biết có tam giác ABC như trong bài không nhỉ: AB + AC = BC.

1. Nhớ hồi học hình học thì biết: tổng 2 cạnh của tam giác bất kỳ luôn lớn hơn cạnh thứ ba.
2. Chắc chắn cả những người không đi học biết là "đường chim bay" luôn là con đường ngắn nhất giữa 2 điểm bất kỳ.

^^ Bạn có làm cái code nào tương tự như bài người đưa thư này ko?

 

[CHAOQUAY]

Đây nhé bạn, mình chỉ lấy ví dụ thôi nhé!

Cần số liệu giả định đó bạn.
Trong bài của bạn, tất cả các nút đều liên thông?

 

[befaint]

code

File dữ liệu hôm qua đâu rồi bạn?

Từ khóa ở bài #10 đó. Sao mình lỡ làm rơi vậy?

 

[gauchoigameonline]

Cần số liệu giả định đó bạn.
Trong bài của bạn, tất cả các nút đều liên thông?

Nó là bài toán thực tế luôn nhé bạn chứ không phải là giả định.
Đường đi ngắn nhất giữa 2 Node bất kỳ sẽ được tự động tính toán bằng giải thuật (Dijstka) >> Số liệu tự động tính toán
Mô hình chính là mạng lưới giao thông, trong đó các Node đều liên thông được với nhau.