Archief - Vraagje of dit mogelijk is

Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
M

Moto

Legacy Member
Artikel over een ander packing problem

Record-breaking algorithm really packs them in - tech - 06 March 2009 - New Scientist

New direction

Their new algorithm matched all the records for packing up to 23 different sized discs in the smallest possible circle and broke all those for packing between 26 and 50 discs - challenges set in a previous competition contested by 155 groups from 32 countries.

The secret to the team's success is their algorithm's ability to take backward, as well as forward steps. Packing algorithms usually shuffle the discs again and again, aiming to reduce the space they occupy each time.

....

"Making the use of backtracking moves more explicit is certainly a merit, and one of the main reasons for the successful approach
Klik om te vergroten...

backtracking pwnz dus ;)
M

MilM

Legacy Member
Zoals al aangehaald, veel hangt af van de gekende informatie, de grootte van de input en wat een realistische wachttijd is. Backtracking is een enorm handige techniek die in elke oplossing kan gebruikt worden voor een bepaalde oplossing te bekomen. Je kan het zelfs gebruiken in een beperkte vorm in een snel algoritme door bijvoorbeeld maar toe te laten om maximum X niveaus terug te keren.

In het artikel staat ook duidelijk volgende informatie:
packs collections of differently sized 2D shapes
Klik om te vergroten...
packing up to 23 different sized discs in the smallest possible circle and broke all those for packing between 26 and 50 discs
Klik om te vergroten...
The secret to the team's success is their algorithm's ability to take backward, as well as forward steps.
Klik om te vergroten...
Locatelli would like to see how the new algorithm performs in other packing problem scenarios, including in three dimensions, something that Schneider's team plans to explore.
Klik om te vergroten...

Er bestaat niet zoiets als "this qwzn!!!!!"
Het is een trade off tussen verschillende zaken.

Een oplossing die zeer goed werkt voor 23 2D objecten, is daarom niet per definitie een goeie oplossing voor 500 3D objecten. ;)

Niemand hier heeft trouwens aangehaald dat backtracking niet goed is (ik toch alvast niet).
v

voltje

Legacy Member
Ik snap wat je bedoeld MilM, en nu volg ik je :-)
Wat je zegt over de grootte van de input enzo dat er gaat voor zorgen of je al dan niet de beste oplossing wil.

Maar ik ga er gewoon al heel de tijd van uit dat de persoon DE BESTE oplossing wil.

Maar ja, als je een magazijn hebt en je wil dozen stapelen maakt het je idd niet uit hoe ze staan, zolang ze er maar staan...

En ja sorry... maar het komt gwn over (niet alleen van u) dat backtracking hier serieus wordt afgewezen.
M

Moto

Legacy Member
Er bestaat niet zoiets als "this qwzn!!!!!"
Het is een trade off tussen verschillende zaken.
Klik om te vergroten...
it pwnzzzzzz :p
backtracking = 1337 °\o/°

Een oplossing die zeer goed werkt voor 23 2D objecten, is daarom niet per definitie een goeie oplossing voor 500 3D objecten.
Klik om te vergroten...
Wow, captain obvious to teh rescue !!! :p

Nee serieus ah mannen, doe eens niet zo serieus

Ik post een artikel over een packing probleem waar er serieus vooruitgang is geboekt door het gebruik van backtracking, dat is alles, geen reden om direkt op uw paard te kruipen
d

djbramz

Legacy Member
voltje zei:
Maar ik ga er gewoon al heel de tijd van uit dat de persoon DE BESTE oplossing wil.
Klik om te vergroten...

Het is een NP-compleet probleem, dus voor de optimale oplossing gaan betekent zowieso lang wachten. Ik zou voor een zo optimaal mogelijke oplossing gaan.
v

voltje

Legacy Member
Hoe dan ook hangt die van de vraag af... Wil de "klant" betalen voor de beste oplossing... (zoals reeds aangehaald denk ik)

Maar hoe dan ook is dit probleem wel oplosbaar...
n

nguaroth

Legacy Member
Cycloon zei:
Als je de oplossing van een realistisch probleem kan definiëren dan kan je altijd wel een programma schrijven die alle mogelijke oplossingen gaat aftoetsen. Vermits er zich in onze wereld nog steeds geen problemen hebben voorgedaan waarbij je de oplossing niet éénduidig kan beschrijven besluit ik dus dat er voor elk realistisch probleem een oplossing te programmeren valt.

Dat je nu over theoretische problemen gaat beginnen zie ik al van mijlenver aankomen, maar wees gerust, ik heb ook een academische opleiding gehad.
Klik om te vergroten...
Om hier nog eens over terug te komen:
Een leuk onbeslisbaar en nuttig probleem dat niet theoretisch is.
Gegeven een willekeurige set van assertions over een relationele databank, spreken deze elkaar tegen?
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
Terug
Bovenaan