Archief - Vraagje of dit mogelijk is

MilM · 17 nov 2010

voltje zei:
Zoals ik al zei, backtracking.

Dat is toch geen backtracking?
Hij 'keert nergens terug' op zijn stappen.

Backtracking zou zijn waarbij je bepaalde dozen toevoegt aan een rek en plots (middenin) tot de conclusie al komt dat dit geen optimale oplossing is.
In plaats van door te doen (zoals brute force die nergens tussenin checkt of dit een optimale oplossing kan, maar gewoon alle oplossing volledig berekent en das pas de vergelijking doet), stop je daar al en keer je terug.

PinkyNTheBrain zei:
En dat algoritme dat jij voorstelt is wel mooi. Maar dat lijkt me moeilijk uit te schrijven
(we moeten eerst een geschreven methode voorleggen en daarna pas programmeren)

Random is net de simpelste oplossing.
Maar ik denk niet dat je dan veel punten moet verwachten ...

En als je optimalisaties doorvoert, dan is het al niet random meer, maar zit je met een boomstructuur opnieuw aan mogelijkheden.

PinkyNTheBrain zei:
Met stap 2 hebben we gewoon gewerkt om het meeste volume voor het laagste gewicht in het rek te krijgen. Aangezien we toch nooit de volle 100 dozen in het rek krijgen, leek ons dat de beste oplossing

Ok, het is dus zo dat je zoveel mogelijk Volume in 1 rek moet krijgen van een teveel aan dozen.
Ik begrijp dat je met de lichtste dozen wil beginnen (verhouding aan volume), maar dit is wel gevaarlijk. Afhankelijk van de input, zal dit verre van een optimaal algoritme zijn.
Dit zal enkel goed werken voor specifieke input.

Jij neemt namelijk eerst een doos van 1kg en 1m³(1*1*1) en pas daarna één van 1100kg en 1000m³ (10*10*10). (om de getallen simpel te houden)
Stel dat je enkel die twee dozen hebt en dat uw schap 10mx10mx10m is en 2000kg kan dragen.

Uw algoritme zal die kleine box daar zetten en stopt daarna al (want de grote doos kan er niet bovenop staan).

-) Dat mag ja, alleen zit je dan met verspilde plaats (en dat lijkt mij altijd wel het geval dat je met enige verspilling zit)

Dat is nog iets te weinig info.
In uw algoritme zet je dozen op elkaar zonder rekening te houden met zwaartekracht ofzo (moet ook niet).
Ik neem dus aan dat je een doos van 100meter breed (en 10 meter hoog) kunt zetten op een doos van 10 meter breed (en 10 meter hoog).

In dat geval is er onder die doos van 100 meter breed nog 90x10 plaats.

Indien je dan een doos hebt van bijvoorbeeld 85x9, kun je deze in de praktijk daar gemakkelijk onderschuiven.

Mag dat? Dat heeft een zeer grote invloed op het algoritme alvast.

Indien dit niet mag, dan worden de afmetingen veel belangrijker dan het gewicht. (grote dozen moeten onderin en mogen niet op kleine dozen gezet worden)
Indien dit wel mag, dan wordt het bijhouden van de dozen in een goeie structuur complexer.

voltje · 17 nov 2010

MilM zei:
Dat is toch geen backtracking?
Hij 'keert nergens terug' op zijn stappen.

En hoe denkte gij da dan te doen wa hij zegt?
Alle mogelijke combinaties afgaan en de beste kieze?

Als jij van 10000 dozen ze allemaal gaat coderen, succes.
Das perfect maakbaar met backtracking zoals hij het zegt he...
Ik zeg niet of dat backtracking het probleem op lost... (het kan, maar ik reageer gwn op zijn antwoord)

Maar als je, zoals die persoon die ik citeerde zei, gaat alle combinaties afgaan kan je beter gewoon alle combinaties afgaan...

En dan beste combi = combi1...

if combi2 is beter dan beste combi, beste combi = combi 2

if combi3 is beter dan beste combi, beste combi = combi 3...

En dat is toch wel backtracking...

Backtracking is niet altijd zo duidelijk "terug gaan" he...

Maar hier ga je terug he...
Je zet alle dozen zoals je wil = combi 1.
Je veranderd bvb de laatste 2 dozen = combi 2 (terug gegaan).

backtracking bestaat er uit op een bepaald punt een bepaalde keuze te maken en daar mee verder te werken en nadien terug te komen tot het punt van die keuze en dan een andere keuze te maken.

Hier maak je continue keuzes, hoe zet je de dozen en waar?
Dus kan je steeds terug komen naar het betreffende keuze punt he ..

MilM · 17 nov 2010

voltje zei:
En hoe denkte gij da dan te doen wa hij zegt?
Alle mogelijke combinaties afgaan en de beste kieze?

Door gewoon x keer een oplossing te generen door telkens een random doos te nemen en die in een schap te zetten tot er geen mogelijke dozen meer zijn.

Daarna kies je de oplossing met het meeste volume.

X is hier dan niet alle oplossingen é, maar een beperkt aantal random.
Dit is totaal geen backtracking. Backtracking is net veel complexer.

De reden waarom je die random oplossingen zou implementeren is net omdat het veel simpeler is en 1 oplossing ook sneller berekend zal worden. Maw, het is mogelijk dat x random oplossingen even snel berekend worden als 1 oplossing met een zwaarder specifiek algoritme. En die specifieke algoritmes zullen maar goed werken op specifieke input sets.

Gurdt · 17 nov 2010

Ik zie daar toch ook geen backtracking in eigenlijk

En ja, het is inderdaad geen "mooie" oplossing maar het wordt in de praktijk wel heel vaak gebruikt

voltje · 17 nov 2010

MilM zei:
Door gewoon x keer een oplossing te generen door telkens een random doos te nemen en die in een schap te zetten tot er geen mogelijke dozen meer zijn.

Daarna kies je de oplossing met het meeste volume.

X is hier dan niet alle oplossingen é, maar een beperkt aantal random.
Dit is totaal geen backtracking. Backtracking is net veel complexer.

Ehm...
Waarom zou je x aantal oplossingen doorlopen? wie zegt er dat je de beste oplossing hebt?

Al overloop je 100 oplossingen van de 101 kan de 101e nog de beste zijn.
Uw programma is alles behalve goed dan he.
Ooit al eens backtracking gebruikt eigenlijk?

Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. Backtracking is handiger dan de brute kracht methode, omdat niet alle oplossingen bekeken hoeven te worden. De term werd rond 1950 voor het eerst gebruikt door de wiskundige Derrick Henry Lehmer.
Bij zoekproblemen moet er een oplossing geselecteerd worden uit een heel aantal plausibele mogelijkheden. Tijdens de oplossing van het probleem moet men keuzes maken. Als achteraf blijkt dat een genomen keuze niet leidt tot een oplossing, of niet tot een optimale oplossing, dan moet men terugkeren naar het keuzemoment. Dit terugkeren noemt men backtracking. Ook de oplossingsmethode als geheel (het algoritme) wordt backtracking genoemd. Na het maken van een nieuwe keuze gaat het algoritme verder tot opnieuw moet terugkeren, of een goede oplossing vindt.

MilM zei:
(zoals brute force die nergens tussenin checkt of dit een optimale oplossing kan, maar gewoon alle oplossing volledig berekent en das pas de vergelijking doet

Ge gaat gewoon alle oplossingen berekenen en dan vergelijken? Das een beetje zwaar niet?
Enig idee hoelang da da gaat duren diene bruteforce?

EDIT: Indien de bedoeling is van gewoon te zorgen dat je alle dozen kan plaatsen. Dan trek ik mijn woorden terug. Als het is van: "Als alle doze op de schappen staan is het goed" dan zou ik het idd niet met backtracking doen.

Maar als gewoon plaatsen niet goed is, maar je de ideale oplossing wenst, dan zou ik toch opteren voor backtracking

DarkBee · 17 nov 2010

Hoe zou je dat immers doen? Je kan het niet gewoon uitvoeren, want dan weet je niet of je oneindig aan het loopen bent, of gewoon nog niet de eindconditie bereikt hebt.
En voor sommige condities/situaties is helemaal niet uit te maken of de stopconditie ooit bereikt wordt, terwijl die op het eerste zicht heel eenvoudig lijkt.

Je hebt meerdere stopcondities :

1) Er is maar een beperkt aantal dozen
2) Er is maar een beperkt aantal volume in het rek

Meer in detail staat ook in de opgave :

Stap 2: Neem de volgende doos in rij met de laagste density (Gewicht/Volume)
Stap 3: Plaats de doos bovenop eerder geplaatste dozen, zodanig dat de waste in de hoogte minimaal is.
Stap 4: Indien men de doos nergens bovenop kan plaatsen vanwege de afmetingenrestrictie, doorloop dan dezelfde methode voor de breedte. I.e. plaats de doos naast eerder geplaatste dozen zodat de waste geminimaliseerd wordt.
Stap 5: Indien de breedterestrictie ook wordt overschreden, doorloop dan dezelfde methode voor de diepte. I.e. plaats de doos achter eerder geplaatste dozen zodat de waste geminimaliseerd wordt.

Dat is toch geen backtracking?
Hij 'keert nergens terug' op zijn stappen.

Stap 1 : Ik 'plaats' doos X
Stap 2 : Ik 'plaats' doos Y en kijk of doos Y naast doos X past.
-> Ja : Neem een andere random doos (die met het daarna minste gewicht)
-> Stop doos 2 terug in de massa, neem een andere doos

== Backtracking !

De reden waarom je die random oplossingen zou implementeren is net omdat het veel simpeler is en 1 oplossing ook sneller berekend zal worden

... Helaas was de opdracht dit :

De prof had ons ook gezegd dat we de optimale oplossing toch niet zouden vinden. We moesten gewoon een zo goed mogelijke oplossing vinden.

MilM · 18 nov 2010

voltje zei:
Ehm...
Waarom zou je x aantal oplossingen doorlopen? wie zegt er dat je de beste oplossing hebt?

Omdat er niet op zoek gegaan wordt naar de beste oplossing, maar naar een goeie oplossing binnen beperkte tijd.

Heb je de topic wel gelezen?

Ge gaat gewoon alle oplossingen berekenen en dan vergelijken? Das een beetje zwaar niet?
Enig idee hoelang da da gaat duren diene bruteforce?

Zucht.
Waar heb ik ergens bruteforce aangehaald als oplossing?

Ik vergeleek het berekenen van x random oplossingen met brute force.
Ik zeg nergens om brute force te gebruiken.

EDIT: Indien de bedoeling is van gewoon te zorgen dat je alle dozen kan plaatsen. Dan trek ik mijn woorden terug. Als het is van: "Als alle doze op de schappen staan is het goed" dan zou ik het idd niet met backtracking doen.

Maar als gewoon plaatsen niet goed is, maar je de ideale oplossing wenst, dan zou ik toch opteren voor backtracking

Opnieuw *zucht*

Ik zeg nergens dat je geen backtracking kan gebruiken.
Waar heb ik dat gezegd?

Ik bedoel gewoon dat uw reactie "zoals ik al zei, backtracking" op niets slaat bij het gedeelte dat jij quote.

Albireo · 18 nov 2010

voltje zei:
Ehm...
Waarom zou je x aantal oplossingen doorlopen? wie zegt er dat je de beste oplossing hebt?

Al overloop je 100 oplossingen van de 101 kan de 101e nog de beste zijn.
Uw programma is alles behalve goed dan he.

De bedoeling is om een zo goed mogelijke oplossing te vinden. Bestaat er eigenlijk wel een algoritme dat de ideale oplossing kan vinden?

Als je een aantal willekeurige oplossingen berekent zullen daar heel slechte tussen zitten maar, hopelijk, ook heel goede. En ik denk niet dat een hedendaagse computer veel tijd nodig heeft om een paar honderdduizend oplossingen te berekenen.
Heeft er iemand een idee over welke orde van grootte we spreken als het gaat om het totale aantal mogelijke oplossingen?

MilM · 18 nov 2010

DarkBee zei:
Stap 1 : Ik 'plaats' doos X
Stap 2 : Ik 'plaats' doos Y en kijk of doos Y naast doos X past.
-> Ja : Neem een andere random doos (die met het daarna minste gewicht)
-> Stop doos 2 terug in de massa, neem een andere doos

== Backtracking !

Nog iemand die mij volledig uit context trekt.

Ten eerste, zoek je gewoon in de overgebleven dozen een doos die nog in het rek past. Indien dat niet werkt, ga je nergens een niveau terug.
(Wel goed gevonden van u dat je dit verwoordt als "stop doos 2 in de massa".)

Dit hoeft ook niet, aangezien je niet moet kijken of het mogelijk is of alle dozen in het rek past, maar gewoon op zoek gaat om zoveel mogelijk dozen in het rek te krijgen.

Ten tweede:

Zelfs al zou het vraagstuk anders zijn, waarbij je backtracking kunt gebruiken om een random werkende oplossing te bekomen, dan nog is dat mijn punt niet.

De discussie is begonnen met volgende quote:

voltje zei:
Albireo zei:

Hoedanook, ik zou i.p.v. een algoritme proberen te schrijven dat een zo goed mogelijke oplossing geeft een algoritme maken dat gedurende een beperkte tijd willekeurige oplossingen berekent en daaruit de beste kiest.

Klik om te vergroten...

Zoals ik al zei, backtracking.

Je kan backtracking gebruiken in een algoritme voor optimale oplossing, in een random oplossing, in een tussenoplossing ... (soms zoekt men namelijk gewoon 'of het mogelijk is')

De link tussen zijn post en die van Albireo is mij dan ook vreemd.

... Helaas was de opdracht dit :

Hier trek je mijn zin ook wel weer uit de context.

Ik haalde dat aan, dat aangezien een random oplossing sneller is (je moet nergens teruggaan en nergens iets controleren), het mogelijk is dat meerdere random oplossingen berekend kunnen worden binnen dezelfde tijd als een meer geavanceerde zoekmethode.

En aangezien een "goed mogelijke oplossing" normaal gezien niet werkt op alle inputs, kan het best zijn dat de beste van x random oplossingen beter is dan de oplossing van de zo "goed mogelijke oplossing"

Dat dit de opdracht niet is, is mij wel duidelijk.
Ik heb namelijk zelf het volgende gezegd daarop:

Maar ik denk niet dat je dan veel punten moet verwachten ...

voltje · 18 nov 2010

Al vanaf het begin dat ik zei dat je dit probleem kan oplossen met backtracking werd er "afgegeven" op mij.
Zitten we daarom op dit forum? Iedereen heeft zijn mening? Ik heb nog nooit "gezucht" bij uw mening, niet waar?
Ik respecteer uw mening maar verdedig de mijn.
Een beetje maturiteit is niet slecht he.

Verder ging ik er van uit, en dat laat je echt wel blijken, dat je gewoon mijn backtracking aan de kant schoof. Sorry indien je het had op die quote.

Mijn quote heeft inderdaad niets te maken met zijn post. Wat hij post is idd geen backtracking.

Heb er waarschijnlijk te snel overgelezen.

Maar mijn punt blijft. Waarom zou je een goede oplossing zoeken als je de "beste" oplossing kan bekomen?

In vele gevallen is het niet belangrijk dat het programma iets langer moet draaien maar is de uitkomst belangrijker.

Als hier de bedoeling is om een programma dat zo snel mogelijk EEN oplossing berekent, ok dan ga je geen backtracking gebruiken.

Maar voor zo ver ik de opdracht versta is het de bedoeling om de beste oplossing te zoeken om de dozen te plaatsen.

En de beste oplossing zou ik (ik zeg dus hoe ik het zou doen, en ben er zeker van dat het zal lukken) doen adhv backtracking.

laten we gerust verder gaan over dit, maar laten we dit vriendelijk houden allright?

Ieder heeft zijn mening en indien die niet klopt mag je me daar gerust op wijzen. Maar op een fatsoenlijke manier

MilM · 18 nov 2010

Als je al vindt dat ik aanvallend ben omdat ik *zucht* zeg, dan zou je best niet teveel posten in andere secties

(waar de toon veel aanvallender kan zijn). Als er al een persoonlijke aanval zou zijn, dan is het wel die opmerking over maturiteit zijn komende van u

Je discussieerde naast de kwestie en deed continu alsof ik een debiel ben die brute force voorstelt als oplossing. Nochtans haalde ik gewoon aan dat dit geen backtracking was op een vriendelijke manier. Ik zucht inderdaad eens wanneer jij dan het tegendeel probeert te bewijzen door de discussie volledig om te vormen al zou ik beweren dat brute force beter is dan backtracking (of dat backtracking een slechte methode is).

Je moet echt zo snel niet op uw tenen getorten zijn. Het is niet alsof ik tijdens deze discussie een slechte mening gevormd heb over u of enige problemen heb met u. Ik begrijp niet echt waarom je u aangevallen voelt.

laten we gerust verder gaan over dit

Voor mij is het afgerond. Je geeft toe dat er een misverstand was over de quote en je er te snel overgelezen hebt (wat ook niet ongewoon is op een forum)

Maar goed, ik wil gerust verder gaan op de probleemstelling:

Indien de topicstarter op zoek gaat naar een simpel, snel algoritme, is het volgens mij (afhankelijk van de antwoorden op de openstaande vragen) beter om gewoon te sorteren op volume en dan telkens proberen of de grootste doos ergens past. Ik zou vermoeden dat volume een grotere restrictie zal hebben dan het gewicht of dan de density en dus beter is om op te sorteren (maar daarvoor is er te weinig informatie momenteel)

Je zou eventueel ook meerdere van die simpele/snelle algoritmes kunnen schrijven (op iets anders sorteren bijvoorbeeld) en dan zoals Albireo aanhaalde de beste eruit kiezen. Volgens mij moet dat best nog meevallen qua snelheid.

Indien je gaat voor een trager algoritme, dan kun je ook het volgende doen (om u tevreden te stellen

):

In bovenstaande methode sorteer je bijvoorbeeld op volume
Laten we zeggen dat na de sortering je 20 dozen hebt gesorteerd van 1 (grootste) tot 20 (kleinste)
Je voegt 1 toe, daarna 2 etc tot je een doos tegenkomt die er niet inpast (bijvoorbeeld doos 8)
Op dat moment hou je de referentie bij (8) en ga je verder met doos 9
Op het einde, wanneer je tot een oplossing gekomen bent (de oplossing van de eerste methode die ik aanhaal), kun je terugkeren tot de eerste doos die er niet inpast (bijvoorbeeld die doos 8)
Het is duidelijk, dat wanneer je doos 1 tot 6 in het schap wilt hebben, het onmogelijk is om daar zowel nog doos 7 als 8 bij te hebben.
We gaan nu dus doos 7 verwijderen (alhoewel deze toegevoegd kan worden) en nu opnieuw van daaruit starten met te controleren of doos 8 toegevoegd kan worden etc
Zo kom je tot een oplossing die beter of slechter is dan de tot nu toe beste oplossing die je gevonden had (indien beter, hou je de stappen bij)

En dan zo verder doen.
Dit zal natuurlijk een pak langer duren. (geen zin om tijdscomplexiteit te bekijken

)

Het zijn allemaal maar voorbeelden hé.
Je kan echt ver gaan in optimalisaties, maar dan moet je het ook grondig bestuderen en er veel tijd insteken. (op internet zal je ook wel betere info vinden van mensen die zich erop toegelegd hebben, maar het zal u ook tijd kosten om die oplossingen te analyseren/begrijpen)

voltje · 18 nov 2010

De manier dat je het zei kwam alleszinds niet "gewoon"over.
Maarja, case closed ;-)

Kan je dan trouwens enigszinds staven waarom backtracking best niet gebruikt wordt? Aangezien ge steeds een andere manier aanhaalt ga ik er van uit dat ge backtracking niet als goede oplossing bekijkt

Want uw 8 stappen vind ik verdacht hard op backtracking lijken...

Ik heb btw geen enkele moment een debiel genoemd of willen laten voelen. Anders zou ik u die pm niet sturen.

Ik ben er gewoon steenvast van overtuigd dat backtracking een van de beste oplossingen is hier. Indien jij er steenvast bent van overtuigd dat dit niet zo is zou ik gewoon graag weten waarom?

Ik programmeer nu al wel enige tijd en sinds ik werk als programmeur heb ik wel de kracht gaan inzien van zaken als backtracking / reflection / ...

Maar ik sta gerust open voor een uitleg wrm backtracking niet beter is dan uw voorstel. Indien uw mening grondig gestaafd is en correct is wil ik dit gerust accepteren. maar tot nu toe ben ik niet overtuigd.

Ik snap gewoonweg niet waarom jullie naar de oplossing random/snel willen gaan?
Zoals ge zelf zei ga je daar mee niet veel punten hebben...

Met backtracking gade meer bekomen dan random he...

Gurdt · 18 nov 2010

Zeg voltje, dat is wel een vorm van backtracking die hij gebruikt, ma backtracking is maar een techniek. Zijn oplossing doet heel wat meer dan gewoonweg backtracken

Dat is zoals zeggen, de faculteit van een getal berekenen, dat is recursief! En ja, dat kan je inderdaad recursief doen, maar daarmee is het algoritme nog niet beschreven

Ik snap gewoonweg niet waarom jullie naar de oplossing random/snel willen gaan?
Zoals ge zelf zei ga je daar mee niet veel punten hebben...

Voor een mooie oplossing ga je dat inderdaad niet doen.
Maar in de praktijk is niet altijd de meest optimale oplossing noodzakelijk. Er zijn heel veel problemen die wij met de algoritmes die we vandaag kennen, niet efficiënt kunnen oplossen. Voor die problemen worden er vaak zogenaamde heuristieken gebruikt, die benaderen de beste oplossing, maar garanderen ze niet. Waarom wil men die heuristieken nu gebruiken? Omdat die vaak efficienter zijn, meer niet.

Random genereren en dan de oplossing checken is sneller uitgevoerd dan het algoritme voor de meest optimale oplossing. Als de "foutmarge" niet heel groot is, kan dat dus perfect nuttig zijn. Hier ga je de foutmarge verkleinen door dat random-algoritme over een bepaalde tijd te simuleren.

voltje · 18 nov 2010

Mja als er een foutmarge kan zijn ja...

Btw, aan de hand van Backtracking wordt een sudoku PERFECT opgelost in een drietal seconden.
Ik zie hier het probleem niet van in aangezien hier ook wel enorm wat combinaties zijn af te gaan.

Gurdt · 18 nov 2010

Complexiteit

3 seconden voor een sudoku, ja wa is da, laat eens een sudoku oplossen van 100 op 100? Dat is exponentieel he da algoritme, met grotere input gaat ge heel scheve dingen krijgen. Maar dat is het domein "complexiteit", moet je je eens in verdiepen!

Een foutmarge kan in de praktijk bijna altijd wel aanvaard worden. Als dat niet zo is, moet ge natuurlijk wel een correct algoritme uitvoeren. Daarom dat er ook pas een heuristiek toegelaten wordt, als het ook echt mag.

djbramz · 18 nov 2010

Het is een NP-compleet probleem, dus ik denk aan oa. Branch-and-Bound.

Cycloon · 18 nov 2010

Backtracking (zonder optimalisaties) is in dit geval gewoon een gestructureerde vorm van bruteforcing, dat lijkt me toch duidelijk? Je kan backtracking pas laten stoppen als je de meest optimale oplossing hebt. De meest optimale oplossing ken je in dit geval pas als je alle mogelijke oplossingen hebt geprobeerd. Backtracking is zelden de beste methode om de oplossing te vinden van een optimalisatieprobleem. Heel veel ruimte voor discussie is hier echt niet.

voltje · 18 nov 2010

wat is er mis met alle oplossingen proberen? Via brute force is dit niet echt goed. Maar via backtracking ga je niet effectief ALLE COMBINATIES overlopen he.

Cycloon · 18 nov 2010

voltje zei:
wat is er mis met alle oplossingen proberen? Via brute force is dit niet echt goed. Maar via backtracking ga je niet effectief ALLE COMBINATIES overlopen he.

Er is niks mis met alle oplossingen te proberen, maar dat gaat enkel als de set van mogelijke oplossingen zeer beperkt is. Vanaf je hier met wat verschillende soorten dozen zit kan je al snel met duizenden combinaties zitten. Zoals ik al zei is backtracking hetzelfde als bruteforcen in deze situatie, alleen is backtracking iets meer gestructureerd en kan je makkelijker deelverzamelingen uitschakelen die onmogelijk de beste kunnen zijn.

MilM · 18 nov 2010

voltje zei:
Want uw 8 stappen vind ik verdacht hard op backtracking lijken...

Inderdaad, daarom ook dat ik erbij had gezegd -> "(om u tevreden te stellen

)"

Kan je dan trouwens enigszinds staven waarom backtracking best niet gebruikt wordt? Aangezien ge steeds een andere manier aanhaalt ga ik er van uit dat ge backtracking niet als goede oplossing bekijkt

Het hangt af van de grootte van de input sets.
Die tweede methode die ik gepost heb zal echt veel meer tijd in beslag nemen bij grote inputs.

Het verschil kan zelfs zwaar oplopen.
Ik ga dus niet zeggen dat hij dat niet moet proberen, veel hangt af van de oefening en manier van verbeteren van de prof.

Kan best zijn dat de prof veel punten geeft omdat de beste oplossing gevonden is, kan best zijn dat de prof van mening is dat dit geen realistisch algoritme is. (het is daarom zelfs goed dat backtracking hier aangehaald wordt. Topicstarter kan dan de verschillende manieren eens bekijken)

In de echte wereld moet je het als volgt bekijken. Stel dat de input te groot is om DE optimale oplossing te vinden binnen een realistische tijd.
Wat is dan goedkoper? Iets meer magazijnruimte kopen en een programma dat snel werkt en toch een goeie oplossing berekent of gaan voor iets minder magazijnruimte en dat er gewacht moet worden met de dozen in te laden op het programma?

Wederom, dit hangt af van verschillende factoren, maar in vele gevallen zullen ze tevreden zijn met een sneller programma dat in de meeste gevallen een zeer goeie uitkomst berekent.

Volgende beschrijft het in feite zeer goed:

Cycloon zei:
Backtracking (zonder optimalisaties) is in dit geval gewoon een gestructureerde vorm van bruteforcing, dat lijkt me toch duidelijk? Je kan backtracking pas laten stoppen als je de meest optimale oplossing hebt. De meest optimale oplossing ken je in dit geval pas als je alle mogelijke oplossingen hebt geprobeerd. Backtracking is zelden de beste methode om de oplossing te vinden van een optimalisatieprobleem.

Op een normale 'brute force manier' zou je inderdaad bijvoorbeeld alle mogelijke combinaties eerst kunnen genereren (waarbij de volgorde in de lijst belangrijk is) en dan elke lijst gaan uittesten en dat zal nog een pak langer duren.

Voor dat te optimaliseren, moet je bijvoorbeeld met een boomstructuur gaan werken en dan krijg je zo een backtracking manier dat zoals Cycloon hier aanhaalt eigenlijk een gestructureerde vorm van bruteforcing is.

Gurdt zei:
Maar in de praktijk is niet altijd de meest optimale oplossing noodzakelijk. Er zijn heel veel problemen die wij met de algoritmes die we vandaag kennen, niet efficiënt kunnen oplossen.

Gurdt zei:
Complexiteit 3 seconden voor een sudoku, ja wa is da, laat eens een sudoku oplossen van 100 op 100? Dat is exponentieel he da algoritme, met grotere input gaat ge heel scheve dingen krijgen. Maar dat is het domein "complexiteit", moet je je eens in verdiepen!

Dit is ook belangrijk.
Want hier zal dat ook zo zijn.
Het verschil tussen een snel en zwaar algoritme zal zeer klein zijn voor kleine input en zeer hoog oplopen voor grote input.

Als de grootte van de input dus ongeveer geweten is, kan je ook gaan bekijken wat realistisch is en wat niet.

Nogmaals, ik heb nergens gezegd dat backtracking geen goeie manier is hé

(hangt namelijk volledig af van hoe je 'goed' definieert hier)
Ik gaf voornamelijk een gewoon algoritme omdat het in de lijn lag van wat de topicstarter nu heeft.

Ik wil mij hierover niet uitspreken, aangezien dit over een oefening voor school haalt en ik niet weet waar de prof die prioriteit zal leggen. (en er bestaan zoveel meer mogelijkheden om een oplossing te vinden)

Archief - Vraagje of dit mogelijk is

MilM

Legacy Member

voltje

Legacy Member

MilM

Legacy Member

Gurdt

Legacy Member

voltje

Legacy Member

DarkBee

Legacy Member

MilM

Legacy Member

Albireo

Legacy Member

MilM

Legacy Member

voltje

Legacy Member

MilM

Legacy Member

voltje

Legacy Member

Gurdt

Legacy Member

voltje

Legacy Member

Gurdt

Legacy Member

djbramz

Legacy Member

Cycloon

Legacy Member

voltje

Legacy Member

Cycloon

Legacy Member

MilM

Legacy Member