Esta pregunta se publicó anteriormente en Computer Science Stack Exchange aquí . Imagine que es un vendedor ambulante muy exitoso con clientes en todo el país. Para acelerar el envío, ha desarrollado una flota de drones de entrega desechables, cada uno con un alcance efectivo de 50 kilómetros....
Considere el siguiente problema: dado un gráfico de consulta y un gráfico de referencia , queremos encontrar el mapeo inyectivo que minimiza el número de bordes tal que . Esta es una generalización del problema del isomorfismo del subgrafo en el que permitimos que los subgrafos sean isomorfos hasta...
Los solucionadores SAT ofrecen una forma poderosa de verificar la validez de una fórmula booleana con un cuantificador. Por ejemplo, para verificar la validez de , podemos usar un solucionador SAT para determinar si φ ( x ) es satisfactoria. Para verificar la validez de ∀ x . φ ( x ) , podemos...
Coloquialmente, la definición del exponente de multiplicación de matrices es el valor más pequeño para el cual existe un algoritmo de multiplicación de matrices conocido . Esto no es aceptable como una definición matemática formal, por lo que supongo que la definición técnica es algo así como el...
En forma simple: ¿Puede un autómata finito bidireccional reconocer gráficos vértice que contienen un triángulo con estados ?vvvo(v3)o(v3)o(v^3) Detalles Aquí son de interés los gráficos vértice codificados usando una secuencia de aristas, cada arista es un par de vértices distintos de...
En su trabajo , Oráculos de distancia aproximada , Thorup y Zwick demostraron que para cualquier gráfico ponderado no dirigido, es posible construir una estructura de datos de tamaño que pueda devolver una distancia aproximada entre cualquier par de vértices en el gráfico.O ( k n1 + 1 /...
Dada como entrada un número entero nnn y un conjunto SSS de conjuntos de elementos de {1,...,n}{1,...,n}\{1, ..., n\} , ¿cuál es la complejidad de encontrar un conjunto TTT de elementos de {1,...,n}{1,...,n}\{1, ..., n\} tal que TTT tiene una cardinalidad mínima y TTT se incluye en ninguno de los...
Estoy interesado en gráficos en nnn vértices que se pueden producir a través del siguiente proceso. Comience con un gráfico arbitrario GGG en k≤nk≤nk\le n vértices. Etiquete todos los vértices en como no utilizados .GGG Producir un nuevo gráfico mediante la adición de un nuevo vértice , que está...
Escribí una implementación del algoritmo Kuhn-Munkres para el problema de coincidencia perfecta bipartita de peso mínimo basado en las notas de clase que encontré aquí y allá en la web. Funciona muy bien, incluso en miles de vértices. Y estoy de acuerdo en que la teoría detrás de esto es realmente...
Sabemos que el algoritmo de mincut de Karger se puede usar para demostrar (de manera no constructiva) que el número máximo de mincuts posibles que puede tener un gráfico es .(n2)(n2)n \choose 2 Me preguntaba si podríamos de alguna manera probar esta identidad al dar una prueba biyectiva (más bien...
¿Cuál es la clase de complejidad asociada con los algoritmos de búsqueda exhaustiva? (si hay uno) ¿Es NP o PSPACE? ¿Existen modelos restringidos de cómputo que capturen la clase de algoritmos de búsqueda exhaustiva similares a los modelos para programación codiciosa y
Ya hice esta pregunta en stackoverflow , pero tal vez sea más adecuada para este sitio. El problema es: Tengo N pares de enteros sin signo. Necesito ordenarlos. El vector final de los pares debe clasificarse de manera no decreciente por el primer número de cada par y no cada vez más por el...
Sea G un gráfico no dirigido de n-nodos, y sea T un subconjunto de nodos de V (G) llamados terminales . Un preservador de distancia de (G, T) es un gráfico H que satisface la propiedad reH( u , v ) = dsol( u , v )reH(tu,v)=resol(tu,v)d_H(u,v) = d_G(u,v) para todos los nodos u, v en T. (Tenga en...
Estoy interesado en implementar SM para la tarea LP, sin embargo, he oído hablar de posibles dificultades: el libro de Cormen dice que es posible tener datos de entrada que harán que la implementación ingenua se comporte en un tiempo exponencial. También he oído que la implementación ingenua puede...
Me pregunto cómo encontrar la circunferencia de un gráfico escaso no dirigido. Por escaso quiero decir . Por óptimo me refiero a la menor complejidad de tiempo.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Pensé en alguna modificación en el algoritmo de Tarjan para gráficos no dirigidos, pero no encontré buenos...
Estoy implementando alguna parte del sistema que requiere ayuda. Por lo tanto, lo estoy enmarcando como un problema gráfico para que sea independiente del dominio. Problema: se nos da un gráfico acíclico dirigido . Sin pérdida de generalidad, suponga que G tiene exactamente un vértice fuente s y...
¿Se sabe algo sobre el siguiente problema? ¿Tiene sentido? Como se llama ¿Es trivialmente equivalente a algún otro problema? ¿Cuál es la complejidad del tiempo? Dado un gráfico G = (V, E) no dirigido (general / planar / acotado / etc.), Encuentre un subconjunto máximo de aristas E ', de modo que...
El tiempo constante es la complejidad absoluta al final del tiempo. Uno puede preguntarse: ¿hay algo no trivial que se pueda calcular en tiempo constante? Si nos atenemos al modelo de máquina de Turing, entonces no se puede hacer mucho, ya que la respuesta solo puede depender de un segmento inicial...
Recuerdo haber visto un estudio o artículo hace un tiempo afirmando que la mayor parte de la aceleración vista en los programas de computadora en las últimas décadas proviene de mejores algoritmos en lugar de hardware más rápido. ¿Alguien sabe el estudio o
Estoy preparando material del curso sobre heurística para la optimización, y he estado buscando métodos de descenso coordinado. La configuración es aquí una función multivariada fff que desea optimizar. fff tiene la propiedad que se restringe a cualquier variable individual, es fácil de optimizar....