다음 정렬 문제에 대한 최상의 알고리즘을 찾으려고합니다.가장 좋은 좌석 지정 알고리즘은 무엇입니까?
는 N = K 있습니다 M × 하나 개의 통로와 강당에서 석, K 행 및 통로 당 M 석. K이 M보다 크지 만 매우 중요하다고는 생각하지 않습니다. N 사람들이 자리에 배정 (지정석)되어 있습니다. 사람들이 기다리는 것과 같이 을하지 않는다고 가정하면 가능한 한 빨리 모두를 얻으려고 줄을서는 가장 빠른 방법은 무엇일까요?
나는 몇 가지 간단한 실험실 기능은 (무작위 순열을 사용하여) 실행과 그들을 정렬시키는 것은 무작위로 다음 가운데 세 번째 첫 번째 줄 (자세한 통로 아래로) 앞 세 번째의 사람이하는 것보다 빠른 듯 , 그 다음 세 번째. 그건 나에게 잘못된 것처럼 보인다.MatLab에이 글을 쓰고 싶습니다. 어떤 아이디어 또는 답변?
Bachmat, Berend, Sapir, Skiena 및 Stolyarov가 비행기 탑승을위한 정확한 문제를 모델링 한 Analysis of airplane boarding via space-time geometry and random matrix theory이라는 매우 훌륭한 기사가 있습니다. 그들의 추상에서 :
우리는 비행기 탑승이 점근 2 차원 로렌 시안 구조로 모델링 수 있습니다 보여줍니다. 탑승 시간은 모델의 곡선 중 최대 시간 에 의해 주어집니다. 모델과 시뮬레이션 결과의 불일치는 과 무작위 매트릭스 이론에 밀접하게 관련되어 있습니다. 우리는 그런 다음 을 보여줍니다. 이러한 모델을 사용하여 을 자주 사용하는 이유는 무엇입니까? 탑승 정책은 효과적이지 않으며 도 해로운 것입니다. 용지의
결론은 다음과 같습니다
귀하의 설정에 대해, 나는 이것을 무시해야한다는 것을 의미한다고 생각합니다 통로 아래로 얼마나 멀리통로에서 얼마나 멀리 있습니다. 이 모델은 수하물 보관 시간도 고려하기 때문에 상황에 맞게 조정해야 할 수도 있습니다. 어쨌든 이것은 당신이 당신의 모델을 통해 무엇을 발견하고 있는지를 확인해줍니다.
모델에 대해 더 알지 못해도 대답하기가 어렵다고 생각합니다. 얼마나 많은 입구가 있고 어디에 위치합니까? 무엇 때문에 사람들은 얼마나 오래 기다려야합니까? 이미 앉아있는 같은 줄에 누군가를 지나쳐야한다면 좌석에 앉는 데 시간이 더 걸립니까? 사람들은 항상 올바른 자리로 바로 가나, 때로는 올바른 행을 찾기 위해 앞뒤로 돌아 다니는가? 기타... –
입구가 하나뿐입니다. 하나의 행을 아래로 이동하거나 한 자리를 따라 이동하는 데 1 단위 시간이 걸립니다. – Daniel
어쩌면 나는 이것을 잘못된 방향으로보고 있을지 모르지만, 당신이 (자리를 돌 때까지 기다리지 않고 섬으로 걸어가는 것을 포함하여) 결코 자리를 비운 적이없는 매우 효율적인 사람들이 있다면, 그렇게하지 않을 것입니다. 그들이 질서를 지키는 문제. 번갈아 가며 각 행의 라인에서 한 명씩 (첫 번째 줄 = 줄 앞, 마지막 줄 = 마지막 지점)을 가질 수는 없지만, 그들은 모두 섬을 걸어 다니다가 한 번에 각각의 줄을 따라 걷습니다 (린스와 반복). –