Search  
Thursday, October 22, 2020 ..:: Forum ::.. Register  Login
 Forum Minimize
Pentru a putea posta mesaje trebuie să vă înregistraţi.
Notă: Mesajele cu conţinut jignitor sau ilegal (inclusiv cereri de soft piratat) nu sunt acceptate şi vor fi şterse imediat .

Pentru a primi raspunsuri rapide si corecte, scrieti in mesaj ce intentionati sa faceti, ce mesaj de eroare primiti, in ce context si in urma caror actiuni. De asemenea, mentionati versiunea de FoxPro in care lucrati!
Dacă nu specificați versiunea, se consideră VFP 9.0 SP2.

SearchForum Home
  Visual FoxPro  Tema pentru acasa  algoritm parcur...
 algoritm parcurgere drum
 
 3/31/2014 1:46:48 PM
User is offlinelucipet
4 posts


algoritm parcurgere drum
 (N/A)
Caut un algoritm cu care sa pot parcurge intr-o matrice binara , toate traseele CONTINUE , formate doar de caracterul '1' , de pilda. Deplasarea se face de pe o latura a matricii pana la capatul drumului care e situat pe oricare latura a aceleasi matrici.Daca drumul e discontinuu, se opreste parcurgerea lui.Continuitate e considerata daca exista un vecin '1' pe linie sau coloana , NU si pe diagonala.
 4/1/2014 8:35:17 AM
User is offlinepraisach
208 posts
praisachion.blogspot.ro/
4th


Re: algoritm parcurgere drum
 (Romania)
Backtracking. Conditia de cotinuare este una din cele patru directii (sus, jos, stanga, dreapta; atentie la celulele care nu sunt in interior). O solutie se obtine cand din celula curenta, in oricare din cele patru directii valoarea este 0.
 4/1/2014 12:08:38 PM
User is offlinepraisach
208 posts
praisachion.blogspot.ro/
4th


Re: algoritm parcurgere drum
 (Romania)
Incerc sa detaliez.
Stiva va fi o matrice care contine nodul curent (elementul curent al matricei) si directia de deplasare spre urmatorul nod.
Fiind patru directii, veti stabili o conventie, de exemplu:
- 1 dreapta (coloana elementului curent +1)
- 2 jos (randul elementului curent +1)
- 3 stanga (coloana elementului curent -1)
- 4 sus (randul elementului curent -1)

Exemplu de stiva pentru drumul (1,1)->(1,2)->(2,2)
primul element (1,1)
stiva[1,1]=1 (deplasare spre dreapta)
stiva[1,2]=1 (linia 1)
stiva[1,3]=1 (coloana 1)
al doilea element (1,2)
stiva[1,1]=2 (deplasare in jos)
stiva[1,2]=1 (linia 1)
stiva[1,3]=2 (coloana 2)
al treilea element (2,2)
stiva[1,1]=4 (deplasare spre stanga, sau terminare)
stiva[1,2]=2 (linia 2)
stiva[1,3]=2 (coloana 2)

Pentru fiecare nod (element al matricei din stiva) se incearca prin backtrancking una din cele patru valori (directii de deplasare)
Se evalueaza noul nod posibil in conformitate cu directia propusa.
Cazuri posibile:
- nod inexistent (nodul curent e pe una din margini si se incearca iesirea in afara matricii)
- noul nod, conform directiei de deplasare, contine valoarea 0, deci nu e bun
- noul nod, conform directiei de deplasare, contine valoarea 1, insa se regaseste printre nodurile precedente (linia si coloana coincide cu una din liniile si coloanele stivei), deci nu e bun (evitarea ciclurilor)
- noul nod e bun
Daca noul nod e bun, se mareste contorul stivei si se incarca cu noul element al matricei (conform cu directia de deplasare), propunandu-se valoarea 1 (stanga) in prima coloana a stivei
Daca nodul nu e bun, se testeaza daca s-a obtinut o solutie (in ultimul nod al stivei s-au incercat toate cele patru variante); daca s-a obtinut solutie se retine, iar daca nu se incearca o noua directie de deplasare
Update
In aceasta sectiune exista un model de backtracking pentru permutari. Principiul este similar. Diferente majore :
- in acest caz stiva e o matrice (se retine atat directia/valoarea curenta cat si linia si coloana nodului curent)
- numarul de valori posibile pentru fiecare nod al stivei este 4
- stiva are dimensiunea NxM (linii x coloane)
- testarea continuarii este mai comnplexa: se evalueaza daca noua directie nu duce la un element in afara matricii; daca noul element e in interior se verifica daca are valoarea 1; daca e in interior si are valoarea 1 se verifica daca linia si coloana sa nu a fost deja parcursa in drumul curent
- solutia se obtine cand nu se mai poate continua si valorea din prima coloana a elementului din varful stivei=4
 4/1/2014 9:46:26 PM
User is offlinepraisach
208 posts
praisachion.blogspot.ro/
4th


Re: algoritm parcurgere drum
 (N/A)
Sunt curios care e solutia gasita de dumneavoastra, ca sa o putem compara cu solutia gasita de mine.
 4/3/2014 9:28:19 PM
User is offlinepraisach
208 posts
praisachion.blogspot.ro/
4th


Re: algoritm parcurgere drum
 (N/A)
Probabil ca ati rezolvat deja probelme. In ceea ce ma priveste gasesc incorect sa nu postez o solutie anuntata.
Solutia pe care o prezint gaseste toate drumurile care incep dintr-un anumit nod (dintr-un anumit element al matricei).
Cu mici modificari puteti obtine intr-un singur tabel toate drumurile, indiferent de nodul din care incep.

LOCAL lnLinii,lnColoane,lnLinCur,lnColCur
* demo pentru o matrice cu 5 linii si 5 coloane
lnLinii=5
lnColoane=5
LOCAL noduri[m.lnLinii,m.lnColoane]
* Definirea matricii nodurilor
Defineste_drum(@noduri)
*********
* teste *
*********
* 1 drumurile incepand din nodul aflat pe linia 5, coloana 3
lnLinCur=5
lnColCur=3
Drumuri(@noduri,m.lnLinii,m.lnColoane,m.lnLinCur,m.lnColCur)
BROWSE
* 2 drumurile incepand din nodul aflat pe linia 1, coloana 1
lnLinCur=1
lnColCur=1
Drumuri(@noduri,m.lnLinii,m.lnColoane,m.lnLinCur,m.lnColCur)
BROWSE
* 3 drumurile incepand din nodul aflat pe linia 3, coloana 1
lnLinCur=3
lnColCur=1
Drumuri(@noduri,m.lnLinii,m.lnColoane,m.lnLinCur,m.lnColCur)
BROWSE
* 4 drumurile incepand din nodul aflat pe linia 3, coloana 3
lnLinCur=3
lnColCur=3
Drumuri(@noduri,m.lnLinii,m.lnColoane,m.lnLinCur,m.lnColCur)
BROWSE

Procedure Drumuri
Lparameter noduri,N,M,linstart,colstart && matricea,dimensiunea matricii,nodul de start
LOCAL laStack[m.N*m.M,3],pos,lContinue,lCanContinue,lni,lnNewLin,lnNewCol,lcPath
CREATE TABLE drum (drum C(254)) && pentru matrice mari mai curand camp de tip memo
pos=1
laStack[m.pos,1]=1
laStack[m.pos,2]=m.linstart
laStack[m.pos,3]=m.colstart
lContinue=.T.
Clea
Do While m.lContinue
    If laStack[m.pos,1] <= 4 && 4 directii 1 dreapta, 2 jos, 3 stanga, 4 sus
        lCanContinue=.T.
        DO CASE
        CASE laStack[m.pos,1]=1 && incercare deplasare spre dreapta
            lnNewLin=laStack[m.pos,2]
            lnNewCol=laStack[m.pos,3]+1
            DO CASE
            CASE laStack[m.pos,3]=m.M && sunt deja in ultima coloana
                lCanContinue=.F.
            CASE noduri[laStack[m.pos,2],laStack[m.pos,3]+1]=0
                lCanContinue=.F.
            ENDCASE
        CASE laStack[m.pos,1]=2 && incercare deplasare in jos
            lnNewLin=laStack[m.pos,2]+1
            lnNewCol=laStack[m.pos,3]
            DO CASE
            CASE laStack[m.pos,2]=m.N && sunt deja in ultimul rand
                lCanContinue=.F.
            CASE noduri[laStack[m.pos,2]+1,laStack[m.pos,3]]=0
                lCanContinue=.F.
            ENDCASE
        CASE laStack[m.pos,1]=3 && incercare deplasare spre stanga
            lnNewLin=laStack[m.pos,2]
            lnNewCol=laStack[m.pos,3]-1
            DO CASE
            CASE laStack[m.pos,3]=1 && sunt deja in prima coloana
                lCanContinue=.F.
            CASE noduri[laStack[m.pos,2],laStack[m.pos,3]-1]=0
                lCanContinue=.F.
            ENDCASE
        CASE laStack[m.pos,1]=4 && incercare deplasare in sus
            lnNewLin=laStack[m.pos,2]-1
            lnNewCol=laStack[m.pos,3]
            DO CASE
            CASE laStack[m.pos,2]=1 && sunt deja in primul rand
                lCanContinue=.F.
            CASE noduri[laStack[m.pos,2]-1,laStack[m.pos,3]]=0
                lCanContinue=.F.
            ENDCASE
        ENDCASE
        IF lCanContinue  && verificare ciclu, adica un nod duplicat
            For lni = 1 To m.pos-1
                If m.lnNewLin = laStack[m.lni,2] AND m.lnNewCol = laStack[m.lni,3]
                    lCanContinue=.F.
                ENDIF
            ENDFOR
        ENDIF
        IF lCanContinue
            pos=m.pos+1
            laStack[m.pos,1]=1
            laStack[m.pos,2]=m.lnNewLin
            laStack[m.pos,3]=m.lnNewCol
        ELSE
            IF laStack[m.pos,1]=4 && solutie
                lcPath=''
                FOR lni=1 TO m.pos&&-1
                    lcPath=m.lcPath+IIF(EMPTY(m.lcPath),"","->")+"("+TRANSFORM(laStack[m.lni,2])+","+TRANSFORM(laStack[m.lni,3])+")"
                NEXT
                SELECT drum
                LOCATE FOR m.lcPath $ drum.drum
                IF !FOUND()
                    INSERT INTO drum VALUES (m.lcPath)
                ENDIF
            ENDIF
            laStack[m.pos,1]=laStack[m.pos,1]+1
        ENDIF
    Else
        pos=m.pos-1
        m.lContinue=pos>0
        If m.lContinue
            laStack[m.pos,1]=laStack[m.pos,1]+1
        Endif
    Endif
ENDDO
ENDPROC

PROCEDURE Defineste_drum
    LPARAMETERS noduri
*    linia 1
    STORE 1 TO noduri[1,1],noduri[1,2],noduri[1,4],noduri[1,5]
    STORE 0 TO noduri[1,3]
*    linia 2
    STORE 1 TO noduri[2,1],noduri[2,2],noduri[2,5]
    STORE 0 TO noduri[2,3],noduri[2,4]
*    linia 3
    STORE 1 TO noduri[3,1],noduri[3,3],noduri[3,5]
    STORE 0 TO noduri[3,2],noduri[3,4]
*    linia 4
    STORE 1 TO noduri[4,4]
    STORE 0 TO noduri[4,1],noduri[4,2],noduri[4,3],noduri[4,5]
*    linia 5
    STORE 1 TO noduri[5,3],noduri[5,4]
    STORE 0 TO noduri[5,1],noduri[5,2],noduri[5,5]
*    1    1    0    1    1
*    1    1    0    0    1
*    1    0    1    0    1
*    0    0    0    1    0
*    0    0    1    1    0
ENDPROC

  Visual FoxPro  Tema pentru acasa  algoritm parcur...

Search  Forum Home         

 Google Ads Minimize

    

Copyright 2002-2013 Profox   Terms Of Use  Privacy Statement