C Desenvolver algoritmo em C

arfneto · 12 de dezembro de 2020

27 minutos atrás, LittleCleiton disse:

O que eu queria dizer é que o problema tem que me dar os melhores pontos que o onibus deve parar, para que haja o mínimo de descontentamento possível...

E?

Mas não isso o que eu expliquei? 3x?

32 minutos atrás, LittleCleiton disse:

a entrada precisa ter :

-onde cada passageiro deseja parar (ex: 2, 10, 12)

-quantas paradas o onibus irá fazer (ex: 2)

Não, não precisa

notou que eu postei um "arquivo" exemplo de entrada, que deveria ser em múltiplos da granularidade ou em número de paradas, estilo Google Maps? o número de linhas do arquivo seria o espaço amostral S, o número de passageiros?

Notou que o número de paradas é a saída e não a entrada?

(Ao ler o que eu expliquei ou ao menos o enunciado)

Em 10/12/2020 às 10:06, brandg disse:

O K será definido após o cálculo do descontentamento de cada passageiro

36 minutos atrás, LittleCleiton disse:

passageiro 1 ---- deseja parar no ponto 2

passageiro 2 ---- deseja parar no ponto 10

passageiro 3 ---- deseja parar no ponto 12

Não necessariamente.

O algoritmo é sintético e não analítico. Não há razão para individualizar os passageiros. E não é necessariamente o ponto: o enunciado fala em distância.

Há um enunciado mais completo que o postado aqui? O que está lendo tem essa passagem?

Em 10/12/2020 às 10:06, brandg disse:

(o ponto seria a quilometragem do local de onde entram no ônibus até onde desejam desembarcar)

LittleCleiton · 12 de dezembro de 2020

@arfneto ah ok, Obrigado!!!

LittleCleiton · 13 de dezembro de 2020

@arfneto O ENUNCIADO COMPLETO SERIA ESSE

Uma empresa resolveu inovar criando um serviço de ônibus compartilhado. O serviço funciona da seguinte maneira: os passageiros embarcam todos juntos em uma certa parada e cada um escolhe o ponto onde pretende desembarcar. O ônibus realiza um determinado trajeto. Cada parada no trajeto é determinada pela sua distância em relação ao ponto inicial (ponto 0). O passageiro i especifica o destino xi para o qual deseja ir. Você pode assumir que as distâncias xi estão em quilômetros e já estão ordenadas em ordem crescente. Porém, o ônibus só irá realizar k paradas, o que faz com que alguns passageiros não desçam exatamente onde gostariam, causando descontentamento.

Se o passageiro i descer do ônibus na posição y, então seu grau de descontentamento é (xi - y)2. Não há paradas de ônibus fixas. As paradas são decididas após a análise de todas as demandas dos passageiros. Como o ônibus só pode fazer k paradas, seu objetivo é criar um algoritmo que minimize a soma do grau de descontentamento de todos os passageiros.

Por exemplo, se há 4 passageiros com x1 = 1, x2 = 18, x3 = 19, x4 = 23 e k = 2, então a solução ótima será fazer duas paradas nos pontos 1 e 20. A primeira parada serve ao primeiro passageiro; a segunda parada serve aos 3 passageiros restantes. Os graus de descontentamento dos passageiros 1, 2, 3 e 4 são 0, 4, 1 e 9, respectivamente, e o total de descontentamento é 14.

Objetivo

Criar um programa em linguagem C que implemente um algoritmo para a determinação dos melhores pontos de parada do ônibus compartilhado em função das demandas dos passageiros e do número máximo de paradas k.

arfneto · 13 de dezembro de 2020

Note que

13 horas atrás, LittleCleiton disse:

(xi - y)2

Sugere o quadrado da distância, mas

Citação

(x-y)*2

Sugere o dobro. Agora que postou um exemplo com o cálculo está claro que é o quadrado.

Vendo seu exemplo com o que eu expliquei acho que você tem uma boa ideia do que fazer

Citação

Por exemplo, se há 4 passageiros com x1 = 1, x2 = 18, x3 = 19, x4 = 23 e k = 2, então a solução ótima será fazer duas paradas nos pontos 1 e 20. A primeira parada serve ao primeiro passageiro; a segunda parada serve aos 3 passageiros restantes. Os graus de descontentamento dos passageiros 1, 2, 3 e 4 são 0, 4, 1 e 9, respectivamente, e o total de descontentamento é 14

Apenas está insistindo em usar k como entrada. E em geral não faz sentido: o que se quer saber é um número ótimo de paradas. Pode ser que mudando uma parada acrescente pouco ou nada ao índice, e então se tabela as possibilidades. Então você varia k e mostra as possibilidades para que alguém usando seu programa defina o melhor valor.

No caso aqui a "granularidade" de que falei é o mais simples: 1km. É muito para um modelo legal, mas tudo bem. É só um modelo afinal. E o melhor caso é com k = 4 onde o índice de descontentamento pode ser zero.

E tem outra simplificação: pode supor as entradas ordenadas.

E tem a maior simplificação de todas: os passageiros embarcam todos juntos. Um único embarque

Notação

É importante ter uma referência. Usando o clássico: Um conjunto S de N passageiros. E para S vai computar um valor ideal de k, usando uma métrica. A métrica é

        ( y[i] - x[i] ) * ( y[i] - x[i] )

onde y[i] é a distância em km de onde o passageiro i de S desceu, em relação ao destino dele, x[i]

E uma entrada possível, usando meu exemplo original, podia ser:

Onde fica claro que são oito passageiros. Não precisa de mais nada

As soluções

Esses problemas são tratados de duas maneiras: na força e no jeito:

Na força se usa o poder absurdo dos computadores e simplesmente se calculam todas as possíveis soluções, quem sabe usando alguma técnica para eliminar alguns casos.
- aqui pode muito bem ser o caso: seriam as permutações de k elementos, para k entre 1 e S, em um conjunto S.
- calculando as possíveis permutações e comparando as somas tem o melhor percurso. Note que podem ter várias soluções
- e se pode ir incrementando k e calculando a queda no índice para cada aumento de k, parando ao atingir algum gatilho
- métodos como o de Monte Carlo podem ser úteis para não gastar muito: se usam valores aleatórios para as paradas e os cálculos seguem até as diferenças encontradas passarem a ser menores que um certo gatilho. Assim não precisa calcular tudo, já muitas possíveis soluções serão equivalentes
No jeito se usa a matemática e tenta calcular o resultado
- nesse caso é preciso analisar a distribuição dos passageiros e marcar as paradas em pontos que agrupem o maior número deles, calculando a distância média dos pontos de parada e destino de cada um para cada caso e classificando. Ou usando outros conceitos.
- a distância média entre os pontos que agrupam o maior número de passageiros, como os POI do GPS, também entram nessa conta, porque podem ajudar a determinar um bom valor de k