Algoritmo a ser usado no layout da loja?

8

Ontem encontrei um problema na sala de aula (aula de negócios, não ciência da computação) e achei interessante do ponto de vista algorítmico.

O problema é mais ou menos assim:
suponha que exista um chão de fábrica com N salas diferentes e você tenha N departamentos diferentes que precisem entrar nessas salas. Os departamentos e as salas são do mesmo tamanho, portanto, qualquer departamento pode entrar em qualquer sala. Há uma distância de viagem conhecida de cada quarto para o outro quarto. Também há uma quantidade conhecida de viagens necessárias de um departamento para outro (as viagens são contadas da mesma forma, independentemente da sala de onde se originam; portanto, uma viagem de A a B é equivalente a uma viagem de B a A). Dadas essas informações, determine um layout dos departamentos nas salas, o que minimiza o tempo de viagem.

Qual é a melhor maneira de abordar esse problema algoritmicamente? Já existe um algoritmo específico ou classe de algoritmos projetados para resolver esse tipo de problema? Esse tipo de problema tem nome na ciência da computação?

Não estou procurando que você crie um algoritmo para resolver isso, embora sinta-se à vontade para fazê-lo, se desejar. Gostaria de saber se este é um espaço problemático que já foi bem definido e estudado algoritmicamente e, em caso afirmativo, obtenha alguns links para pesquisar mais. Eu posso ver muitas estruturas de dados e algoritmos diferentes que podem se aplicar a isso e estou curioso para saber qual abordagem seria "melhor".

E não se preocupe, você não está fazendo minha lição de casa por mim. Este não é um problema de lição de casa em si, pois é um curso de negócios e estávamos simplesmente discutindo os conceitos e não tentando resolver o problema algoritmicamente.

algorithms RationalGeek
fonte
4
Eu acho que seria melhor abordar isso como um problema gráfico, com os departamentos como nós e o número de viagens necessárias entre os departamentos talvez como os pesos das arestas ...
FrustratedWithFormsDesigner
@FrustratedWithFormsDesigner Eu estava pensando exatamente a mesma coisa. Estou curioso para saber se alguém criou outra coisa, mas, se deixado por conta própria, essa seria minha abordagem. Basicamente, gere vários gráficos diferentes com base nos diferentes layouts potenciais e calcule qual gráfico tem o menor peso total. Sinta-se livre para fazer disso uma resposta em vez de um comentário. Eu acho que é legítimo.
RationalGeek
quarto / departamento = nó; número de viagens = peso da borda; A-> B = B-> A - não é um gráfico direcionado;
vartec

Respostas:

-1

Uma solução pragmática:

1) distribua todos os departamentos aleatoriamente (coloque os nomes dos departamentos em uma caixa e retire combinando com o número de salas); 2) calçar sapatos novos para todos os funcionários 3) medir o consumo de sapatos (solados e saltos) após duas semanas 4) colocar os departamentos cujos sapatos dos balconistas mostram grande consumo diretamente nas proximidades 5) repetir esse método n vezes (n = número de departamentos ) 6) após n testes, você medirá a média do consumo de calçados e saberá qual é a melhor distribuição dos departamentos. Mas se eu estivesse no seu lugar, eu faria esse teste como uma experiência mental com a ajuda de algoritmos (você só precisa formalizar esse procedimento, se você é bom em matemática, já sabe como ... se não descobrir)

gianavello
fonte
é difícil ler este post (parede de texto). Você se importaria de editá -lo em uma forma melhor?
amigos estão
-2

A maneira mais simples é: obter o layout civil do edifício, marcar os locais dos departamentos pictoricamente usando uma folha de gráfico (a melhor maneira é usar o Auto CAD ou qualquer outro software 2D / 3D). Você precisa avaliar quanto espaço tem e como deseja colocar os departamentos. Na planilha, você pode obter as distâncias de viagem entre os departamentos.

Bala
fonte