Algoritmo Problema Clasificación

Question

Hay un gran problema en uno de los sitios de concurso de algo. Estoy tratando de resolverlo por 5 días. No le pido que me resuelva esto, ya que soy nuevo en los algoritmos que me gustaría pedirle que me ayude con la clasificación de este tipo de problema, ¿alguien resolvió problemas como este, cuál es el tipo de problema NP o no? Por favor, no crea que le pido que resuelva esto para mí, mi propósito es solo aprender algoritmos y este es el problema que es bastante difícil para mí:

El objetivo de este rompecabezas es determinar dónde colocar un conjunto de estaciones de gas para que estén más cerca de los aeropuertos. Los aeropuertos hacen uso de un lote de gas para alimentar aviones, por lo que ubicar las estaciones de servicio cerca de ellos es de importancia estratégica.

Especificación de entrada Su programa debe tener un solo comando argumento de línea: el archivo de entrada (pasado en argv, args, argumentos según el idioma). El archivo de entrada está formateado como sigue:

La primera línea contiene un número entero: n el número de aeropuertos las siguientes líneas n contienen cada uno 2 valores de punto flotante xi yi que representa las coordenadas del aeropuerto ITH la siguiente línea contiene el número p de los casos para analizar (p es siempre menor que 5) las siguientes líneas p contienen cada uno gi entero que indica el número de estaciones de servicio requeridos

especificaciones de salida: programa que debe ser la salida el resultado a la salida estándar (printf, impresión, eco, escritura): SuLa salidadebe contener p líneas, cada línea proporciona las coordenadas gj xj, yj de las estaciones de servicio. La puntuación de su solución se medirá por la calidad de la solución . La calidad de la solución se mide por la distancia total, la distancia total D es la raíz cuadrada de la suma de las distancias cuadradas desde cada aeropuerto hasta su estación de servicio más cercana. El baja la distancia total D, mayor será tu puntaje.

Answer 1

Para el caso gi = 1. Es fácil: simplemente computarizarías el centro de gravedad/masa (desde todos los aeropuertos, diablos, podrías incluso pesar cada aeropuerto con la cantidad de combustible que consumen, de modo que colocaría la estación de combustible más cerca de los aeropuertos de mucho consumo, pero como esto no es obligatorio, darías todo el mismo peso). Esto arrojaría una solución óptima (este también es un buen ejemplo de que la optimización global no lineal NO implica que NP sea difícil).

Mi idea sería dividir el conjunto de aeropuertos en conjuntos gi, y luego aplicar a cada conjunto el centro de gravedad/masa. Esto se clasificaría como un problema de agrupamiento (o tal vez una partición, depende de cómo lo formule). (Prácticamente, aplicaría un k-means clustering para resolver esto). (Aquí realmente se vuelve NP difícil si desea un resultado perfecto, pero tal vez alguien encuentre otra buena solución)

Answer 2

Este problema es el problema canónico de clasificación k-means no supervisado. Vea aquí para los detalles completos: http://en.wikipedia.org/wiki/K-means_clustering

Para una pista rápida (si quiere evitar los spoilers completos) k-means simplemente comienza escogiendo ubicaciones aleatorias para sus estaciones de servicio. Mejora la solución en cada iteración a partir de entonces reduciendo el costo de cada estación de servicio individual de a una por vez. Lo hace moviendo una estación de servicio con el objetivo de minimizar su costo para el conjunto de aeropuertos que actualmente suministra.

Answer 3

Esto parece ser una variante del Facility location problem. Encontrar las ubicaciones óptimas es NP-hard, pero se pueden aplicar muchos métodos de aproximación para encontrar soluciones dentro de una cierta distancia garantizada del óptimo. Alternativamente, se pueden usar métodos suaves como el agrupamiento, como se propone en otras respuestas.