Heuristik

Bakgrund

Heuristik är konsten att hitta en lämplig lösning på ett problem med hjälp av begränsad kunskap och kort tid. Mer formellt sett bygger heuristik på erfarenhet och kan påskynda sökandet efter en lösning med hjälp av enkla regler. En fullständig sökning kan ta för lång tid eller vara för svår att genomföra.

Mer exakt uttryckt är heuristik strategier som använder lättillgänglig, men löst tillämplig information för att kontrollera problemlösning hos människor och maskiner.

Heuristik kan användas inom vissa vetenskapsområden, men inte inom andra: Ett teleskop som har ett fel på en grad är förmodligen oanvändbart om det riktas mot ett långt borta objekt. Samma teleskop som riktas mot fönstret på andra sidan gatan kommer förmodligen att tolerera detta fel; att missa en grad kommer inte att ha någon större inverkan på ett kort avstånd.

Heuristik kan användas för att uppskatta ett svar som sedan blir tydligare genom att utföra en exakt lösning i mycket liten skala, kanske för att spara tid, pengar eller arbetskraft i ett projekt - till exempel kan en heuristisk gissning om hur mycket vikt en bro förväntas bära användas för att avgöra om bron ska vara gjord av trä, sten eller stål, och lämpliga mängder av det nödvändiga materialet kan köpas in medan den exakta utformningen av bron färdigställs.

Användningen av heuristik inom vissa mycket tekniska områden kan dock vara skadlig - datavetenskap är ett exempel på detta. Att programmera en dator så att den utför mer eller mindre de önskade åtgärderna kan leda till allvarliga störningar. Därför måste datoruppgifter i allmänhet vara ganska exakta. Det finns dock vissa områden där datorer kan beräkna heuristiska lösningar på ett säkert sätt - till exempel Googles sökteknik bygger i hög grad på heuristik, som ger "nära-miss"-matchningar på en sökfråga när en exakt matchning inte kan hittas. Detta gör det möjligt för användaren att korrigera eventuella fel som sökningen ger upphov till. Exempel: Om man söker efter namnet "Peter Smith" och inte kan hitta det exakta namnet, matchar sökmotorn heuristiskt "Pete Smith" i stället, och den person som använder sökmotorn måste avgöra om Pete och Peter är samma person.

Exempel

Polya

Här är några andra vanliga heuristiker från Polyas bok How to Solve It från 1945:

• Om du har svårt att förstå ett problem kan du försöka rita en bild.
• Om du inte kan hitta en lösning, försök att anta att du har en lösning och se vad du kan härleda från den ("arbeta bakåt").
• Om problemet är abstrakt kan du försöka undersöka ett konkret exempel.
• Försök först att lösa ett mer allmänt problem: "uppfinnarens paradox": den mer ambitiösa planen kan ha större chans att lyckas.

Förpackningsproblem

Ett exempel där heuristiker är användbara är ett slags packningsproblem. Problemet består i att packa ett antal föremål. Det finns regler som måste respekteras. Till exempel har varje föremål ett värde och en vikt. Problemet är nu att få med sig de mest värdefulla föremålen, med minsta möjliga vikt. Ett annat exempel är att få in ett antal föremål av olika storlek i ett begränsat utrymme, som i en bils bagageutrymme.

För att få den perfekta lösningen på problemet måste alla möjligheter prövas. Detta är ofta inte ett bra alternativ, eftersom det tar lång tid att prova dem och i genomsnitt måste hälften av alla möjligheter prövas tills man hittar en lösning. Så vad de flesta människor gör är att börja med det största föremålet, passa in det och sedan försöka ordna de andra föremålen runt det. Detta ger oftast en bra lösning. Det finns dock fall där en sådan lösning är mycket dålig och en annan teknik måste användas.

Detta är därför en heuristisk lösning.

Exempel på ett packningsproblem. Detta är ett endimensionellt (begränsat) Knapsack-problem: Vilka lådor ska väljas för att maximera summan av pengar och hålla totalvikten under 15 kg? Ett flerdimensionellt problem skulle kunna ta hänsyn till lådornas täthet eller dimensioner, det sistnämnda är ett typiskt packningsproblem. (Lösningen i det här fallet är att välja alla lådor utom den gröna).