Làm thế nào để thực hiện giải pháp cho các vấn đề chủng tộc mô phỏng

Question

Có một câu hỏi được hỏi trong một cuộc phỏng vấn:

Trong một thách thức Formula-1, có n đội đánh số từ 1 đến n. Mỗi đội có một chiếc xe hơi và một tài xế. đặc điểm kỹ thuật xe của như sau:

• Tốc độ tối đa: (150 + 10 * i) km mỗi giờ
• Acceleration: (2 * i) mét vuông mỗi thứ hai.
• Hệ số xử lý (hf) = 0,8
• Nitro: Tăng tốc độ lên gấp đôi hoặc tốc độ tối đa, tùy theo mức nào thấp hơn. Chỉ có thể sử dụng một lần.

Đây là số nhóm. Những chiếc xe xếp hàng cho cuộc đua. Dòng bắt đầu cho (i + 1) thứ xe là 200 * i mét phía sau chiếc xe thứ i.

Tất cả chúng đều bắt đầu cùng một lúc và cố gắng đạt được tốc độ tối đa của chúng. Việc đánh giá lại các vị trí được thực hiện sau mỗi 2 giây (Vì vậy, ngay cả khi chiếc xe đã vượt qua vạch đích ở giữa, bạn sẽ biết sau 2 giây). Trong quá trình đánh giá này, mỗi người lái xe sẽ kiểm tra xem có xe nào trong phạm vi 10 mét của xe hơi không, tốc độ của anh ta giảm xuống: hf * (tốc độ tại thời điểm đó). Ngoài ra, nếu người lái xe nhận thấy rằng anh ta là người cuối cùng trong cuộc đua, anh ta sử dụng ‘nitro’.

Lấy số lượng đội và độ dài của bản nhạc làm đầu vào, tính toán tốc độ cuối cùng và thời gian hoàn thành tương ứng.

Tôi không hiểu cách tiếp cận loại vấn đề này. Đối với mỗi trường hợp, tôi có nên kiểm tra tất cả các kết hợp C(n,2) của mỗi cặp trình điều khiển và tính toán kết quả không? Nhưng làm thế nào tôi có thể tìm ra trường hợp nào tôi nên thực hiện các tính toán?

Answer 1

Nếu bạn kiểm tra Conway's Game of Life, bạn sẽ thấy rằng có rất nhiều điểm chung với Vấn đề về chủng tộc.

Đây là sự tương tự:

• Các trạng thái ban đầu (hạt giống của hệ thống):
  • Game of Life: mô hình ban đầu về lưới điện. Mỗi tế bào có các thông số sau:
    • x và y phối hợp
    • dù các tế bào còn sống hay đã chết
  • Vấn đề chủng tộc: n xe mỗi người có các thông số được xác định trước và chiều dài của đường l. Mỗi chiếc xe có các thông số sau:
    • tốc độ tối đa
    • tăng tốc
    • xử lý yếu tố
    • vị trí trên đường đua
    • tốc độ hiện tại
• Các quy tắc được áp dụng ở những khoảnh khắc rời rạc mà được gọi là bọ ve.
  • Game of Life: các quy tắc được áp dụng đồng thời cho mọi ô từ thế hệ trước tạo ra thế hệ tiếp theo. Mỗi thế hệ là một hàm thuần túy của cái trước.
  • Vấn đề về chủng tộc: các quy tắc được áp dụng đồng thời cho mọi xe từ trạng thái trước đó tạo ra trạng thái tiếp theo. Điều này xảy ra sau mỗi 2 giây. Tương tự như trong Game of Life, mỗi bước là một chức năng thuần túy của cái trước có nghĩa là nó chỉ phụ thuộc vào các thông số của những chiếc xe từ trạng thái trước đó.

Điều khác biệt là Game of Life không bao giờ kết thúc trong khi các vấn đề chủng tộc nên chấm dứt khi vị trí hiện tại của mỗi chiếc xe là lớn hơn hoặc bằng l theo dõi chiều dài (Mặc dù báo cáo kết quả cuối cùng là gây tranh cãi: do để các yếu tố xử lý nó có thể là trong một số điều kiện một số chiếc xe sẽ không bao giờ đạt đến đích).

Điểm mấu chốt là tính toán được thực hiện tại những khoảnh khắc rời rạc mà trả lời câu hỏi của bạn:

Nhưng làm thế nào tôi có thể tìm ra những gì dụ tôi nên làm cho các tính toán?

Bạn có thể lấy ý tưởng từ mục Algorithms để giải quyết vấn đề này. Bạn cần có 2 mảng ô tô: một ô thể hiện trạng thái hiện tại và ô còn lại đại diện cho bước tiếp theo. Trên mỗi lần lặp, bạn tính toán lại vị trí hiện tại và tốc độ của mỗi chiếc xe theo các quy tắc từ nhiệm vụ và kiểm tra xem vòng lặp có nên chấm dứt hay không. Trước lần lặp tiếp theo, bạn trao đổi các vai trò mảng sao cho mảng kế tiếp trong lần lặp cuối cùng trở thành mảng hiện tại trong lần lặp tiếp theo.

Các giả mã cấp cao có thể trông như thế này:

n = ..; // initial number of cars 
l = ..; // track length 
Car[] currentState = initializeState(n, l); 
Car[] nextState = clone(currentState); 
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) { 
    calculateNextState(currentState, nextState, iteration); 
    swap(currentState, nextState); 
    if (shouldTerminate(currentState, l) { 
     break; 
    } 
} 

printResultOrClaimNotTerminated(currentState); 

Các quy tắc được áp dụng trong calculateNextState (..) chức năng. Trong việc thực hiện ngây thơ nhất mà bạn kiểm tra tất cả các cặp xe mang đến cho bạn

O (C(n, 2)) = O (n * (n - 1)/2) = O (n^2)

phức tạp cho mỗi lần lặp. Tuy nhiên bạn có thể nghĩ về tối ưu hóa có thể có ở đây. Ví dụ bạn có thể sắp xếp các ô tô theo vị trí hiện tại trước tiên (O (n * log(n))) và sau đó đi qua mảng được sắp xếp chỉ kiểm tra các ô tô lân cận (O (2 * n)). Bạn có thể làm điều này vì nếu điều kiện 10 mét không đáp ứng cho những chiếc xe lân cận, nó sẽ không đáp ứng cho những chiếc xe không liền kề. Điều này sẽ cho bạn kết quả phức tạp của:

O (n * log(n)) 

tốt hơn nhiều. Các mảng được sắp xếp của xe sẽ tự nhiên cung cấp cho bạn chiếc xe với vị trí cuối cùng mà bạn cần phải áp dụng quy tắc tăng nitro. Có lẽ có thể có các tối ưu hóa khác. Này trả lời câu hỏi của bạn:

Đối với mỗi trường hợp tôi nên kiểm tra tất cả C (n, 2) sự kết hợp của tất cả các cặp trình điều khiển và tính toán kết quả?

Answer 2

Objects Xe Và Object

tôi giả sử rằng bạn đã tạo ra các đối tượng cần thiết cho chiếc xe, gói gọn trong một đối tượng trò chơi Game.

Ý tưởng để tăng tốc độ lên từng bước cập nhật để không làm tất cả C (n, 2) kiểm tra

Bạn có thể tăng tốc lên vị trí cập nhật và thông số bước, bằng cách không phải rà soát tất cả C (n, 2) kết hợp . Một heuristic đơn giản bạn có thể sử dụng là chúng ta không cần phải kiểm tra tương tác giữa những chiếc xe ở xa. Ví dụ, một chiếc xe trong quý đầu tiên của đường đua sẽ không tương tác với một chiếc xe trong quý thứ ba của đường đua. Tôi nghĩ dựa trên các thông số của câu hỏi của bạn, bạn muốn chia đường đua thành các đoạn dài 10m. Duy trì danh sách cho từng phần và theo dõi tất cả các xe trong mỗi phần. Sau khi cập nhật vị trí, chỉ kiểm tra tương tác giữa các ô trong các phần liên tiếp.

Tương tự, theo dõi xe nào ở vị trí cuối cùng trên mỗi bước cập nhật và chuyển đổi nitrobooster tương ứng.

Lựa chọn TimeStep

Trong câu hỏi của bạn timeStep dường như được cố định sau 2 giây. Tuy nhiên, trong một bối cảnh chung khi bạn đang mã hóa một trò chơi chẳng hạn, lựa chọn này là một lựa chọn quan trọng. Bạn có thể chơi xung quanh với một vài số khác nhau (ví dụ: 10,50,100,500 mili giây).

Nếu bạn chọn timeStep là số cao hơn, (ví dụ), ô tô có thể đi qua xe khác và tránh phát hiện va chạm. Nếu mặt khác, bạn chọn timeStep quá nhỏ và nếu thời gian thực hiện cho các hoạt động lớn hơn timeStep, trò chơi sẽ chạy chậm hơn thời gian thực.