Fylla en Serie av Plan

Går det bra att röra sig i alla riktningar, eller är problemet reducerat till att endast gälla 4 eller 8 riktningar?

Hur som helst borde en modifierad version av djikstras (som räknar om kostnaden för varje ruta efter förflyttning) funka. Alltså ta djikstras (funkar typ som det står nedan) och släng på steget att räkna om alla kostnader vid förflyttning.

1. börja på en ruta,
2. Räkna ut kostnaden att gå till alla rutor från denna ruta.
3. Flytta till den med lägst kostnad, vid samma kostnad: välj en deterministiskt (kanske den närmsta av dom?).
4. Räkna ut kostnaden till alla kvarvarande rutor, givet förflyttningen du nyss gjorde d.v.s. sätt kostnaden till 0 på de rutor som ligger i linje.
5. Repetera 3 och 4 tills alla rutor är täckta.
6. Spara kostnaden
7. Back-tracka och gör om men pröva nästa i ordningen vid steg 3 (alltså näst närmaste rutan, sedan 3:e närmaste o.s.v.). Ifall du hittar en som täcker alla med lägre kostnad än tidigare, ersätt kostnaden. Annars avbryt när du kommer över den hittills lägsta kostnaden.
8. Efter alla vägar är prövade är bästa vägen den med lägst kostnad.

För optimala så prövar du att starta på alla olika rutor. Annars kan du antagligen använda domänkunskap för att välja bättre (t.ex. bara pröva rutor som ligger nära rutor på nästa lager). Denna lösning kommer dock gå väldigt segt för stora rutnät då optimala lösningen har hög tidskomplexitet.