Duda programación

[Franki]

Buenas.

Estoy realizando un trabajo de prácticas para la universidad, la aplicación en sí es un simulador de una cantera mediante el modelo vista-controlador. Ya tengo implementado el 90% de la aplicación, pero me estoy volviendo loco con un problema en particular. Como el analisis de los requisitos es muy extenso, voy a poner un ejemplo similar a ver como se os ocurriria hacerlo a vosotros, porque me estoy volviendo loco xD.

Imaginaros que teneis una coleccion de datos organizada en cinco filas y cuatro columnas. Hasta ahí bien, ahora teneis que activar una serie de esos datos pero tienen que estar lo mas alejado posible. Y para colmo, no sabes cuantos datos tienes que activar, a lo mejor son dos, que tres, que cuatro.

No se si me he explicado muy bien. Imaginaros este ejemplo:


XXXX
XXXX
XXXX
XXXX

Bien, ahora teneis que activar cuatro X de esas y tienen que estar lo mas alejado posible unas de otras.

0XXX
XXXX
XXXX
XXXX
XXX0

Así sería activando dos. Pero cuando pasa de dos datos, ya me pierdo y mi cabeza entra en un bucle espacio-temporal hasta llegar a la saturación.

Lo estoy implementando en C#, pero lo pongo en esta sección porque no pido una solución en código, con alguna explicacion de que se os ocurriria a vosotros me sirve.

Muchas gracias, y saludos, es la primera vez que posteo y ya llevo un añito leyendo el foro xD.

[biribau]

Bueno, te diré primero un método que nunca me falla: la búsqueda ciega, su ejemplo más conocido es la fuerza bruta. Sólo tienes que calcular todas las combinaciones posibles y luego ordenarlas según tu criterio o puntuarlas con una métrica tuya. Luego yo suelo ir incluyéndole heurísticas, pistas que vas sacando tu y pueden ayudar la búsqueda.
En este caso yo lo he hecho en un papel, creo que no me equivoco aunque tengo las mates algo oxidadas y no sabría demostrártelo, esperemos que la intuición no me falle.
Lo que me ha salido es una especie de algoritmo fractal o recursivo, ahora lo explico:
Dados un cuadrado y una función de distancia.
Para un punto es trivial, vale cualquier punto del cuadrado.
Para 2 puntos es trivial, un punto en una esquina y otro en la contraria. Por ello cambiamos el primer paso, en coger cualquier punto preferimos coger uno esquinado. Con esto ya podemos inventar un algoritmo incremental que vaya añadiendo puntos.
Para añadir un punto a un cuadrado con n puntos colocados de esta manera(recursiva, partiendo de los 2 esquinados), trazamos una cruz formada por 2 lineas diagonales que salen de los puntos más externos, la otra diagonal es la que corta perpendicularmente a estas 2, vamos a mirar los puntos que interseccionan la cruz con el perímetro del cuadrado o el cuadrado vamos, que es lo mismo.
El nuevo punto lo ponemos en la primera de estas intersecciones que no contenga un punto. Si las 4 intersecciones ya estan ocupadas usamos el punto central de la interseccion. Si también está ocupado pasamos a repetir el proceso pero con el cuadrado cogiendo uno de los puntos externos y el punto central. Pero ha de ser hecho como exploracion en anchura, o sea sólo mirar un nivel, luego el siguiente subcuadrado hasta los 4, y si entonces no hay hueco pasamos a explorar el segundo nivel de cada uno de los 4 subcuadrados recursivamente.

Soltado el rollo, si este algoritmo es bueno, creo que se puede hacer con un simple bucle iterativo si disponemos el número de puntos a priori(que ya has dicho que sí), el número de puntos que cubre cada nivel son: (4,4+1), +(4,4+4),  +(12,12+4)
O sea, que primero se cubren las esquinas, 4
Luego los centros, 1
Cuando hay más de un cuadro anidado, las esquinas se comparten muchas,
son ... bueno te dejo calcularlas, habría que tener más muestras. Esto sería para calcular el numero de divisiones partiendo de un numero de puntos a colocar, luego sólo sería llenar los vértices de las divisiones del cuadrado.

Quizá lo esté liando, a ver, simplifico, rellenas las 4 esquinas en ese orden, luego el centro, luego divides el cuadro en 4 y cubres las intersecciones, de cada subcuadro rellenas el centro, luego de cada subcuadro lo divides en 4 y repites el proceso. Sólo ten en cuenta que no puedes hacerlo con recursividad normal pues sería en profundidad, tu necesitas explorar en anchura(en vez de una pila LIFO usa una cola FIFO)

Perdón por el rollo, espero que te sirva, aunque el mío es para espacio continuo, no discreto(dividido en casillas) quizá podría cambiar, jugar con el redondeo, a veces arriba a veces abajo? no sé, si me animo te intento luego hacer un code .

[Franki]

Muchas gracias biribau, he cogido el método que has pensado y lo he adaptado un poquito a mi caso, ya que como tengo 5 filas y cuatro columnas, las lineas que se cruzan no se cortaban en un punto intermedio. Lo que he hecho ha sido seguir lo que me has dicho cogiendo subcuadrados de 3x3. Colocar primero en esquinas y despues en centros.

Luego depuraré un poco, pero creo que en un principio tu idea funciona perfecatmente. Muhas gracias ^^

[Meta]

Buenas:

Suena al juego tres en raya lo que intentas hacer. Algo de eso teníamos en mente. Por si acaso te paso este enlace para que te de ideas.

Ver enlace.

Saludo.

[biribau]

Gracias por revivir el post,
Me di cuenta que lo que te di sólo sirve para cuadrados y que tu lo querías para rectángulos. Además ahora dudo de si eso funciona o no. Yo de tí cogería todas las combinaciones y probaría el seudo"teorema".
No sé que podría servir, lo he intentado demostrar con ayuda del autocad pero es que ya se me olvidó manejarlo:
Dado un rectángulo, los 2 primeros puntos son los de 2 esquinas opuestas.
El tercer punto se calcula fácilmente con la línea que corta las intersecciones de 2 circunferencias de centro un punto de los puestos y que pase por el punto contrario.
El tercer punto es cualquiera de los 2 que corta esa recta al perímetro.
Para añadir más puntos no tengo ni idea, he probado trazando paralelas equidistantes y dividiendo equiproporcionalmente una circunferencia... pero no, sé que no, porque la relación fundamental que ha de cumplir es que todos los puntos estén a la misma distancia, esto se prueba fácil(es trazar circunferencias), pero no sé como hacerlo, salvo del modo que te dije, probando todas las combinaciones.
Yo me guié pensando el rectángulo como un segmento "grueso", un segmento es un rectángulo con base 0, en este es fácil de calcular, pues para n puntos sólo hay que dividir el segmento por n.
Aunque sigo pensando que se puede hacer geométricamente...

[Kase]

no sabes cuantos valores tienes que encender?    pero tienes que pedirlos, no?   por que en su defecto tendria que ser un random...
o incluso peor, seguir ensendiendo valores mientras el usuario diga enciende mas...

y otra duda.. la mayor distancia es en filas y columnas? o como si todo fuera una unica serie?
omitiendo esta duda..


en el primer y segundo caso, no vasta con  tomar el valor dividirlo entre el total del arreglo y ya con eso tienes la distancia mayor?

pedir cantidad a encendir
z=leer()
distanciamax= z/arreglo.lenght  // aki debe redondearse, pero me da flojera pensar como
puntero = 0
contador = 0
while  contador < z{
 arreglo[puntero] = encender  
 contador++
 puntero += distanciamax
 if contador = (z-1)   // exepcion del ultimo por si  la distancia maxima se pasa del total =/
                              // este error no sucede si distanciamax es redondeado al mas chiko
    do {
        if puntero > arreglo.lenght
        puntero--
       }
 }
}


si fuera el caso 2.. es solo de modificar un pokito el algoritmo para  que se reaga la tabla cada que el usuario kiere encender uno nuevo