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]

@gauchoigameonline
Chạy solver trong file đính kèm.
Số liệu 4 nút trong file cũ của bạn.
---
Thực tế với giả định máy tính nó có phân biệt được không bạn?
---
Chạy sheet3

 

[gauchoigameonline]

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?

View attachment 245329

Trong file đính kèm trên bài đăng đó bạn (trong Sheet thứ 2 nhé)!

Mà từ khóa ở bài #10 là gì bạn? Bạn gửi luôn link cho mk đc ko?

 

[tigertiger]

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ỳ.

Chắc kiểu lối cũ ta về

 

[befaint]

Trong file đính kèm trên bài đăng đó bạn (trong Sheet thứ 2 nhé)!

Tải cả 2 file đều không thấy Sheet thứ 2 nào. Chỉ thấy 1 sheet duy nhất.

Mà từ khóa ở bài #10 là gì

 

[gauchoigameonline]

Tải cả 2 file đều không thấy Sheet thứ 2 nào. Chỉ thấy 1 sheet duy nhất.

View attachment 245338


View attachment 245345

Đây nhé bạn (File đăng lên chỉ chứa đc 1 Sheet hay sao ấy, file nguồn của mk vẫn có 2 Sheet mà).

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

@gauchoigameonline
Chạy solver trong file đính kèm.
Số liệu 4 nút trong file cũ của bạn.
---
Thực tế với giả định máy tính nó có phân biệt được không bạn?
---
Chạy sheet3

Mình chẳng thấy phần chạy ở đâu vậy bạn?
Thực tế với giả định (mô hình Map mình lập) chương trình tự động phân biệt được nhé.
(Đang hướng tới việc xây dung hệ thống tương tự Google map trên Excel: tự nhận biết vị trí hiện tại, chỉ đường…)

 

[CHAOQUAY]

Mình chẳng thấy phần chạy ở đâu vậy bạn?
Thực tế với giả định (mô hình Map mình lập) chương trình tự động phân biệt được nhé.
(Đang hướng tới việc xây dung hệ thống tương tự Google map trên Excel: tự nhận biết vị trí hiện tại, chỉ đường…)

Chọn sheet3, vào menu data, tìm biểu tượng solver, ấn vào đấy

 

[befaint]

Đây nhé bạn

Đây nhé bạn 1 2 3.

 

[VetMini]

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

Xổ thiếng Anh tưng bừng như ngày hội thì không giỏi chẳng nhẽ là Tây bồi à?

 

[gauchoigameonline]

Đây nhé bạn 1 2 3.
View attachment 245352

Bạn ơi, gửi giúp mk file text để tham khảo được không. Thank bạn nhé!

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

Xổ thiếng Anh tưng bừng như ngày hội thì không giỏi chẳng nhẽ là Tây bồi à?

Đúng rồi bạn, Tây bồi mà. Từ nào mà khó diễn đạt ngữ nghĩa quá chuyển sang dung tiếng Tây cho dễ
(Sửa lại cho bạn hiểu đúng ngữ nghĩa của câu này nhé!)

 

[VetMini]

...
Đúng rồi bạn, Tây bồi mà. Từ nào mà khó diễn đạt ngữ nghĩa quá chuyển sang dung tiếng Tây cho dễ

In such case, you should not have had any problems following the key words in post #9.
Searching "postman problem algorithm" would have given you hundreds of solutions.

Đúng là trường hợp này dùng tiếng Tây mới dễ diễn tả cái ý trong các cụm từ tô đậm.

 

[tigertiger]

Đây nhé bạn (File đăng lên chỉ chứa đc 1 Sheet hay sao ấy, file nguồn của mk vẫn có 2 Sheet mà).

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

Mình chẳng thấy phần chạy ở đâu vậy bạn?
Thực tế với giả định (mô hình Map mình lập) chương trình tự động phân biệt được nhé.
(Đang hướng tới việc xây dung hệ thống tương tự Google map trên Excel: tự nhận biết vị trí hiện tại, chỉ đường…)

Muốn làm vậy phải làm từ phần nhỏ
Phần nhỏ đầu tiên là tự tìm kiếm (tự search) tự thử, tự suy nghĩ, tự làm để hiểu vấn đề

Miết đọc topic này không biết ai hỏi ai, ai giúp ai?

 

[ptm0412]

Bạn ơi, gửi giúp mk file text để tham khảo được không. Thank bạn nhé!

Đúng rồi bạn, Tây bồi mà. Từ nào mà khó diễn đạt ngữ nghĩa quá chuyển sang dung tiếng Tây cho dễ

mk là "mẹ kiếp" hay là gì bạn? còn "cám ơn" là rất khó diễn đạt ngữ nghĩa nên phải dùng "thank" sao? Tôi ít khi bắt bẻ tiếng Anh, từ viết tắt, nhưng kiểu "mk" là rất dị ứng và kiểu biện minh vô lý cũng vậy

 

[VetMini]

mk là "mẹ kiếp" hay là gì bạn? còn "cám ơn" là rất khó diễn đạt ngữ nghĩa nên phải dùng "thank" sao? Tôi ít khi bắt bẻ tiếng Anh, từ viết tắt, nhưng kiểu "mk" là rất dị ứng và kiểu biện minh vô lý cũng vậy

Các cụm từ "cám ơn", "xin lỗi" trong tiếng Việt khá nặng. Vì văn hoá Việt nó đặt trọng các chỗ đó.
Từ "thanks", "sorry" trong tiếng Anh nó nhẹ hơn nhiều.
Vì vậy, khi muốn cám ơn hay xin lỗi một cách hời hợt, không hoàn toàn cố ý thì người ta dùng tiếng Anh.

Trong trường hợp này thì tôi tin là lý luận của thớt chấp nhận được: dùng tiếng Việt rất khó mà nói "cám ơn" trong khi bụng không hẳn 100% "cám ơn"

mk thì tôi không biết. Tôi đoán là từ moã (moi, tiếng Pháp)

 

[gauchoigameonline]

Các cụm từ "cám ơn", "xin lỗi" trong tiếng Việt khá nặng. Vì văn hoá Việt nó đặt trọng các chỗ đó.
Từ "thanks", "sorry" trong tiếng Anh nó nhẹ hơn nhiều.
Vì vậy, khi muốn cám ơn hay xin lỗi một cách hời hợt, không hoàn toàn cố ý thì người ta dùng tiếng Anh.

Trong trường hợp này thì tôi tin là lý luận của thớt chấp nhận được: dùng tiếng Việt rất khó mà nói "cám ơn" trong khi bụng không hẳn 100% "cám ơn"

mk thì tôi không biết. Tôi đoán là từ moã (moi, tiếng Pháp)

Các bạn nghĩ sao vậy, mình không nghĩ được sâu xa như vậy đâu. Sao không nghĩ đơn giản hơn chút cho cuộc sống nó nhẹ nhàng nhỉ? Đơn giản:
Tùy từng văn hóa vùng miền, thói quen, lứa tuổi... mà ngôn ngữ giao tiếp có thể khác nhau.
Và quan trọng hơn chính là cách nhìn của bản thân mỗi người là hướng tích cực hay tiêu cực thôi ^^

 

[ptm0412]

Các bạn nghĩ sao vậy, mình không nghĩ được sâu xa như vậy đâu. Sao không nghĩ đơn giản hơn chút cho cuộc sống nó nhẹ nhàng nhỉ? Đơn giản:
Tùy từng văn hóa vùng miền, thói quen, lứa tuổi... mà ngôn ngữ giao tiếp có thể khác nhau.
Và quan trọng hơn chính là cách nhìn của bản thân mỗi người là hướng tích cực hay tiêu cực thôi ^^

Ở trên tôi nhắc bạn trên cương vị là quản trị diễn đàn và căn cứ vào nội quy để giữ gìn sự trong sáng của tiếng Việt. Nếu như bạn không bỏ những từ ngữ kiểu chat chit như mk, mn, ... thì tôi sẽ xoá bài. Từ tiếng Anh thì nội quy chưa có, nhưng là thể hiện văn hoá và sự tôn trọng cũng như tự trọng.
Văn hoá là những điều tốt đẹp chứ không phải những kiểu ngôn ngữ giao tiếp như vậy. Vùng miền lại càng không có. Đây lại là 1 thứ biện minh vô lý khác

 

[VetMini]

Các bạn nghĩ sao vậy, mình không nghĩ được sâu xa như vậy đâu. Sao không nghĩ đơn giản hơn chút cho cuộc sống nó nhẹ nhàng nhỉ? Đơn giản:
Tùy từng văn hóa vùng miền, thói quen, lứa tuổi... mà ngôn ngữ giao tiếp có thể khác nhau.
Và quan trọng hơn chính là cách nhìn của bản thân mỗi người là hướng tích cực hay tiêu cực thôi ^^

Thì chính vì hai cái từ văn hoá, và cái vụ vùng miền, vân vân,... mà tôi không muốn ba cái tiếng ba rọi ấy lan qua "văn hoá vùng miền" của tôi.
Đối với bạn thì quan trọng ở chỗ qua cho xong cho nên nói búa xua tiếng Tây là tích cực.
Đối với tôi, cái quan trọng là văn hoá Việt cho nên tôi thấy Tây bồi là tiêu cực.

Cái quan trọng hơn nữa là ở đây tôi không phải là người nhờ vết code.
Nếu từ đầu tôi cảm thấy xứng đáng "tích cực" thì đã bỏ công dịch C++ sang VBA rồi. Đâu đợi đến giờ này.

 

[CHAOQUAY]

Các bạn nghĩ sao vậy, mình không nghĩ được sâu xa như vậy đâu. Sao không nghĩ đơn giản hơn chút cho cuộc sống nó nhẹ nhàng nhỉ? Đơn giản:
Tùy từng văn hóa vùng miền, thói quen, lứa tuổi... mà ngôn ngữ giao tiếp có thể khác nhau.
Và quan trọng hơn chính là cách nhìn của bản thân mỗi người là hướng tích cực hay tiêu cực thôi ^^

Theo bạn, phần chữ đậm có liên quan gì tới việc cộng điểm khi thi đại học không bạn?

 

[batman1]

2 điểm thì đâu phải tìm nữa.

Bạn không hiểu ý tác giả rồi.

Bài toán: cho vd. 10 điểm A, B, ..., I, J.
1. Bài của tác giả. Trong tất cả những con đường đi từ A tới J mà đi quả tất cả 10 điểm hãy tìm lộ trình ngắn nhất.

2. Bài toán "đi qua 2 điểm" mà tác giả lưu ý bạn. Trong tất cả những con đường đi từ A tới J tìm lộ trình ngắn nhất.

Nên biết rằng trong bài 2 có thể giữa A và J không có đường trực tiếp. Vậy mọi lộ trình trong trường hợp tổng quát là đường gấp khúc có ít nhất 2 đoạn. Hãy tìm đường gấp khúc ngắn nhất. Không có đòi hỏi đi qua tất cả các điểm đã cho như bài 1. Và thuật toán cho bài 2 tác giả cũng đã biết. Đó là thuật toán Dijkstra.

 

[batman1]

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

Hồi xưa tôi cũng tò mò. Tò mò thôi chứ không bao giờ công việc của tôi đòi hỏi kiến thức toán. Nhưng cái tò mò kia cũng gần 40 năm rồi. Tôi không có code.

 

[gauchoigameonline]

Hồi xưa tôi cũng tò mò. Tò mò thôi chứ không bao giờ công việc của tôi đòi hỏi kiến thức toán. Nhưng cái tò mò kia cũng gần 40 năm rồi. Tôi không có code.

Hi, cám ơn bạn nhều nhé!