Qual algoritmo é usado por elevadores para encontrar o caminho mais curto para percorrer os pedidos de piso?
On Fevereiro 15, 2021 by adminEstou tentando simular um elevador, como sempre, comecei de maneira muito simples, pegando apenas um pedido de cada vez, depois adicionei memória ao elevador em a forma das filas para que os pisos sejam percorridos na ordem em que foram pressionados, o que obviamente não é a melhor abordagem.
Então, no momento, estou usando um método muito simples e “míope” lógica que é, para o andar atual, encontre o andar mais próximo de mim e defina-o como meu próximo destino e faça um loop até que não haja mais andares na lista.
Mas isso nem sempre funciona, por exemplo o o elevador estava no 3º andar de um prédio de 5 andares e recebeu pedidos 4,5,2 o caminho mais curto seria 2-> 4-> 5 que custa 4 andares, mas usando esta lógica 4-> 5-> 2 que custa 5 tem a mesma chance de ser escolhido, dependendo do código.
Como faço para encontrar o caminho mais curto e tornar o elevador mais eficiente?
Comentários
- Algo relacionado: programmers.stackexchange.com/q/96278/149904
- Eu ‘ gostaria de convidá-lo para o meu escritório e descobrir o algoritmo que os elevadores usam lá. Porque eu absolutamente não posso ‘ t.
- @ gnasher729 Oh, eu posso, embora eu não ‘ não conheça você , porque ‘ é certamente o mesmo que no meu escritório: nunca pare no andar que ‘ m dentro, exceto quando já estiver cheio de pessoas. Estou certo?
- Não exatamente. Existem quatro elevadores. Você pressiona o botão, nada se move por um longo tempo. Se um se mover, ele para bem antes do seu chão e espera por séculos, até que seja ultrapassado por outro que passa pelo seu chão e depois desce. No caminho para o solo, ele para pelo menos três vezes sem ninguém entrar.
- Jogo / desafio de programação relevante: play.elevatorsaga.com
Resposta
“Eficiência” não é o recurso mais importante, o mais importante é garantir que cada a ordem é seguida, para que não haja fome. Se alguém pressiona 100 e as pessoas continuam pressionando 1 e 2, pode ser eficiente continuar entre esses andares, mas seria bom que 100 fossem visitados em algum momento.
Eu acho (por observação pessoal quando eu estava interessado em descobrir) que a maioria deles faz:
- Comece a ir na direção do primeiro botão pressionado, acompanhe a direção em que estamos indo
- Quando chegar a um andar e esse botão for pressionado, pare e abra as portas, marque os botões para este andar como não mais pressionados.
-
- Se ainda há mais andares que precisamos visitar que estão na mesma direção, continue nessa direção .
- Se não e ainda haja andares que precisamos visitar, mude nessa direção.
- Caso contrário, terminamos e começaremos em 1 quando um botão for pressionado novamente.
Observação que muitos elevadores têm botões “Quero subir” e “Quero descer” ao lado das portas em vez de um único botão. o algoritmo só precisa de uma pequena mudança: em 2, se o único botão pressionado para aquele andar for um dos botões ao lado da porta, só pare e abra as portas se formos nessa direção. Possivelmente mantenha o botão pressionado se as portas se abrirem por causa de um botão pressionado dentro do elevador e ele estiver indo na direção errada.
Você nunca precisa descobrir um caminho inteiro, apenas em que direção tomar a seguir.
Comentários
- isso me escapou completamente, eu estava tão focado na eficiência e esqueci que outras coisas também são importantes . ainda ‘ não é eficiente ir, digamos, de 2- > 100 e voltar para 1 simplesmente porque estava na mesma direção, mas em pelo menos, não garante nenhuma fome. e, completamente fora do assunto, talvez seja por isso que ‘ é comum encontrar dois elevadores com essa lógica? o que me faz pensar se é ‘ mais comum encontrar os elevadores indo na direção oposta a qualquer momento. de qualquer forma, eu ‘ ainda estou curioso sobre como encontrar o caminho inteiro mais curto, mas isso responde minha pergunta muito bem, obrigado
- Observe que quando você chegar a um edifício com 100 andares, você normalmente terá elevadores atendendo apenas uma faixa específica de andares (por exemplo, 0-19, 20-39, …), bem como elevadores expressos que só percorrem longas distâncias (por exemplo, 0 a 50, 0 a 100 , 50 a 100, mas sem andares entre eles), então você pode ter que trocar de elevadores para chegar ao seu destino. Você também pode ter vários elevadores por poço que obviamente não podem passar uns pelos outros.Totalmente fora do assunto: IIRC, havia uma dúvida sobre a eficiência dos botões de seta para cima e para baixo no site Experiência do usuário que proporcionou uma leitura fascinante.
- obrigado, eu não ‘ não sabia disso. subdividir parece uma boa estratégia se uma parte quebrar todo o sistema não ‘ te também para distribuir a carga que é importante para o desgaste mecânico. Eu me pergunto se esses elevadores expressos foram devido às deficiências lógicas do algoritmo de elevador Knuth ‘ s.
- apenas outra coisa i ‘ d adicionar é que muitas vezes eles têm um ‘ andar ‘ ao qual voltarão quando não estiverem em uso, isso pode ser diferente para elevadores diferentes e possivelmente até mesmo mudar dependendo da hora do dia e dos padrões de uso esperados
- Tenho uma tendência a apertar o botão para cima / para baixo de forma semi-aleatória, independentemente da direção que eu ‘ estou realmente viajando. No meu caso, só tenho um destino, então o elevador me leva até esse local, independentemente de eu ter escolhido subir ou descer. Suspeito que se eu pressionasse o botão de descer, escolhesse um andar acima de mim e, em seguida, escolhesse um andar abaixo de mim antes que o elevador começasse a se mover, isso me levaria para o andar abaixo de mim, em vez do andar que empurrei primeiro. Posso estar errado, ‘ terei certeza de testá-lo da próxima vez que me encontrar em um elevador.
Resposta
A outra resposta fornece corretamente o algoritmo de elevador padrão, que é basicamente “continue na mesma direção o maior tempo possível e faça todas as paradas necessárias ao longo do caminho”.
Existem outros algoritmos de elevador. Por exemplo, considere um prédio de apartamentos onde os apartamentos ficam mais caros à medida que você sobe. Os proprietários do edifício podem optar por modificar o algoritmo do elevador para “ir na mesma direção o maior tempo possível, mas só parar na descida”. Dessa forma, se você tiver pessoas no elevador que estão no saguão e vão para 2, 5 e 10, o elevador vai para 10, depois para 5, depois para 2, deixando as pessoas na ordem de quanto pagam de aluguel. Mas é claro que, quando as pessoas no número 10 saem de seus apartamentos, com mais frequência terão que esperar mais para chegar ao saguão.
Se você está procurando uma solução eficiente em seguida, crie uma métrica de custo e implemente vários algoritmos diferentes e execute simulações. Lembre-se de medir não apenas o custo médio, mas também métricas como o tempo máximo que uma solicitação leva para ser atendida. Otimizar para médias baixas às vezes pode desotimizar o pior caso, o que é ruim.
Comentários
- Parece ser raro (outros alogirthms)
Resposta
Observe que os elevadores usam os mesmos algoritmos de programação que alguns controladores de disco rígido. O algoritmo SCAN padrão é conhecido como algoritmo de elevador . Acho que, na prática, o algoritmo LOOK é mais comum, pois é um pouco mais eficiente do que SCAN.
Comentários
- Quando você fala com certeza, você tem experiência profissional na implementação do código para elevadores? Especialmente os sistemas de elevador mais novos? Estou curioso para saber se, depois do 11 de setembro em Nova York, houve maior prioridade em mandar passageiros para baixo do que trazê-los para cima.
- Tire os passageiros de lá, não para baixo. Costumo usar o elevador em um estacionamento, onde o terceiro andar dos andares 1 a 6 é o térreo, então, para escapar, o andar 3 seria o melhor.
Resposta
Esta resposta é sobre um sistema de controle de destino mais avançado. Em um prédio com vários elevadores onde as pessoas indicam para qual andar desejam ir e o sistema designa um elevador para elas.
A ideia é bastante simples, teoricamente você sabe para onde todos e cada um estão indo. Assim, você pode, para cada elevador, calcular quando é a sua hora de chegada prevista e o quanto isso vai atrasar os outros. Escolha avidamente o elevador mais rápido.
Existem limitações para isso, como grupos pressionando o botão apenas uma vez e pessoas pressionando o botão várias vezes.
Deixe uma resposta