Recientemente tuve este problema en una prueba: dado un conjunto de puntos m (todo en el eje x) y un conjunto n de líneas con puntos finales [l, r] (de nuevo en el eje x), busque el subconjunto mínimo de n de manera que todos los puntos estén cubiertos por una línea. Demuestre que su solución siempre encuentra el subconjunto mínimo.Point cubriendo problema
El algoritmo que escribí para ella era algo en el sentido de: (por ejemplo líneas se almacenan como matrices con el extremo izquierdo en la posición 0 y la derecha en la posición 1)
algorithm coverPoints(set[] m, set[][] n):
chosenLines = []
while m is not empty:
minX = min(m)
bestLine = n[0]
for i=1 to length of n:
if n[i][0] <= minX and n[i][1] > bestLine[1] then
bestLine = n[i]
add bestLine to chosenLines
for i=0 to length of m:
if m[i] <= bestLine[1] then delete m[i] from m
return chosenLines
Estoy no estoy seguro si esto siempre encuentra la solución mínima. Es un algoritmo codicioso simple, así que mi instinto me dice que no, pero uno de mis amigos que es mucho mejor que yo en esto dice que para este problema un algoritmo codicioso como este siempre encuentra la solución mínima. Para probar que el mío siempre encuentra la solución mínima, hice una prueba ondulada a mano por contradicción, donde asumí que probablemente no sea cierta. Olvidé exactamente lo que hice.
Si esta no es una solución mínima, ¿hay alguna forma de hacerlo en menos de algo como O (n!) Time?
Gracias
Tengo problemas para seguir su pseudocódigo. ¿Qué se supone que significa 'n [i] [0] <= m' si' n [i] [0] 'es un punto en el eje xy' m' es un conjunto? ¿Puedes aclarar un poco y quizás explicar naturalmente cuál es tu idea? ¿Por conjunto te refieres a una colección ordenada o cualquier colección? ¿En qué criterios pides 'n'? – IVlad
Lo siento, me refería a <= minX. Editado Probablemente debería haber usado la palabra matriz en lugar de establecer también para las entradas. Está ordenado porque se puede acceder a los elementos secuencialmente, pero no en el sentido de que los puntos estén en orden ascendente o descendente. Todas las entradas se ordenan al azar, supuse. La esencia de mi algoritmo fue: trabajando desde la izquierda, encuentre la línea de longitud más larga que cubre el primer punto descubierto y agréguela a la colección. Repita hasta que cada punto esté cubierto. – Sean
Considere los puntos '1, 100, 101, 102, 103, 104' y las líneas' [1, 100] [10, 101] [20, 102] [30, 103] [40, 104] [101, 104 ] '. Si entiendo tu algoritmo correctamente, elegirá '[1, 100]' para cubrir los dos primeros puntos, '[10, 101]' para cubrir el tercero, hasta '[40, 104]' para cubrir el último . Podemos hacer mucho mejor eligiendo '[1, 100]' y '[101, 104]' o '[1, 100]' y '[40, 104]'. Si entendí tu algoritmo correctamente, entonces no funcionará en todos los casos. – IVlad