Labyrint springare

Den här artikeln handlar om den elektroniska designroutingmetoden. För romanen av James Dashner, se The Maze Runner . För filmatiseringen av romanen, se The Maze Runner (film) .

Inom elektronisk designautomation är maze runner en anslutningsdirigeringsmetod som representerar hela routingutrymmet som ett rutnät. Delar av detta nät är blockerade av komponenter, specialiserade områden eller redan befintliga ledningar. Nätstorleken motsvarar områdets ledningsdelning. Målet är att hitta en kedja av rutnätsceller som går från punkt A till punkt B.

En labyrintlöpare kan använda Lee-algoritmen . Den använder en vågutbredningsstil (en våg är alla celler som kan nås i n steg) genom hela routingutrymmet. Vågen stannar när målet nås, och vägen bestäms genom att backa genom cellerna.

Se även

• Autorouter

• Lee, CY (1961), "An Algorithm for Path Connections and Its Applications", IRE Transactions on Electronic Computers , EC-10 (2): 346–365, doi : 10.1109/TEC.1961.5219222 . En av de första beskrivningarna av en labyrintrouter.