Sa se construiasca arborele de acoperire mimim, ilustrand ordinea de selectie a arcelor. Se vor aplica:
4.2. Se considera graful din figura 5. Sa se determine drumurile minime cu origine comuna in nodul 1. Se va enumera ordinea de selectie a nodurilor si se va reprezenta arborele de acoperire corespunzator drumurilor minime.
6.1. O companie de drumuri are sarcina de a moderniza o retea existenta de sosele care conecteaza multimea de localitati ale unui judet. Se cunosc perechile de localitati intre care exista sosele si lungimile acestora. Intre oricare doua localitati exista maximum o legatura directa. O cerinta impusa este ca circulatia intre oricare doua localitati sa se poata face urmand un traseu numai pe sosele modernizate.
Care va fi solutia propusa de compania care executa lucrarea? Care va fi solutia propusa de primaria localitatii resedinta de judet? Ce solutie mai buna pentru locuitorii capitalei poate oferi atunci compania care va executa lucrarile?
Argumentati alegerea celor 3 solutii.
Scrieti un program care primeste ca date de intrare harta rutiera a judetului si, pentru fiecare din cele 3 solutii, afiseaza soselele propuse spre modernizare. Programul va calcula si afisa procentul cu care solutia a doua( propusa de locuitorii capitalei) este mai costisitoare decat solutia solutia propusa de executantul lucrarii.
Indicatii:
Problema se poate modela cu ajutorul grafurilor ponderate neorientate. Localitatile judetului sunt nodurile unui graf, iar arcele reprezinta soselele existente.
Compania de drumuri va propune o solutie care sa minimizeze costul total al lucrarilor.Aceasta corespunde arborelui minim de acoperire.
Primaria capitalei propune o solutie care sa minimizeze costul de acces din capitala spre oricare din localitatile judetului. Aceasta corespunde arborelui de acoperire corespunzator drumurilor minime cu originea in capitala.
Solutia a 3-a, propusa de companie, poate imbunatati situatia din punctul de vedere al locuitorilor capitalei, alegand un alt arbore minim de acoperire(daca mai exista), avand radacina in nodul capitalei.
Costul unei solutii este direct proportional cu suma lungimilor tuturor soselelor modernizate.
6.2. Relativ la problema enuntata la 6.1., sa se calculeze si afiseze cu cat este mai lung drumul din capitala spre o localitate a judetului in cazul aplicarii solutiei 1 fata de situatia aplicarii solutiei 2.
Indicatie
Se va calcula lungimea drumului din capitala spre o anumita localitate in cadrul grafului care este arborele minim de acoperire. Se poate tine seama de faptul ca in arbore exista un unic drum intre doua noduri.
6.3. Se cunosc pozitiile celor N=1000 de localitati ale unei tari, date prin coordonatele lor (x,y) pe harta. Sa se determine configuratia unei retele telefonice (legaturile prin linii directe intre doua localitati) astfel incat fiecare localitate sa fie conectat la retea si costul total al retelei sa fie minim.
6.4. Problema comis-voiajorului: Un comis voiajor trebuie sa viziteze, in circuit, toate filialele firmei, aflate in N orase diferite. Nu este admisa vizitarea de 2 ori a unui oras. Se cunosc costurile calatoriei directe intre oricare doua orase. Costul total al calatoriei trebuie sa fie minim. Sa se realizeze un program care gaseste o solutie la aceasta problema.
Indicatii
Toti algoritmii care garanteaza gasirea solutiei optime necesita un timp de ordinul O(2N). Se va implementa un algoritm neoptim de tip Greedy, alegand de fiecare data ca oras urmator cel mai apropiat de orasul curent si care nu a fost inca vizitat. Acest algoritm necesita un timp de ordinul O(N2). Algoritmul se poate executa in mod repetat, considerand de fiecare data alt nod de start.