이동 층 주문의 최단 경로를 찾기 위해 엘리베이터가 사용하는 알고리즘은 무엇입니까?
On 2월 15, 2021 by admin저는 언제나처럼 엘리베이터를 시뮬레이션하려고합니다. 저는 한 번에 하나의 주문 만받는 것으로 매우 간단하게 시작한 다음 엘리베이터에 메모리를 추가했습니다. 바닥이 눌린 순서대로 이동하는 대기열의 형태로, “최상의 접근 방식은 아닙니다.
지금은 매우 간단하고”근시적인 “방식을 사용하고 있습니다. 즉, 현재 층의 경우 가장 가까운 층을 찾아 내 다음 목적지로 설정하고 더 이상 층이 목록에 없을 때까지 반복합니다.
하지만 항상 작동하는 것은 아닙니다. 엘리베이터는 5 층 건물의 3 층에 있었고 4,5,2 주문을 받았습니다. 최단 경로는 2-> 4-> 5가되며 비용은 4 층이지만이 논리를 사용하면 비용이 5 인 4-> 5-> 2가됩니다. 코드에 따라 선택 될 확률이 동일합니다.
최단 경로를 찾고 엘리베이터를 더 효율적으로 만들려면 어떻게해야합니까?
댓글
- 다소 관련 : programmers.stackexchange.com/q/96278/149904
- ' 당신을 제 사무실로 초대하여 엘리베이터가 그곳에서 사용하는 알고리즘을 알아 내고 싶습니다. 전 절대 할 수 있기 때문에 ' t.
- @ gnasher729 오, 나는 당신을 몰라도 ' 할 수 있습니다. , 왜냐하면 ' 확실히 제 사무실과 동일하기 때문입니다. 이미 가득 찬 경우를 제외하고는 제가 ' 미터에있는 층에서 멈추지 마십시오. 사람들. 제가 맞나요?
- 정답이 아닙니다. 엘리베이터가 4 대 있습니다. 버튼을 누르면 아주 오랫동안 아무것도 움직이지 않습니다. 한 사람이 움직이면 바닥 바로 앞에서 멈추고 몇 년 동안 기다렸다가 바닥을지나 내려온 다른 사람이 추월 할 때까지 기다립니다. 땅으로 내려가는 도중에 아무도 들어 가지 않고 3 번 이상 멈 춥니 다.
- 관련 프로그래밍 게임 / 도전 : play.elevatorsaga.com
답변
“효율성”은 가장 중요한 기능이 아닙니다. 가장 중요한 것은 굶주림이없는 질서를 따른다. 누군가 100을 누르고 사람들이 1과 2를 계속 누르면 그 층 사이를 계속 이동하는 것이 효율적일 수 있지만, 어떤 시점에서 100 명이 방문하는 것이 좋을 것입니다.
생각합니다 (내가 알아내는 데 관심이 있었을 때의 개인적인 관찰에서) 그들 대부분이하는 일 :
- 첫 번째 버튼을 누른 방향으로 이동하기 시작하고 우리가 어느 방향으로 가고 있는지 추적 가기
- 층에 도달하고 버튼을 눌렀을 때 문을 멈추고 열고이 층의 버튼을 더 이상 누르지 않은 것으로 표시합니다.
-
- 더 많은 층을 방문해야하는 동일한 방향이 있습니다. 그 방향으로 계속 가십시오 .
- 그렇지 않고 방문해야하는 층이 아직 남아있는 경우 이동 그 방향으로.
- 그렇지 않으면 완료되고 버튼을 다시 누를 때 1부터 시작합니다.
참고 많은 엘리베이터에는 하나의 버튼 대신에 “상승하고 싶다”와 “하강하고 싶다”라는 버튼이 문 옆에 있습니다. 알고리즘은 약간만 변경하면됩니다. 2에서 해당 층에 대해 눌려진 유일한 버튼이 문 옆의 버튼 중 하나 인 경우 해당 방향으로가는 경우에만 문을 멈추고 엽니 다. 엘리베이터 내부의 버튼이 눌려서 잘못된 방향으로 가고있어 문이 열리면 버튼을 계속 누르고있을 수 있습니다.
전체 경로 를 알아낼 필요가 없습니다. 다음으로 갈 방향으로 이동합니다.
댓글
- 이것은 완전히 생각을 잊고 효율성에 집중했고 다른 것도 중요하다는 사실을 잊었습니다. . ' 2 > 100에서 1로 돌아가는 것은 여전히 효율적이지 않습니다. 단순히 같은 방향이지만 최소한 굶주림을 보장하지 않습니다. 그리고 주제에서 완전히 벗어난 것입니다.이 논리로 엘리베이터 두 대를 찾는 것이 ' 일반적인 이유일까요? 이 때문에 ' 항상 반대 방향으로가는 엘리베이터를 찾는 것이 더 일반적인 것인지 궁금합니다. 어쨌든, 저는 ' 최단 전체 경로를 찾는 방법에 대해 여전히 궁금합니다.하지만 이것은 제 질문에 매우 깔끔하게 대답합니다. 감사합니다.
- 100 층 건물의 경우 일반적으로 특정 범위의 층 (예 : 0-19, 20-39,…)에만 서비스를 제공하는 엘리베이터와 장거리 (예 : 0 ~ 50, 0 ~ 100)로만 이동하는 고속 엘리베이터가 있습니다. , 50 ~ 100 층이지만 그 사이에 층이 없음) 목적지까지 이동하려면 엘리베이터를 바꿔야 할 수도 있습니다. 분명히 서로 통과 할 수없는 샤프트 당 여러 대의 엘리베이터가있을 수도 있습니다.주제에서 완전히 벗어남 : IIRC, 사용자 경험 사이트에있는 위쪽 및 아래쪽 화살표 버튼의 효율성에 대한 질문이 매우 흥미롭게 읽었습니다.
- 감사합니다. ' 몰랐습니다. 세분화는 한 부분이 전체 시스템을 분해하지 않고 ' 기계적 마모에 중요한 부하를 분산하는 경우 좋은 전략으로 보입니다. 이러한 급행 엘리베이터가 Knuth ' 엘리베이터 알고리즘의 논리적 결점 때문인지 궁금합니다.
- 다른 것뿐입니다. ' d 추가는 종종 ' home ' 층을 사용하지 않을 때 돌아갈 수 있다는 것입니다. 이것은 엘리베이터마다 다를 수 있으며, 시간과 예상되는 사용 패턴에 따라 변경 될 수도 있습니다.
- 어느 방향에 관계없이 위쪽 / 아래쪽 버튼을 무작위로 반쯤 누르는 경향이 있습니다. ' 실제로 여행 중입니다. 제 경우에는 목적지가 하나뿐이기 때문에 승강기를 선택하든 하강하든 상관없이 엘리베이터가 저를 그 위치로 데려다줍니다. 아래로 버튼을 누르고 내 위층을 선택한 다음 엘리베이터가 움직이기 전에 내 아래층을 선택하면 내가 먼저 밀었던 층이 아닌 내 아래층으로 이동하게 될 것입니다. 제가 틀렸을 수도 있습니다. ' 다음에 엘리베이터에서 내 자신을 발견 할 때 테스트 할 것입니다.
답변
다른 답변은 표준 엘리베이터 알고리즘을 올바르게 제공합니다. 기본적으로 “가능한 한 같은 방향으로 계속 가고 길을 따라 필요한 모든 정지를합니다”입니다.
다른 엘리베이터 알고리즘이 있습니다. 예를 들어, 올라가면 아파트가 더 비싸지는 아파트 건물을 생각해보십시오. 건물 소유주는 엘리베이터 알고리즘을 수정하여 “가능한 한 같은 방향으로 가되 내려갈 때만 정지”하도록 선택할 수 있습니다. 이렇게하면 엘리베이터에 로비에 있고 2, 5, 10으로가는 사람이있는 경우 엘리베이터는 10, 5, 2로 이동하여 임대료를내는 순서대로 내려갑니다. 그러나 물론 10 명의 사람들이 아파트를 떠나면 로비에 도착하기 위해 더 오래 기다려야 할 것입니다.
효율적인 솔루션을 찾고 있다면 그런 다음 비용에 대한 메트릭을 만들고 다양한 알고리즘을 구현하고 시뮬레이션을 실행합니다. 평균 비용뿐만 아니라 하나의 요청을 처리하는 데 가장 오래 걸리는 측정 항목도 측정해야합니다. 낮은 평균에 최적화하면 최악의 경우 최적화가 해제 될 수 있습니다.
댓글
- 아주 드물게 보입니다 (기타 오류)
답변
엘리베이터는 일부 하드 드라이브 컨트롤러와 동일한 예약 알고리즘을 사용합니다. 표준 SCAN 알고리즘은 엘리베이터 알고리즘 이라고도합니다. 실제로는 LOOK 알고리즘이 SCAN보다 약간 더 효율적이기 때문에 더 일반적이라고 생각합니다.
댓글
- 확실하게 말할 때 엘리베이터 코드 구현에 대한 전문적인 경험이 있습니까? 특히 최신 엘리베이터 시스템? NYC에서 9/11 이후 승객을 내리는 것보다 승객을 올리는 것보다 우선 순위가 더 높았는지 궁금합니다.
- 승객을 내리지 말고 나가십시오. 1 ~ 6 층의 3 층이 1 층인 주차장에서 엘리베이터를 자주 사용하므로 탈출하려면 3 층이 가장 좋습니다.
답변
이 답변은 고급 목적지 제어 시스템 에 대한 것입니다. 사람들이 가고 싶은 층을 표시하고 시스템이 엘리베이터를 할당하는 여러 개의 엘리베이터가있는 건물에서.
아이디어는 매우 간단합니다. 이론적으로 모든 사람과 모든 엘리베이터가 어디로 가는지 알고 있습니다. 따라서 각 엘리베이터에 대해 예상 도착 시간이 언제이고 다른 엘리베이터가 얼마나 느려지는지 계산할 수 있습니다. 탐욕스럽게 가장 빠른 엘리베이터를 선택하세요.
그룹이 버튼을 한 번만 누르고 사람들이 버튼을 여러 번 누르는 등의 제한이 있습니다.
답글 남기기