Leeův algoritmus - Lee algorithm

The Leeův algoritmus je jedním z možných řešení pro problémy s směrováním bludiště na základě Šířka první vyhledávání Vždy poskytuje optimální řešení, pokud existuje, ale je pomalé a vyžaduje značnou paměť.

Algoritmus

1) Inicializace

 - Vyberte počáteční bod, označte ho 0 - i: = 0

2) Vlnová expanze

 - REPEAT - Označte všechny neoznačené sousedy bodů označených i pomocí i + 1 - i: = i + 1 AŽ DO ((cíl dosažen) nebo (nelze označit žádné body))

Krok rozšíření vlny

3) Backtrace

   - přejít na cílový bod OPAKOVAT - přejít na další uzel, který má nižší značku než aktuální uzel - přidat tento uzel na cestu AŽ (dosažený počáteční bod)

4) Výprodej

 - Blokovat cestu pro budoucí zapojení - Smazat všechny značky

Rozpětí vln samozřejmě označuje pouze body ve směrovatelné oblasti čipu, nikoli v blocích nebo již zapojených částech, a aby se minimalizovala segmentace, měli byste se držet v jednom směru co nejdéle.

externí odkazy

• http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf

Reference

• Vlk, Wayne (2002), Moderní design VLSI, Prentice Hall, str. 518ff, ISBN  0-13-061970-1
• Lee, C. Y. (1961), „Algoritmus pro propojení cest a jejich aplikace“, Transakce IRE na elektronických počítačích, EC-10 (2): 346–365, doi:10.1109 / TEC.1961.5219222

Tento článek týkající se elektroniky je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.