1. Dom
  2. Pytanie i odpowiedź
  3. Algorytm pakowania 3d bin

Algorytm pakowania 3d bin

2009-10-13 15 views
9

Szukam deterministycznego wdrożenia dowolnego algorytmu pakowania 3d bin, tj. Do pakowania wielu małych i różnych prostopadłościanów wewnątrz jednego lub wielu większych. Rozwiązanie może różnić się od optymalnego.Algorytm pakowania 3d bin

Powinien być napisany w języku C, C++, Java, C#, IronPython, IronRuby lub w dowolnym innym języku i może być bin z kodu .Net.

Znalazłem tego algorytmu C http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c, ale nie obraca się prostopadłościany, aby znaleźć najlepsze dopasowanie. Nie mam nic przeciwko obracaniu ich do góry nogami, ale rotacja pozioma powinna być możliwa.

Źródło

2009-10-13 Mouk

+0

@Mouk: Czy to zadanie domowe? – Asaph

+4

Twierdzisz, że szukasz algorytmu, ale potem podajesz języki programowania. Szukasz ogólnego algorytmu lub implementacji? –

+0

Czy potrzebujesz optymalnego rozwiązania, czy takiego, które jest całkiem dobre? Czy prostopadłościany są takie same? Kiedy mówisz o rotacji, masz na myśli 90 stopni, czy jakikolwiek kąt? – Beta

Odpowiedz

8

Napisałem przybliżony algorytm dla opisywanego przypadku, tj. Prostokątne pudełka 3D z rotacją prostopadłą, w C++. można znaleźć wyniki i algorytmu w opublikowanym artykule: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

Źródło

2010-04-19 14:55:29 user320450

+3

Czy aplikacja źródłowa lub C++ jest dostępna w Internecie w dowolnym miejscu? –

+0

Jest to dobre rozwiązanie, ale naprawdę nie działa tak dobrze. Dla każdego, kto chce wyjaśnienia i pomocy w napisaniu tej książki, proponuję tę książkę: Problemy z plecakami, autor: Martello and Toth, ISBN: 0471924202 – ars265

1

Ten problem jest NP-trudny. Najlepszym rozwiązaniem jest algorytm aproksymacji (dopóki genialna osoba nie rozwiąże jakiegoś problemu NP lub bardzo szczęśliwy człowiek natknie się na rozwiązanie). Niestety nie znam dobrze znanych algorytmów aproksymacji tego problemu.

Źródło

2009-10-16 22:51:16 ldog

+3

Rozwiązanie problemu NP-zupełnego w czasie wielomianowym nadal nie zapewni wielomianowego rozwiązania problemów NP-trudnych :) –

1

konwertowane wknechtel/3d-bin-pack kod C do JavaScript. Może być łatwo przeniesiony do C#.

https://github.com/keremdemirer/3dbinpackingjs

można uruchamiać przykładowe kalkulacje z index.html pliku i przejrzeć wygenerowany raport. pack1.js plik zawiera aplikację i algorytm. Nie jestem pewien, jak działa algorytm, ale wyniki są zadowalające dla obliczeń opakowań.

Źródło

2016-02-27 23:10:46

Powiązane problemy

 Powiązane problemy