Giới thiệu
Trong các thuật toán, cũng như trong cuộc sống, sự tiêu cực có thể là lực cản.
Hãy xem xét vấn đề tìm đường đi ngắn nhất giữa hai điểm trên biểu đồ — một mạng lưới các nút được kết nối bằng liên kết hoặc cạnh. Thông thường, các cạnh này không thể hoán đổi cho nhau: Biểu đồ có thể biểu thị bản đồ đường đi mà trên đó một số đường chậm hơn các đường khác hoặc có phí cầu đường cao hơn. Các nhà khoa học máy tính giải thích cho những khác biệt này bằng cách ghép nối từng cạnh với một “trọng lượng” định lượng chi phí di chuyển qua phân khúc đó — cho dù chi phí đó đại diện cho thời gian, tiền bạc hay thứ gì khác. Từ những năm 1950, họ đã biết cách tìm đường đi ngắn nhất về cơ bản là nhanh nhất có thể về mặt lý thuyết, giả sử tất cả các trọng số đều là số dương.
Nhưng trên một số biểu đồ, trọng số có thể âm — việc di chuyển dọc theo một đoạn có thể bù đắp chi phí đi qua một đoạn khác. Ví dụ, hãy xem xét một tài xế giao hàng phải cân bằng chi phí xăng và phí cầu đường (được biểu thị bằng trọng lượng dương) với thu nhập từ việc vận chuyển các kiện hàng (được biểu thị bằng trọng lượng âm). Trong những trường hợp như vậy, thuật toán đường đi ngắn nhất đã biết nhanh nhất không hoạt động. Trong nhiều thập kỷ, các thuật toán nhanh để tìm đường đi ngắn nhất trên đồ thị có trọng số âm vẫn khó nắm bắt.
Giờ đây, bộ ba nhà khoa học máy tính đã giải quyết được vấn đề tồn tại từ lâu này. mới của họ thuật toán, tìm các đường đi ngắn nhất qua biểu đồ từ một nút "nguồn" nhất định đến mọi nút khác, gần như khớp với tốc độ mà các thuật toán trọng số dương đã đạt được từ lâu.
Hơn nữa, cách tiếp cận mới sử dụng các kỹ thuật toán học đã có hàng thập kỷ, tránh xa các phương pháp tinh vi hơn đã thống trị nghiên cứu lý thuyết đồ thị hiện đại.
“Tôi không thể tin rằng một thuật toán đơn giản như vậy lại tồn tại,” anh nói Maximilian Probst Gutenberg, một nhà khoa học máy tính tại Viện Công nghệ Liên bang Thụy Sĩ Zurich. “Tất cả đã ở đó 40 năm rồi. Chỉ cần ai đó thực sự thông minh và quyết tâm thì mọi việc sẽ thành công.”
Giới hạn của lòng tham
Câu chuyện bắt đầu vào năm 1956, khi nhà khoa học máy tính người Hà Lan Edsger Dijkstra phát triển một thuật toán nhanh để tìm đường đi ngắn nhất trên biểu đồ chỉ có trọng số dương. Để hiểu nó, hãy tưởng tượng bắt đầu từ nguồn và khám phá biểu đồ một nút tại một thời điểm, ghi lại trọng số của các cạnh mới được phát hiện khi bạn đi. Mỗi khi bạn truy cập một nút, hãy ước tính sơ bộ các đường đi ngắn nhất từ nguồn đến từng nút lân cận của nút mới, cập nhật bất kỳ ước tính hiện có nào nếu bạn đã tìm thấy một đường dẫn mới ngắn hơn. Để quyết định nút nào chưa được khám phá sẽ truy cập tiếp theo, hãy sử dụng cái được gọi là chiến lược tham lam: Truy cập bất kỳ nút nào gần nguồn nhất theo ước tính hiện tại của bạn.
Với trọng số dương, đường đi mà thuật toán Dijkstra đi đến mỗi nút lần đầu tiên thực sự là ngắn nhất. Dễ thấy nhất là điều này đúng ngay từ bước đầu tiên. Tưởng tượng hai nút A và B được nối với nhau bằng một cạnh có trọng số 2. Nếu A là nút nguồn và mọi cạnh khác chạm vào nó đều có trọng số lớn hơn, thì đường đi trực tiếp từ A đến B phải là đường đi ngắn nhất có thể nối hai điểm đó , vì đoạn đầu tiên của bất kỳ đường dẫn nào khác sẽ dài hơn. Lý luận tương tự hoạt động ở mỗi bước. Thuật toán không bao giờ phải nhìn lại, vì vậy nó được đảm bảo hoàn thành sau khi chạy qua đồ thị một lần — đó là lý do khiến thuật toán trở nên nhanh như vậy.
Nhưng trọng số âm báo hiệu rắc rối cho chiến lược tham lam của Dijkstra. Hãy xem xét lại tài xế giao hàng của chúng tôi. Một con đường trực tiếp từ A đến B thu được một khoản lợi nhuận nhỏ có thể kiếm được ít tiền hơn một con đường quanh co có một khoản tiền lớn ở đâu đó. “Bạn không thể đưa ra quyết định chỉ dựa trên thông tin địa phương,” nói Sanjeev Khanna, một nhà khoa học máy tính tại Đại học Pennsylvania. “Bạn có thể phải thực hiện một số nước đi có vẻ dưới mức tối ưu để cuối cùng nhận được phần thưởng thực sự.”
Trong nhiều thập kỷ, các nhà khoa học máy tính làm việc trên đồ thị có trọng số âm đã cố gắng khớp tốc độ của thuật toán Dijkstra với các thuật toán “tổ hợp” tương tự. Chúng liên quan đến các hoạt động rời rạc — như khả năng đếm, sửa đổi trọng số và xóa có chọn lọc các cạnh — phản ánh cấu trúc rời rạc của biểu đồ bên dưới. Tuy nhiên, tiến độ đã chậm lại vào những năm 1990. Gần đây hơn, các nhà nghiên cứu đã sử dụng các thuật toán “tối ưu hóa liên tục”, mượn các thủ thuật từ giải tích. Thật không may, việc tăng tốc kết quả đã bị hạn chế và thường phải trả giá bằng sự đơn giản.
Phá vỡ chu kỳ
Vào mùa hè năm 2021, hai nhà khoa học máy tính trở thành đồng nghiệp tại Đại học Copenhagen — Danupon Nanongkai và Christian Wulff-Nilsen — đang tìm kiếm một chủ đề cho một dự án nghiên cứu chung. “Christian nói, 'Ồ, nhân tiện, tôi đang trong kỳ nghỉ, và vì vậy tôi đang cố nghĩ về một điều gì đó rất tham vọng',” Nanongkai, hiện đang làm việc tại Viện Tin học Max Planck ở Saarbrucken, Đức, nhớ lại. Họ giải quyết vấn đề đường đi ngắn nhất có trọng số âm và mời Aaron Bernstein của Đại học Rutgers để tham gia cùng họ.
Cả ba nhà nghiên cứu đều là chuyên gia về thuật toán đồ thị tổ hợp cho các bài toán khác và họ muốn xem những phương pháp tương đối cổ xưa này có thể giúp họ tiến xa đến đâu. Bernstein nói: “Thực sự có một sự tự do nhất định khi nghiên cứu một vấn đề đầy tham vọng và đã được mở ra trong một thời gian dài.
Bộ ba bắt đầu bằng cách tạm thời bỏ qua một tập con các đồ thị khả dĩ: những đồ thị chứa các chu kỳ âm. Đây là những đường dẫn vòng trở lại nơi chúng bắt đầu sau khi đi qua một loạt các cạnh có trọng số cộng lại thành một số âm. Trong biểu đồ có các chu kỳ âm có thể đi tới từ điểm bắt đầu, khái niệm về đường đi ngắn nhất bị phá vỡ, vì bạn có thể đặt khoảng cách tới bất kỳ nút nào là âm (hoặc có lãi) tùy thích, bằng cách thực hiện các vòng lặp lại xung quanh chu kỳ âm trước đó. đi đến đích của bạn.
Các nhà nghiên cứu nghi ngờ rằng các đường âm dài là nguyên nhân chính khiến bài toán trở nên khó khăn. Vì vậy, họ bắt đầu tập trung vào các cụm chặt chẽ gồm các nút lân cận, không thể chứa bất kỳ đường dẫn âm dài nào: Đó là bởi vì nếu hai điểm được kết nối bằng một đường dẫn dương ngắn, thì việc thêm một đường dẫn âm dài vào giữa chúng sẽ tạo ra một chu kỳ âm. Trong một cụm chặt chẽ, “việc mọi người ở gần nhau theo nghĩa tích cực cũng thực sự cung cấp cho bạn thông tin hữu ích về các khía cạnh tiêu cực,” Bernstein nói. “Nó cho bạn biết mọi thứ không thể quá tiêu cực.”
Hầu hết các biểu đồ chứa nhiều cụm liên kết chặt chẽ như vậy chỉ được kết nối yếu với nhau. Nếu các nhà nghiên cứu có thể xác định chính xác tất cả các cụm, họ nghi ngờ rằng họ có thể phát triển một cách để nhanh chóng tìm ra những con đường ngắn nhất trong mỗi cụm. Từ đó, họ có thể dễ dàng hơn trong việc kết nối các cụm riêng lẻ và tìm đường đi ngắn nhất trên biểu đồ ban đầu. Nhưng điều đó sẽ yêu cầu nhanh chóng phát hiện ra các vùng của bất kỳ biểu đồ nào trong đó các nút ở gần nhau — điều mà họ không biết cách thực hiện. Chìa khóa hóa ra lại là một kỹ thuật bắt nguồn từ một nhánh hoàn toàn khác của lý thuyết đồ thị.
Cắt đồ thị
Vào những năm 1980, các nhà khoa học máy tính đã phát triển một kỹ thuật gọi là phân tách đường kính thấp để chọn ra các cụm chặt chẽ trong biểu đồ và xác định các cạnh cần xóa để tách các cụm đó. Kỹ thuật này cung cấp một cách để chia đồ thị thành các phần độc lập. Nó được phát minh để hỗ trợ các thuật toán “phân tán”, trong đó các phép tính chạy song song trên các phần khác nhau của biểu đồ, do đó rõ ràng là nó ít hữu ích hơn đối với các thuật toán đường đi ngắn nhất, vốn không có thuộc tính này.
Bernstein, Nanongkai và Wulff-Nilsen nhận ra rằng sự phân tách đường kính thấp có thể giúp họ xác định các cụm mà không có nhiều tiêu cực tập trung. Thật không may, các thuật toán phân tách đường kính thấp tiêu chuẩn chỉ hoạt động trên các đồ thị vô hướng — những đồ thị mà mọi cạnh có thể được duyệt theo cả hai hướng. Trong khi đó, bài toán đường đi ngắn nhất có trọng số âm chỉ có ý nghĩa trên đồ thị có hướng, trong đó mỗi cạnh là đường một chiều. (Nếu không, một cạnh âm vô hướng duy nhất sẽ tạo ra một chu kỳ âm bao gồm các bước nhảy lặp đi lặp lại qua cạnh đó.) Nếu các nhà nghiên cứu muốn sử dụng phân tách đường kính thấp, họ phải điều chỉnh nó.
Đó là những gì họ đã làm trong bài báo mới của họ. Lấy cảm hứng từ công việc quá khứ trong đó Bernstein và Wulff-Nilsen đã hợp tác với Probst Gutenberg, họ đã phát triển một quy trình bẻ khóa cho các đồ thị có hướng tương tự như phân tách đường kính thấp. Quy trình này cắt một biểu đồ có hướng tùy ý thành một loạt các cụm liên kết chặt chẽ bằng cách sử dụng một quy trình ngẫu nhiên để chỉ xóa một số cạnh. Sau đó, các cụm đó được kết nối bởi một mạng lưới thưa thớt hơn, trong đó tất cả các cạnh đều chỉ về cùng một hướng. Loại mạng đó được gọi là đồ thị tuần hoàn có hướng, hay DAG.
Hãy nghĩ về một DAG giống như một dòng nước trong đó nước có thể chảy theo các đường khác nhau: Một số đường chảy vào từ các nguồn khác nhau, một số khác chảy ra theo các hướng khác nhau và vẫn còn những đường khác có thể tách ra và hợp nhất lại với nhau. Nhưng không có gì chảy ngược lại, vì vậy không có chu kỳ; điều này làm cho DAG dễ làm việc hơn nhiều.
Các nhà nghiên cứu từ lâu đã biết cách nhanh chóng tìm ra các đường đi ngắn nhất trên DAG ngay cả với trọng số âm. Vì vậy, kỹ thuật bẻ khóa cho phép ba nhà nghiên cứu giảm bất kỳ biểu đồ có hướng nào thành sự kết hợp của hai trường hợp đặc biệt — DAG và cụm chặt chẽ — mỗi trường hợp đều dễ xử lý.
Thuật toán đường đi ngắn nhất mới liên tục sử dụng quy trình bẻ khóa để chia biểu đồ thành các cụm liên kết chặt chẽ được kết nối bởi một DAG. Sau đó, nó phá vỡ các cụm đó ngày càng xa hơn. Vào cuối quá trình, các cụm ở cấp độ trong cùng được kết nối chặt chẽ nhất có thể. Một phần lý do thuật toán quá nhanh là vì nó không mất nhiều lần lặp lại để chia nhỏ hoàn toàn ngay cả một biểu đồ rất lớn, cũng như không mất nhiều thời gian để cắt một số lớn xuống kích thước hợp lý nếu bạn chia nhiều lần. nó một nửa.
Với biểu đồ được chia nhỏ hoàn toàn theo cách này, các nhà nghiên cứu có thể nhanh chóng tìm ra các đường đi ngắn nhất qua mọi phần của biểu đồ. Đối với các cụm chặt chẽ ở mức trong cùng của cấu trúc biểu đồ lồng nhau, điều này thật dễ dàng - thực tế chúng không còn tiêu cực. Và các nhà nghiên cứu đã biết cách tìm đường đi ngắn nhất trên các phần DAG nối với chúng.
Cuối cùng, thuật toán cộng lại các cạnh bị loại bỏ bởi quá trình bẻ gãy và tính toán tác động của chúng trên các đường đi ngắn nhất. Các nhà nghiên cứu đã chứng minh rằng quy trình xóa ngẫu nhiên các cạnh của họ hầu như luôn chỉ yêu cầu một vài thao tác xóa để loại bỏ các cạnh “lạc hậu” — loại sẽ biến DAG của họ thành một biểu đồ có chu kỳ lớn. Điều đó khiến cho rất khó có khả năng bất kỳ đường đi ngắn nhất nào đi qua quá nhiều đoạn lùi như vậy, vì vậy họ có thể giải quyết bước cuối cùng phức tạp này bằng cách kết hợp hai phương pháp trong sách giáo khoa từ những năm 1950: thuật toán Dijkstra và thuật toán đầu tiên được phát triển cho đồ thị có trọng số âm.
Khanna nói: “Đó là một sự kết hợp cực kỳ thông minh của những ý tưởng này. Thuật toán này là thuật toán đầu tiên dành cho đồ thị có trọng số âm chạy trong thời gian “gần tuyến tính” — có nghĩa là thời gian chạy của nó gần như tỷ lệ thuận với thời gian cần thiết chỉ để đếm tất cả các cạnh, nhanh nhất có thể.
Còn những đồ thị có chu kỳ âm mà các nhà nghiên cứu đã quyết định bỏ qua ngay từ đầu thì sao? Sau khi hoàn thiện thuật toán đường đi ngắn nhất của mình, họ đã chỉ ra rằng nó cũng có thể hoạt động như một thuật toán nhanh để xác định chính xác các chu kỳ âm. Hầu như không có biểu đồ nào nằm ngoài tầm với của nó.
đường dẫn song song
Bernstein đã trình bày kết quả của nhóm tại hội nghị Nền tảng Khoa học Máy tính năm 2022, nơi bản thảo mô tả thuật toán mới của họ được coi là một trong hai bài báo hay nhất. Các giấy khác cũng tình cờ mô tả một thuật toán thời gian cận tuyến tính mới để giải quyết một vấn đề đã tồn tại từ lâu trong lý thuyết đồ thị.
Thuật toán đó, được phát triển bởi Probst Gutenberg và năm nhà nghiên cứu khác, đã giải quyết một vấn đề tổng quát hơn gọi là luồng chi phí tối thiểu, trong đó mục tiêu là tối ưu hóa việc vận chuyển qua nhiều đường song song và mỗi cạnh có công suất tối đa cũng như chi phí liên quan . Các vấn đề về đường đi ngắn nhất là một trường hợp đặc biệt của luồng chi phí tối thiểu, vì vậy thuật toán luồng chi phí tối thiểu mới cũng có thể được sử dụng để giải quyết vấn đề về đường đi ngắn nhất có trọng số âm trong thời gian gần tuyến tính, mặc dù với một cách tiếp cận hoàn toàn khác.
Nhóm làm việc về luồng chi phí tối thiểu đã phát triển thuật toán nhanh cho mục đích chung của họ bằng cách sử dụng tổng hợp phức tạp các kỹ thuật tối ưu hóa tổ hợp và liên tục khiến thuật toán này trở nên khó sử dụng trong thực tế, ít nhất là ở thời điểm hiện tại. Thuật toán tổ hợp của Bernstein và các đồng nghiệp của ông, mặc dù bị giới hạn trong một vấn đề cụ thể hơn, đạt được thời gian chạy gần tuyến tính của nó mà không làm mất đi tính đơn giản.
“Đây là điều rất đáng kinh ngạc về bài báo này,” Probst Gutenberg nói. “Bạn có thể giải thích nó cho một sinh viên đại học và bạn cũng có thể thực hiện nó trên máy tính của mình.”
Kết quả là, thuật toán mới này đã làm sống lại sự quan tâm đến cách tiếp cận tổ hợp đối với các vấn đề khác trong lý thuyết đồ thị. Vẫn còn phải xem vấn đề nào có thể được giải quyết nhanh chóng bằng cách sử dụng các thuật toán tổ hợp thuần túy và vấn đề nào thực sự đòi hỏi các kỹ thuật liên tục được phát triển trong 20 năm qua.
“Đây là một câu hỏi triết học mà tôi đang cố hiểu,” Nanongkai nói. “Bài toán đường đi ngắn nhất này mang lại chút hy vọng.”
- Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
- Platoblockchain. Web3 Metaverse Intelligence. Khuếch đại kiến thức. Truy cập Tại đây.
- nguồn: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/
- 20 năm
- 2021
- 2022
- a
- Giới thiệu
- Theo
- Tài khoản
- đạt được
- ngang qua
- thực sự
- xoay vòng
- thích ứng
- Thêm
- Sau
- chống lại
- thuật toán
- thuật toán
- Tất cả
- Đã
- luôn luôn
- đầy tham vọng
- Xưa
- và
- Một
- ngoài
- phương pháp tiếp cận
- cách tiếp cận
- xung quanh
- liên kết
- trở lại
- Cân đối
- dựa
- bởi vì
- trở nên
- trước
- bắt đầu
- Tin
- Bernstein
- BEST
- giữa
- Ngoài
- lớn
- vay
- Chi nhánh
- Nghỉ giải lao
- nghỉ giải lao
- Bị phá vỡ
- tính toán
- gọi là
- Sức chứa
- trường hợp
- trường hợp
- nhất định
- CIS
- Đóng
- chặt chẽ
- cụm
- hợp tác
- đồng nghiệp
- kết hợp
- kết hợp
- Đến
- tính toán
- máy tính
- Khoa học Máy tính
- Tập trung
- Hội nghị
- kết nối
- Kết nối
- Hãy xem xét
- Bao gồm
- liên tục
- Phí Tổn
- có thể
- tạo
- Current
- Hiện nay
- Cắt
- chu kỳ
- DAG
- thập kỷ
- quyết định
- quyết định
- giao hàng
- mô tả
- điểm đến
- xác định
- phát triển
- phát triển
- ĐÃ LÀM
- sự khác biệt
- khác nhau
- khó khăn
- trực tiếp
- hướng
- phát hiện
- khoảng cách
- Không
- dont
- xuống
- trình điều khiển
- Tiếng Hà Lan
- mỗi
- kiếm được
- dễ dàng hơn
- dễ nhất
- Cạnh
- hiệu ứng
- loại bỏ
- loại bỏ
- kích hoạt
- hoàn toàn
- chủ yếu
- ước tính
- dự toán
- Ngay cả
- BAO GIỜ
- mọi người
- hiện tại
- tồn tại
- các chuyên gia
- Giải thích
- Khám phá
- cực kỳ
- tạo điều kiện
- fan hâm mộ
- NHANH
- nhanh nhất
- Liên bang
- vài
- cuối cùng
- Cuối cùng
- Tìm kiếm
- tìm kiếm
- tìm thấy
- Tên
- lần đầu tiên
- dòng chảy
- Chảy
- Tập trung
- tìm thấy
- Foundations
- Freedom
- từ
- đầy đủ
- xa hơn
- GAS
- Tổng Quát
- mục đích chung
- Nước Đức
- được
- được
- cho
- Go
- mục tiêu
- đồ thị
- đồ thị
- Tham lam
- đảm bảo
- Gutenberg
- Một nửa
- số ít
- xử lý
- đã xảy ra
- Nhóm
- giúp đỡ
- cao hơn
- mong
- Độ đáng tin của
- Hướng dẫn
- Tuy nhiên
- HTML
- HTTPS
- ý tưởng
- xác định
- thực hiện
- in
- lợi tức
- độc lập
- hệ thống riêng biệt,
- thông tin
- lấy cảm hứng từ
- ví dụ
- Viện
- quan tâm
- Phát minh
- liên quan
- IT
- sự lặp lại
- tham gia
- tham gia
- Key
- Loại
- Biết
- nổi tiếng
- lớn
- lớn hơn
- Cấp
- Cuộc sống
- Hạn chế
- giới hạn
- liên kết
- địa phương
- dài
- thời gian dài
- lâu đời
- còn
- Xem
- thực hiện
- làm cho
- LÀM CHO
- Làm
- cách thức
- nhiều
- bản đồ
- Trận đấu
- toán học
- tối đa
- tối đa
- có nghĩa
- Trong khi đó
- đi
- phương pháp
- Might
- hiện đại
- tiền
- chi tiết
- di chuyển
- di chuyển
- gần
- tiêu cực
- người hàng xóm
- Lưới
- mạng
- Mới
- tiếp theo
- nút
- các nút
- Khái niệm
- con số
- số
- bù đắp
- ONE
- mở
- Hoạt động
- tối ưu hóa
- Tối ưu hóa
- nguyên
- nguồn gốc
- Nền tảng khác
- Khác
- nếu không thì
- gói
- cặp đôi
- Giấy
- giấy tờ
- Song song
- một phần
- các bộ phận
- Đi qua
- qua
- con đường
- Pennsylvania
- chọn
- plato
- Thông tin dữ liệu Plato
- PlatoDữ liệu
- Điểm
- điểm
- tích cực
- khả năng
- có thể
- thực tế
- thực hành
- trình bày
- Vấn đề
- vấn đề
- quá trình
- Lợi nhuận
- lợi nhuận
- Tiến độ
- dự án
- tài sản
- chứng minh
- cung cấp
- hoàn toàn
- Đặt
- tạp chí lượng tử
- câu hỏi
- Mau
- triệt để
- ngẫu nhiên
- nhanh chóng
- đạt
- thực
- nhận ra
- lý do
- hợp lý
- gần đây
- giảm
- phản ánh
- vùng
- tương đối
- vẫn
- vẫn còn
- lặp đi lặp lại
- NHIỀU LẦN
- đại diện
- đại diện
- đại diện cho
- yêu cầu
- cần phải
- nghiên cứu
- nhà nghiên cứu
- chịu trách nhiệm
- hạn chế
- kết quả
- kết quả
- Khen thưởng
- đường
- Route
- chạy
- chạy
- Đại học Rutgers
- hy sinh
- Nói
- tương tự
- Khoa học
- Nhà khoa học
- các nhà khoa học
- tìm kiếm
- phần
- phân khúc
- phân đoạn
- ý nghĩa
- Loạt Sách
- Giải quyết
- một số
- ngắn
- tương tự
- Đơn giản
- đơn giản
- kể từ khi
- duy nhất
- Kích thước máy
- nhỏ
- So
- động SOLVE
- Giải quyết
- một số
- Một người nào đó
- một cái gì đó
- một nơi nào đó
- tinh vi
- nguồn
- nguồn
- đặc biệt
- riêng
- tốc độ
- ĐÁNH VẦN
- chia
- Tiêu chuẩn
- Bắt đầu
- bắt đầu
- Bắt đầu
- Bước
- Vẫn còn
- Câu chuyện
- Chiến lược
- dòng
- đường phố
- cấu trúc
- Sinh viên
- như vậy
- mùa hè
- Thụy Sĩ
- Hãy
- mất
- dùng
- nhóm
- kỹ thuật
- Công nghệ
- nói
- sách giáo khoa
- Sản phẩm
- Đồ thị
- Nguồn
- cung cấp their dịch
- điều
- số ba
- Thông qua
- thời gian
- đến
- bên nhau
- quá
- chủ đề
- sờ vào
- vận chuyển
- Đi du lịch
- rắc rối
- đúng
- XOAY
- Quay
- cơ bản
- hiểu
- trường đại học
- cập nhật
- sử dụng
- kỳ nghỉ
- hầu như
- muốn
- Nước
- webp
- trọng lượng
- Điều gì
- liệu
- cái nào
- CHÚNG TÔI LÀ
- ở trong
- không có
- Công việc
- đang làm việc
- công trinh
- sẽ
- năm
- Bạn
- trên màn hình
- zephyrnet
- Zurich