5

El problema se plantea diciendo que tengo una puerta de ancho w y alto h, la cual tiene n cables, los cuales poseen 2 coordenadas (x,y) que corresponden al punto de inicio y termino de cada cable y estos puntos deben estar dentro de las dimensiones de la puerta. Entonces es necesario determinar cuantos cortes debo hacer de forma que pueda cortar todos los cables y cuales serán las coordenadas de este corte. Por ejemplo: Entrada 1

Ejemplo de entrada 1

4 4 6

0 1 4 4

0 5 2 0

0 3 3 6

2 6 4 2

Ejemplo de salida 1

1

0 4 4 3

Entrada 2

Ejemplo de entrada 2

5 4 6

0 2 2 0

0 3 2 6

1 6 3 0

1 0 4 4

3 6 4 2

Ejemplo de salida 2

2

0 4 4 4.5

0 1 4 1

Hasta ahora solo tengo el código para dibujar el plano:

import matplotlib.pyplot as plt
n=int(input("Ingrese numero de sensores "))
w=int(input("Ingrese ancho de la puerta "))
h=int(input("Ingrese alto de la puerta "))
x1=[]
x2=[]
y1=[]
y2=[]
m=[]

for i in range(n):
    print "Sensor %d",(i+1)
    x=int(input("Ingrese cordenada x1 "))
    x1.append(x)
    x=int(input("Ingrese cordenada y1 "))
    y1.append(x)
    x=int(input("Ingrese cordenada x2 "))
    x2.append(x)
    x=int(input("Ingrese cordenada y2 "))
    y2.append(x)
    p=(y1[i]-y2[i])/(x1[i]-x2[i])
    m.append(p)
for i in range (n):
    plt.plot([x1[i],x2[i]],[y1[i],y2[i]])
    plt.axis([0,w,0,h])
plt.show()
1
  • Tal como planteas el problema, el resultado puede tener infinitas soluciones. Si no buscas un punto de optimización claro, es imposible dar una solución única. El problema se reduce a resolver un sistema de ecuaciones. Commented el 23 ene. 2019 a las 20:36

1 respuesta 1

2

Como ya te lo han comentado, puedes tener infinitas soluciones, pero como te interesa tener solo una en particular, entonces podemos elegir una estrategia segura para encontrar las líneas de corte que nos aseguren la intersección con todas las líneas posibles. ¿Y que líneas nos aseguran de forma segura la intersección con cualquier otra recta? Respuesta: las dos diagonales, ambas rectas cortan cualquier línea posible tal como has definido que se construyen. Cualquier línea que "nazca" en alguno de los lados del rectángulo y "muera" en cualquier otro lado del mismo, se intersectará con al menos una de las dos diagonales.

Esto cambia un poco el sentido del problema, podemos decir que al menos con dos rectas (las diagonales) podremos cortar cualquier línea que has trazado, es decir 2 es nuestro número máximo y ya sabemos cuales son las coordenadas de estas rectas, sin embargo, de acuerdo a la configuración de los sensores, puede ocurrir que con una sola de las diagonales cortemos el camino de todos. De forma que ahora el problema se reduce a verificar cuantas lineas corta cada diagonal, si una sola corta el total de sensores, esa será nuestra solución única al problema.

Ésta sería una prueba de concepto:

import matplotlib.pyplot as plt
from random import randint

w,h = (3,9)

# Ejemplo con solución de una sola diagonal
sensores = [
    [[0, w], [2, h]],
    [[0, w], [4, 4]],
    [[0, w], [8, 7]],
]   

# Ejemplo con solución usando las dos diagonales
sensores = [
    [[0, w], [2, h]],
    [[0, w], [4, 4]],
    [[0, w], [8, 7]],
    [[1, w], [h, 3]],
    [[2, w], [0, 2]],
]   

diagonales = [
    [[0, w], [0, h]],
    [[0, w], [h, 0]]
]

cantidad_sensores = len(sensores)

# Dibujamos el camino de los sensores
for x,y in sensores:
    plt.plot(x,y, marker = 'o', color='blue')

# Verificamos cada diagonal, si una sola corta el total de sensores
# esta será nuestra respuesta sino serán las dos diagonales
diag_ok = None
for xd,yd in diagonales:
    corta = 0
    for xs,ys in sensores:
        print("diag: {0}:{1}  sensor {2}:{3}".format(xd, yd, xs, ys))

        if (xs[0] <= xd[0] and ys[1] > yd[1]) or (xs[0] >= xd[0] and ys[1]< yd[1]):
            corta = corta + 1

    if corta == cantidad_sensores:
        diag_ok = [xd,yd]
        break

if diag_ok is not None:
    plt.plot(diag_ok[0], diag_ok[1], marker = 'o', color='red', linestyle = 'dashdot')
else:       
    for x,y in diagonales:
        plt.plot(x,y, marker = 'o', color='red', linestyle = 'dashdot')

plt.axis([0,w,0,h])
plt.show()

Ejemplo con solución de una única diagonal

introducir la descripción de la imagen aquí

Ejemplo con solución con las dos diagonales

introducir la descripción de la imagen aquí

Una aclaración importante

@abulafia, me hizo notar algo importante, está solución resuelve con una mínima cantidad de rectas y con un mínimo de complejidad computacional la solución para cualquier cantidad de líneas de sensores, pero para un conjunto más pequeño de posibles combinaciones, no te garantiza el mínimo posible. Es decir, existe una combinación de sensores en la que este "algoritmo" te dará 2 rectas mínimas, cuando la realidad es que podrías resolverlo con una. Tomo el ejemplo de @abulafia:

introducir la descripción de la imagen aquí

6
  • Bien visto! +1 Pero me queda la duda ¿habrá algún caso en el que una diagonal no intersecte todas las líneas, (y tu solución producirá dos diagonales), pero había otra recta que sí las intersectaba todas? ¿Será posible demostrar que tal caso no existe?
    – abulafia
    Commented el 6 feb. 2019 a las 10:52
  • De hecho, sí hay tal caso: i.sstatic.net/88Uhp.png Pero releyendo la pregunta veo que no pide el número mínimo de cortes, por lo que tu solución con dos diagonales sigue siendo válida.
    – abulafia
    Commented el 6 feb. 2019 a las 11:05
  • @abulafia, lamentablemente no sé, ni pude encontrar un teorema que diga que todas la líneas tal como las define el OP van a ser cortadas por las dos diagonales. Pero si lo piensas gráficamente, una sola diagonal construye dos triángulos, cualquiera de la lineas que nacen de alguno de estos catetos y vayan a cualquiera de los catetos del otro triangulo van a pasar (y cortar) por la hipotenusa (diagonal) .. salvo las que van de un cateto al otro pero del mismo triangulo, en estas es dónde la otra diagonal tiene sentido. Commented el 6 feb. 2019 a las 12:07
  • El otro problema, serían las lineas que pasan justo sobre la diagonal, no podemos decir que la propia diagonal la corta, pero la otra diagonal si. De ahí que afirmo que dos diagonales es el número mínimo seguro para cualquier configuración, eventualmente una sola puede resolverlo Commented el 6 feb. 2019 a las 12:10
  • Sí, lo de que dos diagonales seguro cortarán todas lo veía claro. Lo que muestro esta figura es que tu método de usar una o dos diagonales, no da siempre una solución "optima" en el sentido de generar el mínimo de cortes. En el caso de la figura das como solución dos cortes (las dos diagonales), pero podía resolverse con uno solo (por ejemplo una vertical que pase por x=0.5)
    – abulafia
    Commented el 6 feb. 2019 a las 12:32

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.