Simplex se utiliza para resolver el sistema de desigualdades lineales.
Se basa en la propiedad de convexidad: cualquier mínimo local debe ser un mínimo global. Simplex es un algoritmo no determinista.
Si un problema se puede reducir a ecuaciones de desigualdad lineal, se puede resolver con simplex. Una amplia variedad de problemas, como la ruta más corta de una sola fuente, el flujo máximo, el flujo de costo mínimo, etc. pueden reducirse a desigualdades lineales.
- Dados n puntos en un plano 2D, ¿cómo encontrarías el número máximo de puntos que se encuentran en la misma línea recta? Proporcione un algoritmo para resolver este problema.
- ¿Cuál sería la mejor manera de integrar el algoritmo de aprendizaje para clasificar en Solr?
- ¿Por qué el ensacado funciona tan bien para los árboles de decisión, pero no para los clasificadores lineales?
- ¿Son los problemas NP completos también problemas NP difíciles? ¿Por qué?
- ¿Cuál es el mejor algoritmo de extracción en primer plano de escenas dinámicas, donde el fondo también puede cambiar (debido a las vibraciones de la cámara o los detalles en movimiento)?
Sin embargo, los problemas mencionados anteriormente tienen soluciones más conocidas que simplex. Un problema particular que se me ocurre, que no tiene una solución de tiempo polinomial que no sea reducirse a desigualdades lineales (y aplicar simplex), es el flujo de productos múltiples.
Ejemplo: los generadores de escudo se pueden resolver con simplex (Divulgación: soy el autor de este problema).
