---

Hej

Jeg ved ikke rigtigt hvordan jeg skal beskrive mit problem.
Det handler vist nok om at finde den korteste sti gennem et antal
tilstande....

Jeg har en tilstandsmaskine som kan være i X forskellige tilstande.
Den skal være i stand til at gå fra en vilkårlig tilstand til en vilkårlig
anden tilstand.
Det kan den kun hvis tilstandene er "ved siden af hinanden"
Jeg kan bevæge mig både frem og tilbage.

Mit problem er:
Hvordan organiserer jeg, mest effektivt, tilstandene i en rækkefølge, som
muliggør alle tilstands-ændringer ?

Exempel:
Der eksisterer 3 forskellige tilstande 0,1 og 2
den korteste beskrivelse af tilstands skift mellem dem må være
0-1-2-0
Det kræver altså en sti med 4 punkter, for at jeg kan bevæge mig mellem 0 og
1, mellem 1 og 2 og mellem 0 og 2

Hvis der eksisterer 4 tilstande (0,1,2,3) kan man organisere stien:
0-1-2-3-2-0-3-1
Men er det den kortest mulige organisation ?? Her har jeg jo to steder hvor
2 og 3 er forbundne.

Hvad med 10 tilstande eller 50 ??

På forhånd tak for hjælpen
Morten

---

rudolpho wrote:
> Hej
>
> Jeg ved ikke rigtigt hvordan jeg skal beskrive mit problem.
> Det handler vist nok om at finde den korteste sti gennem et antal
> tilstande....
>
> Jeg har en tilstandsmaskine som kan være i X forskellige tilstande.
> Den skal være i stand til at gå fra en vilkårlig tilstand til en
> vilkårlig anden tilstand.
> Det kan den kun hvis tilstandene er "ved siden af hinanden"
> Jeg kan bevæge mig både frem og tilbage.
>
> Mit problem er:
> Hvordan organiserer jeg, mest effektivt, tilstandene i en rækkefølge,
> som muliggør alle tilstands-ændringer ?
>
> Exempel:
> Der eksisterer 3 forskellige tilstande 0,1 og 2
> den korteste beskrivelse af tilstands skift mellem dem må være
> 0-1-2-0
> Det kræver altså en sti med 4 punkter, for at jeg kan bevæge mig
> mellem 0 og 1, mellem 1 og 2 og mellem 0 og 2
>
> Hvis der eksisterer 4 tilstande (0,1,2,3) kan man organisere stien:
> 0-1-2-3-2-0-3-1
> Men er det den kortest mulige organisation ?? Her har jeg jo to
> steder hvor 2 og 3 er forbundne.
>
> Hvad med 10 tilstande eller 50 ??
>
> På forhånd tak for hjælpen
> Morten

Lad mig forsøge at omformulere dit problem:

Du har en graf (muligvis en orienteret graf, men det er forså vidt ikke
vigtigt). Tilstandene er knuder, tilstandovergangene er kanter.

Du ønsker at finde den kortest mulige sti gennem grafen, der besøger alle
punkter. (Færrest muligt antal tilstandsovergange, der sikrer at du har
været i alle tilstande.) Tilsyneladende ønsker du desuden at vende tilbage
til udgangspunktet.

Dette er ækvivalent til Travelling Salesman problemet, som du kan finde
oceaner af sider om på nettet. Problemet er et af de mest kendte
NP-komplette problemer, hvilket indebærer at der ikke kendes en algoritme,
der kører i logaritmisk tid, men at det på den anden side ikke er bevist, at
der ikke findes en sådan algoritme.

--
Regards,
Kristian Damm Jensen

---

"rudolpho" <anon@anon.dk> writes:

> Hej
>
> Jeg ved ikke rigtigt hvordan jeg skal beskrive mit problem.
> Det handler vist nok om at finde den korteste sti gennem et antal
> tilstande....
>
> Jeg har en tilstandsmaskine som kan være i X forskellige tilstande.
> Den skal være i stand til at gå fra en vilkårlig tilstand til en vilkårlig
> anden tilstand.
> Det kan den kun hvis tilstandene er "ved siden af hinanden"
> Jeg kan bevæge mig både frem og tilbage.
>
> Mit problem er:
> Hvordan organiserer jeg, mest effektivt, tilstandene i en rækkefølge, som
> muliggør alle tilstands-ændringer ?
>
> Exempel:
> Der eksisterer 3 forskellige tilstande 0,1 og 2
> den korteste beskrivelse af tilstands skift mellem dem må være
> 0-1-2-0
> Det kræver altså en sti med 4 punkter, for at jeg kan bevæge mig mellem 0 og
> 1, mellem 1 og 2 og mellem 0 og 2
>
> Hvis der eksisterer 4 tilstande (0,1,2,3) kan man organisere stien:
> 0-1-2-3-2-0-3-1
> Men er det den kortest mulige organisation ?? Her har jeg jo to steder hvor
> 2 og 3 er forbundne.
>
> Hvad med 10 tilstande eller 50 ??

Hvis du har N tilstande, skal du have (N*(N-1))/2 forbindelser, hvis alle skal
være direkte forbundet med alle andre.

Dvs (tilstande, forbindelser) bliver:
(1,0)
(2,1)
(3,3)
(4,6)
(5,10)
(6,15)
....
etc.
Skal disse skrives på en linie, som du har vist (på formen A-B-C-A) , gælder
at hver "instans" af en tilstand kun kan have 2 forbindelser, endvidere kan
endepunkterne, som der kun er 2 af, kun have 1 forbindelse.

2 punkter A-B : 1 forbindelse
3 punkter A-B-C-A : 3 forbindelser
4 punkter A-B-C-D-A-C-D-B : 7 fobindelser, altså ikke de 6 som vi har beregnet.

med 4 punkter skal hvert punkt have 3 forbindelser.
Men da instanser altid får 2 forbindelse pånær endepunkter, har vi altså
som i ovenstående at A og B (de er endepunkter) får deres 3 fobindelser,
medens C og D er nødt til at instantieres 2 gange for at opnå deres 3
forbindelser. De får nu fire (da de ikke er endepunkter) og dermed har
vi en "spildforbindelse".


5 punkter A-B-C-D-E-C-A-D-B-E-A : 10 forbindelser.
Altså ingen "spild".
6 punkter.

Her skal hvert punkt have 5 forbindelser. Da kun 2 kan være endepunkter
vil altså fire punkter skulle instantieres 2 gange, dvs 2 "spildforbindelser".

dvs man skulle få 17 forbindelser som "minimum".

efter den device skulle man altså få:
hvis N er lige fås (N-2)/2 spildforbindelser.
hvis N er ulige fås 0 spildforbindelser.

mvh

--
Søren Dideriksen

---

Hej Søren

Imponerende forståelses evne du der demonstrerer.
Det er præcist min problemstilling

Det næste naturlige spørgsmål er selvfølgelig:
med N tilstande, hvordan strukturerer jeg jeg så rækkefølgen ?
Du har vist at der et minimalt antal forbindelser men er der også en entydig
sortering ?

mvh
Morten


""Søren Diderikse" "n"" <sdide@ag.aaa.dk> wrote in message
news:87r6yoc9mf.fsf@localhost.localdomain...
> "rudolpho" <anon@anon.dk> writes:
>
>> Hej
>>
>> Jeg ved ikke rigtigt hvordan jeg skal beskrive mit problem.
>> Det handler vist nok om at finde den korteste sti gennem et antal
>> tilstande....
>>
>> Jeg har en tilstandsmaskine som kan være i X forskellige tilstande.
>> Den skal være i stand til at gå fra en vilkårlig tilstand til en
>> vilkårlig
>> anden tilstand.
>> Det kan den kun hvis tilstandene er "ved siden af hinanden"
>> Jeg kan bevæge mig både frem og tilbage.
>>
>> Mit problem er:
>> Hvordan organiserer jeg, mest effektivt, tilstandene i en rækkefølge, som
>> muliggør alle tilstands-ændringer ?
>>
>> Exempel:
>> Der eksisterer 3 forskellige tilstande 0,1 og 2
>> den korteste beskrivelse af tilstands skift mellem dem må være
>> 0-1-2-0
>> Det kræver altså en sti med 4 punkter, for at jeg kan bevæge mig mellem 0
>> og
>> 1, mellem 1 og 2 og mellem 0 og 2
>>
>> Hvis der eksisterer 4 tilstande (0,1,2,3) kan man organisere stien:
>> 0-1-2-3-2-0-3-1
>> Men er det den kortest mulige organisation ?? Her har jeg jo to steder
>> hvor
>> 2 og 3 er forbundne.
>>
>> Hvad med 10 tilstande eller 50 ??
>
> Hvis du har N tilstande, skal du have (N*(N-1))/2 forbindelser, hvis alle
> skal
> være direkte forbundet med alle andre.
>
> Dvs (tilstande, forbindelser) bliver:
> (1,0)
> (2,1)
> (3,3)
> (4,6)
> (5,10)
> (6,15)
> ...
> etc.
> Skal disse skrives på en linie, som du har vist (på formen A-B-C-A) ,
> gælder
> at hver "instans" af en tilstand kun kan have 2 forbindelser, endvidere
> kan
> endepunkterne, som der kun er 2 af, kun have 1 forbindelse.
>
> 2 punkter A-B : 1 forbindelse
> 3 punkter A-B-C-A : 3 forbindelser
> 4 punkter A-B-C-D-A-C-D-B : 7 fobindelser, altså ikke de 6 som vi har
> beregnet.
>
> med 4 punkter skal hvert punkt have 3 forbindelser.
> Men da instanser altid får 2 forbindelse pånær endepunkter, har vi altså
> som i ovenstående at A og B (de er endepunkter) får deres 3 fobindelser,
> medens C og D er nødt til at instantieres 2 gange for at opnå deres 3
> forbindelser. De får nu fire (da de ikke er endepunkter) og dermed har
> vi en "spildforbindelse".
>
>
> 5 punkter A-B-C-D-E-C-A-D-B-E-A : 10 forbindelser.
> Altså ingen "spild".
> 6 punkter.
>
> Her skal hvert punkt have 5 forbindelser. Da kun 2 kan være endepunkter
> vil altså fire punkter skulle instantieres 2 gange, dvs 2
> "spildforbindelser".
>
> dvs man skulle få 17 forbindelser som "minimum".
>
> efter den device skulle man altså få:
> hvis N er lige fås (N-2)/2 spildforbindelser.
> hvis N er ulige fås 0 spildforbindelser.
>
> mvh
>
> --
> Søren Dideriksen