algorithm - trazar - construccion de un rectangulo dibujo tecnico

Construye el rectángulo más grande posible fuera de los segmentos de línea de longitudes dadas

Question

Recientemente participé en un concurso donde me hicieron esta pregunta. Dada una matriz con longitudes, ¿cuál es el área del rectángulo más grande que se puede hacer usando TODAS las longitudes? Las longitudes se pueden agregar pero no se pueden dividir en el medio.

Ejemplo: [ 4,2,4,4,6,8 ] dado este arreglo lo mejor que podemos hacer es hacer un rectángulo de lados 8 y 6 como este.

dando una superficie de 8 * 6 = 48.

Soy un principiante e incluso después de pensar mucho en cómo hacerlo, no puedo llegar a ningún lado. No estoy buscando una solución, pero se agradecería cualquier pista para empujarme en la dirección correcta.

TIA

Edit: Alguien señaló (comentario eliminado ahora) que es difícil explicar la solución con solo sugerencias y no publicar algún código. Código postal amable si es necesario.

Answer 1

Aquí hay una solución al problema en Python. No está optimizado en absoluto. Incluso verifico 2, 4 después de verificar 4,2, por ejemplo. Pero para mostrar cómo puedes encontrar una solución, creo que es lo suficientemente bueno.

def all_but(lst, pos):
    return lst[0:pos]+lst[pos+1:]

def find_sets_with_len(segs, l):
    for i in range(0, len(segs)):
        val = segs[i]
        if (val == l):
            yield [val], all_but(segs, i)
        if (val < l):
            for soln, rest in find_sets_with_len(all_but(segs, i), l - val):
                yield [val]+soln, rest

def find_rect(segs, l1, l2):
    for side1, rest1 in find_sets_with_len(segs, l1):
        for side2, rest2 in find_sets_with_len(rest1, l1):
            for side3, rest3 in find_sets_with_len(rest2, l2):
                return [side1, side2, side3, rest3]

def make_rect(segs):
    tot_len = sum(segs)
    if (tot_len %2) == 0:
        opt_len=tot_len/4
        for l in range(opt_len, 0, -1):
            sides = find_rect(segs, l, tot_len/2-l)
            if sides is not None:
                print(sides)
                return sides
    print("Can''t find any solution")

make_rect([4,2,4,4,6,8])

La idea es simple: primero, calcule la longitud óptima (es decir, la longitud para hacer un cuadrado), luego busque todo comenzando con la longitud óptima y baje a 1 por un lado. Para cada longitud, enumere todos los conjuntos para un lado de la longitud calculada, luego enumere todos los conjuntos para el lado opuesto (de la misma longitud), entonces si puedo encontrar un conjunto más de la longitud restante (que es total_len/2 menos el longitud del lado que estoy mirando), entonces tengo la mejor solución. Esto sucede en la función find_rect() .

Answer 2

Bueno, me aburro un poco, así que juego con Java para tener algo de experiencia, puede estar mal codificado y sin afinar, ya que estoy tratando de aumentar mi habilidad de codificación, los comentarios son bienvenidos. Mi computadora es capaz de responderme para arreglos pequeños :)

La salida se ve como:

Largest rectangle range is ; 48
-------------------------------------------------
input values; [ 4,2,4,4,6,8,9 ]
-------------------------------------------------
Array details of the rectangle:
A1: [ 6 ]
B1: [ 8 ]
A2: [ 2,4 ]
B2: [ 4,4 ]

combinación.clase utilizando el algoritmo de Kenneth;

importar java.math.BigInteger;

public class Combination {

    /**
     * Burak
     */
      private int[] a;
      private int n;
      private int r;
      private BigInteger numLeft;
      private BigInteger total;

    public Combination (int n, int r) {
        if (r > n) {
          throw new IllegalArgumentException ();
        }
        if (n < 1) {
          throw new IllegalArgumentException ();
        }
        this.n = n;
        this.r = r;
        a = new int[r];
        BigInteger nFact = getFactorial (n);
        BigInteger rFact = getFactorial (r);
        BigInteger nminusrFact = getFactorial (n - r);
        total = nFact.divide (rFact.multiply (nminusrFact));
        reset ();
      }

      //------
      // Reset
      //------

      public void reset () {
        for (int i = 0; i < a.length; i++) {
          a[i] = i;
        }
        numLeft = new BigInteger (total.toString ());
      }

      //------------------------------------------------
      // Return number of combinations not yet generated
      //------------------------------------------------

      public BigInteger getNumLeft () {
        return numLeft;
      }

      //-----------------------------
      // Are there more combinations?
      //-----------------------------

      public boolean hasMore () {
        return numLeft.compareTo (BigInteger.ZERO) == 1;
      }

      //------------------------------------
      // Return total number of combinations
      //------------------------------------

      public BigInteger getTotal () {
        return total;
      }

      //------------------
      // Compute factorial
      //------------------

      private static BigInteger getFactorial (int n) {
        BigInteger fact = BigInteger.ONE;
        for (int i = n; i > 1; i--) {
          fact = fact.multiply (new BigInteger (Integer.toString (i)));
        }
        return fact;
      }

      //--------------------------------------------------------
      // Generate next combination (algorithm from Rosen p. 286)
      //--------------------------------------------------------

      public int[] getNext () {

        if (numLeft.equals (total)) {
          numLeft = numLeft.subtract (BigInteger.ONE);
          return a;
        }

        int i = r - 1;
        while (a[i] == n - r + i) {
          i--;
        }
        a[i] = a[i] + 1;
        for (int j = i + 1; j < r; j++) {
          a[j] = a[i] + j - i;
        }

        numLeft = numLeft.subtract (BigInteger.ONE);
        return a;

      }
}

Y principal Combinator.class;

import java.util. *;

Combinador de clase pública {

/**
 * @param args
 */


private static int[] ad;
private static int[] bd;
private static String a1;
private static String a2;
private static String b1;
private static String b2;
private static int bestTotal =0;


public static void main(String[] args) {
    int[] array={4,2,4,4,6,8,9};
    getBestCombination(array, 1);

    if(bestTotal <= 0){
        System.out.println("System couldnt create any rectangle.");
    }else{
        System.out.println("Largest rectangle range is ; " + bestTotal);
        System.out.println("-------------------------------------------------");
        System.out.println("input values; " + parseArrayToString(array));
        System.out.println("-------------------------------------------------");

        System.out.println("Array details of the rectangle:");
        System.out.println("A1: " + a1);
        System.out.println("B1: " + b1);
        System.out.println("A2: " + a2);
        System.out.println("B2: " + b2);


    }
}



private static void getBestCombination(int[] array, int level){


    int[] a;
    int[] b;

    int bestPerimeter = getTotal(array,true);

    Vector<Vector<Integer>> results = null;

    for(int o=array.length-1;o>=1;o--){
        for(int u=bestPerimeter;u>=1;u--){

            results = Combinator.compute (array, o, u);

            if(results.size() > 0){

                for(int i=0;i<results.size();i++){

                    a = new int[results.elementAt(i).size()];
                    for(int j = 0;j<results.elementAt(i).size();j++){
                        a[j] = results.elementAt(i).elementAt(j);
                    }

                    b = removeItems(array, results.elementAt(i));

                    if(level == 1){
                        getBestCombination(a,2);
                        getBestCombination(b,3);
                    }else if(level == 2){

                        ad = a;
                        bd = b;

                    }else{

                        getBestCombination(a,4);
                        getBestCombination(b,4);

                        if(getTotal(ad, false) == getTotal(a, false) && getTotal(bd, false) == getTotal(b, false)){
                            if(bestTotal<(getTotal(ad, false)*getTotal(bd, false))){
                                bestTotal = getTotal(ad, false)*getTotal(bd, false);
                                a1 = parseArrayToString(ad);
                                a2 = parseArrayToString(a);
                                b1 = parseArrayToString(bd);
                                b2 = parseArrayToString(b);
                            }
                        }else   if(getTotal(ad, false) == getTotal(b, false) && getTotal(bd, false) == getTotal(a, false)){
                            if(bestTotal<(getTotal(ad, false)*getTotal(bd, false))){
                                bestTotal = getTotal(ad, false)*getTotal(bd, false);
                                a1 = parseArrayToString(ad);
                                a2 = parseArrayToString(b);
                                b1 = parseArrayToString(bd);
                                b2 = parseArrayToString(a);
                            }
                        }
                    }
                }
            }
        }
    }
}


private static String parseArrayToString(int[] items){

    String s = "[ ";

    for(int i=0;i<items.length;i++){
        if(i!=items.length-1){

            s = s + items[i] + ",";

        }else{
            s = s + items[i];
        }
    }

    s = s + " ]";

    return s;

}
@SuppressWarnings("rawtypes")
private static int[] removeItems(int[] array, Vector items){


    ArrayList<Integer> res = new ArrayList<Integer>();
    for(int i=0;i<array.length;i++){
        res.add(array[i]);
    }
    for(int u = 0;u<items.size();u++){
        res.remove(items.elementAt(u));
    }
    int[] results = new int[res.size()];
    for(int o=0;o<res.size();o++){
        results[o] = res.get(o);
    }
    return results;
}
private static int getTotal(int[] array,boolean bestPerimeter){
    int sum = 0;

    for (int i = 0; i < array.length; i++) {
      sum += array[i];
    }
   if(bestPerimeter == true){
       if(sum%2!=0){
           sum = sum -1;
       }
       sum = sum/2;
   }
   //System.out.println(sum); 
   return sum;

}

 @SuppressWarnings("rawtypes")
private static int getSum (Vector v) {
        int sum = 0;
        Integer n;
        for (int i = 0; i < v.size (); i++) {
          n = (Integer) v.elementAt(i);
          sum += n.intValue ();
        }
        return sum;
      }



    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static Vector<Vector<Integer>> compute (int[] array, int atATime, int desiredTotal) {
        int[] indices;
        Combination gen = new Combination (array.length, atATime);
        Vector results = new Vector ();
        Vector combination;
        int sum;
        Integer intObj;
        while (gen.hasMore ()) {
          combination = new Vector ();
          indices = gen.getNext ();
          for (int i = 0; i < indices.length; i++) {
            intObj = new Integer (array[indices[i]]);

            combination.addElement (intObj);
          }
          sum = getSum (combination);
          if (sum == desiredTotal) {

            Collections.sort (combination);
            if (!results.contains (combination)) {
              results.addElement (combination);
            }
          }
        }
        return results;
      }

}

Answer 3

El problema es NP-Hard , por lo tanto, la solución de backtracking [u otra solución exponencial sugerida por @vhallac] será su mejor opción, ya que no se conoce [y si P! = NP, no existe] solución polinómica existente para esto. tipo de problema

Prueba de dureza NP:
Primero, sabemos que un rectángulo consiste en 4 bordes, que son iguales en pares [e1 = e2, e3 = e4].
Mostraremos que si hay un algoritmo polinomial A para este problema, también podemos resolver el problema de partición , mediante el siguiente algoritmo:

input: a group of numbers S=a1,a2,...,an
output: true if and only if the numbers can be partitioned
algorithm:
sum <- a1 + a2 + .. + an
lengths <- a1, a2 , ... , an , (sum*5), (sum*5)
activate A with lengths.
if A answered there is any rectangle [solution is not 0], answer True
else answer False

Exactitud:
(1) si hay una partición en S, que sea S1, S2, también hay un rectángulo con bordes: (sum*5),(sum*5),S1,S2 , y el algoritmo arrojará el valor True.

(2) si el algoritmo arroja Verdadero, hay un rectángulo disponible en longitudes, ya que a1 + a2 + ... + una <suma * 5, hay 2 bordes con longitud suma * 5, ya que los otros 2 bordes deben hacerse Al usar todas las longitudes restantes [según la pregunta especificada], cada otro borde es en realidad de longitud (a1 + a2 + ... + an)/2 , y por lo tanto hay una partición legal del problema.

Conclusión: hay una reducción PARTITION<=(p) this problem , y por lo tanto, este problema es NP-Duro

EDITAR:
La solución de retroceso es bastante simple, obtenga todos los rectángulos posibles y compruebe cada uno de ellos para ver cuál es el mejor.
Solución de seguimiento: pseudo-código:

getAllRectangles(S,e1,e2,e3,e4,sol):
  if S == {}:
     if legalRectangle(e1,e2,e3,e4):
          sol.add((e1,e2,e3,e4))
  else: //S is not empty
     elem <- S[0]
      getAllRectangles(S-elem,e1+elem,e2,e3,e4,sol)
      getAllRectangles(S-elem,e1,e2+elem,e3,e4,sol)
      getAllRectangles(S-elem,e1,e2,e3+elem,e4,sol)
      getAllRectangles(S-elem,e1,e2,e3,e4+elem,sol)

getRectangle(S):
  RECS <- new Set
  getAllRectangles(S,{},{},{},{},RECS)
  getBest(RECS)

EDIT2:
Como se comentó en los comentarios, esta respuesta muestra que no solo es difícil encontrar el MEJOR rectángulo, sino que también es difícil encontrar CUALQUIER rectángulo, lo que dificulta este problema para las soluciones heuristic .