Sac à dos parabolique

Question

Disons que j'ai une parabole. Maintenant j'ai aussi un tas de bâtons, qui sont toutes de la même largeur (oui mes compétences en dessin sont incroyable!). Comment puis-je pile ces bâtons à l'intérieur de la parabole que je suis en minimisant l'espace qu'il utilise autant que possible? Je crois que cela relève de la catégorie des problèmes de sac-à-Dos, mais cette page de Wikipédia n'apparaît pas pour me rapprocher d'un monde réel solution. Est-ce un problème NP-Difficile?

Dans ce problème, nous essayons de minimiser la quantité de la zone occupée (par exemple: Intégrale), qui comprend une surface verticale.

Answer 1

J'ai cuit une solution en JavaScript à l'aide de processing.js et HTML5 canvas.

Ce projet devrait être un bon point de départ si vous souhaitez créer votre propre solution. J'ai ajouté deux algorithmes. Celui qui trie les blocs d'entrées, de la plus grande à la plus petite, et un autre qui mélange la liste de façon aléatoire. Chaque élément est ensuite tenté d'être placé dans le seau en commençant par le bas (le plus petit seau) et en déplaçant jusqu'à ce qu'il dispose de suffisamment d'espace pour s'adapter.

Selon le type d'entrée de l'algorithme de tri peut donner de bons résultats en O(n^2). Voici un exemple de la triés en sortie.

Voici les insérer dans le but de l'algorithme.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

Projet sur github - https://github.com/gradbot/Parabolic-Knapsack

C'est un public de pensions, alors n'hésitez pas à la branche et ajouter d'autres algorithmes. Je vais probablement ajouter plus dans le futur, comme il est un problème intéressant.

Answer 2

La simplification

Je tiens d'abord à simplifier le problème, à le faire:

• J'ai passer les axes et les ajouter les uns aux autres, il en résulte x2 croissance
• Je suppose que c'est une parabole sur un intervalle fermé [a, b], where a = 0 et pour cet exemple, b = 3

Disons que vous êtes donné l' b (deuxième partie de l'intervalle) et w (la largeur d'un segment), alors vous pouvez trouver nombre total de segments en n=Floor[b/w]. Dans ce cas, il existe un cas trivial de maximiser la somme de Riemann et de la fonction pour obtenir i-ième segment hauteur est de: f(b-(b*i)/(n+1))). En fait c'est une hypothèse, et je ne suis pas sûr à 100%.

Max ed exemple pour 17 des segments sur l'intervalle fermé [0, 3] pour la fonction Sqrt[x] vraies valeurs:

Et le segment des hauteurs de la fonction dans ce cas, est - Re[Sqrt[3-3*Range[1,17]/18]], et les valeurs sont:

• Forme exacte:

{Sqrt[17/6], 2 Sqrt[2/3], Sqrt[5/2], Sqrt[7/3], Sqrt[13/6], Sqrt[2], Sqrt[11/6], Sqrt[5/3], Sqrt[3/2], 2/Sqrt[3], Sqrt[7/6], 1, Sqrt[5/6], Sqrt[2/3], 1/Sqrt[2], 1/Sqrt[3], 1/Sqrt[6]}

• Approchée de la forme:

{1.6832508230603465, 1.632993161855452, 1.5811388300841898, 1.5275252316519468, 1.4719601443879744, 1.4142135623730951, 1.35400640077266, 1.2909944487358056, 1.224744871391589, 1.1547005383792517, 1.0801234497346435, 1, 0.9128709291752769, 0.816496580927726, 0.7071067811865475, 0.5773502691896258, 0.4082482904638631}

Ce que vous avez archivé est un Bin-Packing problème, partiellement rempli bin.

Trouver b

Si b est inconnu ou notre tâche est de trouver le plus petit possible b en vertu de ce que tous les bâtons de la forme initiale du tas en forme. Ensuite, nous pouvons limiter au moins b valeurs de:

1. limite inférieure : si la somme des hauteurs de segments = somme des hauteurs de bâton
2. limite supérieure : nombre de segments = nombre de bâtonnets plus long bâton < le plus long segment de hauteur

Un de la façon la plus simple de trouver b est de prendre un pivot à l' (higher limit-lower limit)/2 trouver si une solution existe. Ensuite, elle devient la nouvelle limite supérieure et inférieure, et vous répétez le processus jusqu'à ce que la précision demandée est respectée.

---

Lorsque vous êtes à la recherche pour b vous n'avez pas besoin de résultat exact, mais sous-optimale et il serait beaucoup plus rapide si vous utilisez algorithme efficace pour trouver relativement proches du point de pivot à effectif b.

Par exemple:

• triez les par le bâton longueur: du plus grand au plus petit
• commencer à "mettre de plus grands objets" dans la première bin ton ajustement

Answer 3

Cela équivaut à avoir plusieurs sacs à dos (en supposant que ces blocs ont la même «hauteur», cela signifie qu'il y a un sac à dos pour chaque «ligne») et constitue donc un exemple du problème d'emballage des bacs.

Voir http://en.wikipedia.org/wiki/Bin_packing

Answer 4

Comment puis-je pile ces bâtons à l'intérieur de la parabole que je suis en minimisant l' (vertical) de l'espace qu'il utilise autant que possible?

Juste le traiter comme n'importe quel autre Bin Packing problème. Je jetterais méta-heuristiques (comme la recherche tabou, le recuit simulé, ...), puisque ces algorithmes ne sont pas de problème spécifique.

Par exemple, si j'avais de mon Nuage Équilibre problème (= une forme de Bin Packing) en Bave Planner. Si tous les bâtons ont la même hauteur et il n'y a pas d'espace vertical entre les 2 bâtons sur le dessus les uns des autres, il n'y a pas beaucoup que j'aurais du changement:

• Renommer Computer de ParabolicRow. Supprimer les propriétés (cpu, mémoire, bande passante). Donnez-lui un unique level (où 0 est la ligne la plus basse). Créer un certain nombre d' ParabolicRows.
• Renommer Process de Stick
• Renommer ProcessAssignement de StickAssignment
• Réécrire les dures contraintes de manière à ce qu'il vérifie si il y a assez de place pour la somme de tous les Sticks affecté à un ParabolicRow.
• Réécrire les contraintes souples afin de minimiser le plus haut level de à tous ParabolicRows.

Answer 5

Je suis sûr que c'est l'équivalent de bin-packing:

informel de réduction

Soit x la largeur de la plus grande ligne, faire les poubelles 2x gros et de créer pour chaque ligne un espace réservé à l'élément qui est 2x-rowWidth grand. Ainsi, deux éléments réservés ne peut pas être emballé dans un bac.

Pour réduire bin-packing parabolique sac à dos que vous venez de créer un espace réservé éléments pour toutes les lignes qui sont plus gros que le nécessaire binsize avec la taille de la largeur binsize. En outre, ajouter des espaces réservés pour toutes les lignes qui sont plus petits que binsize qui remplissent l'ensemble de la ligne.

Ce serait évidemment dire que votre problème est NP-dur.

Pour d'autres idées de look ici peut-être: http://en.wikipedia.org/wiki/Cutting_stock_problem