Análisis y diseño de algoritmos] Problema de mejor orden de servicio_Respuesta del algoritmo al problema de mejor orden de servicio
Hay n clientes esperando el mismo servicio al mismo tiempo. El tiempo de servicio requerido por el cliente i es ti,1
Respuesta de referencia
I. Problema de orden de mejor servicio
Entorno operativo (entorno de software y hardware).
Software en ejecución: Windows7 de 64 bits
Hardware: computadora ASUS
Programación: lenguaje C++
Entorno de compilación: VC++ 6.0
3. Ideas de diseño de algoritmos
Primero, se debe minimizar el tiempo de espera promedio de n clientes, es decir, se debe minimizar la suma de los tiempos de servicio de espera de n clientes. Porque el tiempo promedio de espera = la suma de los tiempos de espera del servicio/n.
En segundo lugar, dado que el tiempo de servicio de cada cliente i es ti, para lograr el tiempo mínimo de espera de servicio, se debe organizar el servicio al cliente con un valor de ti pequeño tanto como sea posible.
Por lo tanto, este problema es un problema de diseño óptimo local, es decir, un algoritmo codicioso.
4. Diagrama de flujo del algoritmo
1
5. Análisis del diseño del algoritmo
Supongamos que el tiempo del problema original es T, y ya conocemos una determinada serie de servicios óptimos, la solución óptima es min = {t(1), t(2), ..., t(n)} (donde t(i) es el servicio requerido por el i-ésimo tiempo del cliente), entonces el tiempo de espera requerido para cada cliente es:
T(1)=t(1);
T(2)=t(1) +t( 2);
......
T(n)=t(1)+t(2)+......+ t( n);
Entonces, el tiempo total de espera es la solución óptima
T min=n*t(1)+(n-1)*t(2)+(n). -2) *t(3)......+(n+1-i)*t(i)+......+2*t(n-1)+1*t(n) ;
Dado que el tiempo de espera promedio es la suma de los tiempos de espera de n clientes divididos por n, el problema se transforma en el problema de encontrar la secuencia de servicios que minimice la suma de los tiempos de espera de los clientes.
VI.código fuente
#include
#include
#include
#include
#include
#include
long n=-1; //cliente n
long *wait //tiempo de espera del cliente wait <; /p>
void inputData ()
{ //datos de entrada n, tiempo de espera esperar
ifstream fin;
fin.open(*input .txt', los::nocreate);
if(!fin ){
cout
return;
}
fin>>n;
esperar==nuevo largo[n];
for(1ong i=0;i
{
fin>>espera[ i];
)
fin.close0;
}
void ShellSort (long *x)
( // Ordenación de shell, ordena los datos de pequeño a grande long i, j, temp.gap=n/2;
while(gap >0 ) {
for(i=espacio; i
j=i-espacio;
while(j>=0){
if(x[j]>x[j+espacio])
{
temp=x[j]=x[j+espacio]; [ j+gap]=temp;//implementar intercambio de tamaño
j=j-gap;
}
else{j=-1;}< / p>
}
}
}
brecha=brecha/2;
}
}
/**
Nombre de la función AveWait0
Descripción: Calcula el tiempo medio de espera
Parámetros: Tiempo de espera para cada cliente
**/
double AveWait(long *x)
{
double ave=0.0 ;
ShellSort(x)
for(long i=0; i
{
ave+=1.0*(n-i) * x[i];
}
ave/=n; //encuentra el tiempo de espera promedio
return ave;
)
void outputData(doble salida)
( //resultado de salida
ofstream fout;
fout.open("output. txt ");
fout
fout.close0;
)
void main0
{ // función de llamada principal
inputData();
if(n!=-1)(
double avewait=AveWait(wait);
<p>outputData(avewait):
}
}
VII. Análisis del resultado de la operación
Resultados de la prueba:
entrada.txt:
12 56 22 l9 90 1002 234 33 45 97 810
salida.txt:
532.00
VIII. Ganancias y Experiencia
Este problema minimiza el tiempo promedio de espera de los clientes, es decir, minimiza la suma de los tiempos de espera del servicio. Este problema se resuelve utilizando el algoritmo codicioso de optimización local.
A través de este problema, también comprendemos mejor la esencia del algoritmo codicioso. En el futuro, otros problemas de optimización local similares y problemas de subestructura óptima se pueden resolver utilizando el algoritmo codicioso.
Esta pregunta también nos da una comprensión más profunda de la naturaleza de los algoritmos codiciosos.