En general, este problema parece ser NP-completo. Supongamos que solo hay 1 barco (y un puerto) que tiene suficiente capacidad para satisfacer todas las ciudades. Entonces, el problema resultante parece una instancia del Problema del vendedor ambulante. (En el TSP debe volver al origen, pero omitir este requisito no cambia la complejidad computacional).
En el otro extremo, si M = 1 y K = N (exactamente tantos barcos y puertos como ciudades), entonces el problema es encontrar la coincidencia de menor costo en un gráfico bipartito ponderado, que puede resolverse en tiempo polinómico (ya sea [matemática] O (V ^ 2E) [/ matemática] o [matemática] O (V ^ 2 log V + VE) [/ matemática] Consulte Coincidencia (teoría de grafos).
No sé si podrían identificarse otros casos especiales que permitan soluciones de tiempo polinómico, pero la reducción a TSP muestra que el problema es NP completo.
- ¿Cuál es la mejor práctica y estructura de datos para la aplicación de autocompletado multilingüe?
- ¿Es cierto que si entendemos los algoritmos podemos entender todos los programas difíciles de todos los idiomas?
- ¿Por qué el hashing geométrico es más eficiente que usar una matriz indexada de las coordenadas de los puntos característicos?
- ¿Qué consejos y técnicas puedo aprender para retener mi comprensión de algoritmos y estructuras de datos?
- ¿Cómo describirías el algoritmo de Quora usando una ecuación?
