 |
Een kortste circuit algoritme |  |
 |
download program
download Delphi projectIntroductie
Dit Delphi project spoort de kortste circuits op in een netwerk.In het netwerk hieronder zijn de elementen ervan aangegeven als cirkels met daarbinnen hun naam (A, B, C).
De elementen zijn verboden via contacten. Die zijn getekend als stippen met daarnaast hun contact nummer (1,2,3).
Dit algoritme zal worden toegepast in een AC netwerk calculator.
De elementen zijn dan weerstanden, condensatoren, spoelen en spanningsbronnen.
De cicuits zijn nodig om de wettten van Kirchhoff te kunnen toepassen
waarmee dan stromen en spanningen zijn te berekenen.
Maar er zijn nog veel meer toepassingen.
Het algoritme
Vanaf een bepaald element wordt het kortste circuit (of rondwandeling) gezocht.Dit gebeurt door aan elk contact een level (1,2,3 ) toe te kennen.
Voor het zoeken begint krijgt elk contacht het level 99, dat te beschouwen is als oneindig.
Dan wordt het eerste element gekozen, laat dat A zijn.
Het output contact (2) van A krijgt level 1 (het laagste).
Dan wordt elk ander element getest op een verbinding met een contact met een lager level dan 99.
K is zo'n element omdat contact 2 level 1 heeft.
Het output contact (3) van K krijgt nu een level dat 1 hoger is dan het input contact, dus level 2.
Etcetera.
Zolang er contacten een nieuw level ontvagen worden alle elementen getest voor een level dat kleiner is dan 99.
Stel dat een element verboden is met een level 6 contact.
Het andere contact van dat element krijgt dan level 7, maar alleen als het level van dat contact groter is dan 7.
Bij element A zien we contacten met level 1 en 5.
Dat duidt op een circuit van 5 elementen: A en vier andere.
Hier staat het resultaat nadat alle elementen zijn bekeken: (levels in rood aangegeven).
Element C heeft input level 2, het output level is dus 3 wat toegekend wordt aan 5.
Element D heeft input level 3 dus output level 4.
Maar contact 5 heeft al level 3 door element C en het level van contact 5 verandert niet.
Bij toekenning van een level wordt het element dat dit level veroorzaakte ook geregistreerd.
Terugwerkend van het begin element (A) is zo het circuit vast te stellen (AKCGH),
dat zijn de elementen die de laagste levels gaven aan een contact.
Nu er een circuit is gevonden schrappen we het begin element (A)
zodat dit geen deel kan uitmaken van nieuwe circuits.
Opmerking: niet elk start element kan een circuit opleveren.
Met element A verwijderd is geen circuit mogelijk met element K.
De hele zoektocht eindigt nadat alle elementen als start element zijn geselecteerd en vervolgens verwijderd.
Het volgende plaatje toont de gevonden circuits:
Het programma
Het rode contact is het startpunt.
Dit contact krijgt level 1.Verwijderde (disabled) elementen zijn als grijze horizontale strepen getekend.
Vertikale strepen zijn de contacten.
Na A wordt element B het begin van een nieuw circuit.
Element D zet contact 5 op level 2.
Element C zet contact 3 op level 3.
Contact 7 (element E) start met level 1.
F zet contact 6 op level 2.
H zet contact 1 op level 3.
Het netwerk is nu opgesplitst in circuits AKGCH, BCD en EFH.
He project
De namen van de elementen (maximaal 15) staan al in een Tstringgrid component.Daarin moeten alleen de contacten nog worden ingevuld.
Elementen die correct zijn verbonden krijgen de status "valid".
Druk op restart als de contacten zijn ingevuld om het netwerk te tekenen in een rooster op Paintbox1.
Druk op go om het eerste circuit te vinden.
Is er geen circuit, druk dan opnieuw op go tot de mededeling verschijnt: "no more elements" .
Onder het rooster staat per contact het level afgebeeld met het element dat dit level veroorzaakte.
type TElement = record
valid : boolean;
enabled : boolean;//part of search
active : boolean; //not blocked
ctIn,ctOut : byte;//contact in, out
end;
Tcontact = record
level : byte;
source : byte; //element nr
end;
Tcircuit = record
elmt : byte;
sign : shortInt;//1:in>out;-1:out>in
end;
var element : array[1..15] of Telement;
contact : array[1..15] of Tcontact;
circuit : array[1..15] of Tcircuit;
circL : byte; //circuit length
elmntsOK : boolean; //elements OK flag
valid betekent dat het element bestaat en correct is verbonden.Enabled betekent dat het element deel kan uitmaken van het circuit.
De "enabled" status uitschakelen houdt in dat het element geen deel meer kan uitmaken van nieuwe circuits.
Active betekent dat het element nog geen nieuw level aan een contact heeft toegekend.
Want als dit het geval is dan wordt de status inactive.
Met een druk op knop restart, krijgen alle elementen met de status "valid" de status "enabled".
Door een druk op knop go krijgen alle elementen met status "enabled" de status "active".
Voor details verwijs ik naar de source code.
Tenslotte vermeld ik enkele specifieke procedures:
procedure TForm1.okBtnClick(Sender: TObject);
Dit is de restart knop.
Deze procedure test de contacten (niet dezelfde nummers, niet hoger dan 15).
function procGo : byte;
Aangeroepen door een click event op de go knop worden circuits gezocht door elementen en contacten te bekijken.
Het resultaat (0,1,2) duidt aan: "new circuit", "no circuit" of "out of elements".
ProcGo roept aan procedure InitSearch(var n : byte);
n is het eerste "enabled" element vanwaar het zoeken naar een circuit begint.
function extractCircuit(ct : byte) : byte;
ct is het start contact.
In omgekeerde volgorde staat in array contact het nieuwe circuit.
procedure Hline(var x1,x2,y: word; el : byte);
procedure Vline(var x,y1,y2 : word; n1,n2 : byte);
Verschaft de coordinaten (x,y) om horizontaal elementen en vertikaal contacten te tekenen.
Vier demo netwerken zijn ingebouwd.
Type TDemo = record
ch : char;//A,B,C
c1 : byte;//input contact
c2 : byte;//output contact
end;
const demo1 : array[1..4] of Tdemo =
((ch:'A'; c1: 1; c2: 2),
(ch:'B'; c1: 2; c2: 3),
(ch:'C'; c1: 3; c2: 4),
(ch:'D'; c1: 4; c2: 1));
demo2........
procedure TForm1.demoBtn1Click(Sender: TObject);//common for demo's 1..4
var p : PAdemo; //pointer to array[1..15] of TElement;
elcount,n,nr,tg : byte;
begin
p := nil;
elcount := 0;
tg := Tspeedbutton(sender).tag;
case tg of
1 : begin
p := @demo1;
elcount := high(demo1);
end;
2 : begin
p := @demo2;
elcount := high(demo2);
end;
3 : begin
p := @demo3;
elcount := high(demo3);
end;
4 : begin
p := @demo4;
elcount := high(demo4);
end;
end;
clearElements;
clearcontacts;
clearcircuit;
paintgrid;
msgtext.caption := 'loaded demo '+inttostr(tg);
for n := 1 to elcount do
with p^[n] do
begin
nr := pos(ch,elmntnames)-1;
stringgrid1.cells[1,nr] := inttostr(c1);
stringgrid1.cells[2,nr] := inttostr(c2);
end;
end;
Hiermee beëindig ik de beschrijving van dit kortste circuit algoritme.Voor details verwijs ik naar de source code.
