Problema comis-voiajorului

Algoritmi nedeterministi :

Activitatea unui algoritm nedeterminist se desfasoara in doua etape: intr-o prima etapa “se ghiceste” o anumita structura S ¸si in etapa a doua se verifica daca S satisface o conditia de rezolvare a problemei. Putem adauga “puteri magice de ghicire” unui limbaj de programare adaugandu-i o functie de forma:

choice(M) – care intoarce un element din multimea M.

Pentru a sti daca verificarea s-a terminat cu succes sau nu adauga ¸si doua instructiuni de terminare:

success – care semnaleaza terminarea verificarii (si a a algoritmului) cu succes, si

failure – care semnaleaza terminarea verificarii (si a a algoritmului) fara succes.

Aceasta definitie a algoritmilor nedeterministi este strans legata de rezolvarea problemelor de decizie, ce constituie forma standard utilizata de teoria calculabilitatii.

Notam cu P clasa problemelor P pentru care exista un algoritm determinist care rezolva P in timp polinomial si cu NP clasa problemelor P pentru care exista un algoritm nedeterminist care rezolva P in timp polinomial. Evident, are loc P NP.

Daca o problema P apartine clasei NP, atunci exista polinoamele p(n) ¸si q(n) astfel incat P poate fi rezolvata de un algoritm determinist in timpul O(p(n)(2qn)).

Fie P ¸si Q doua probleme si g(n) un polinom. Spunem ca P este transformata in timpul O(g(n)) in problema Q daca exista o functie t astfel incat:

1. t are complexitatea timp O(g(n));

2. t transforma o instant¸a p P intr-o instanta t(p) Q;

3. pentru orice instanta p P, p ¸si t(p) au aceal¸si raspuns (valoare de adevar).

O problema P este NP-completa daca:

- este in NP, i.e. exista un algoritm nedeterminist care rezolva P in timp polinomial (echivalent, exista un algoritm determinist care rezolva P in timp exponential);

- este NP-dificila, i.e. orice alta problema Q din NP se reduce polinomial la P.

Problema comis-voiajorului

In problema comis-voiajorului care este strâns legata de problema ciclului hamiltonian, un comis-voiajor trebuie sa viziteze n orase. Modeland problema pe un graf cu n vârfuri, putem spune ca comis-voiajorul doreste sa faca un tur, sau un ciclu hamiltonian, vizitând fiecare oras o singura data si terminând cu orasul din care a pornit. Pentru calatoria intre orasele i si j exista un cost c(i,j) reprezentat printr-un numar intreg. Comis-voiajorul doreste sa parcurga un ciclu al carui cost total sa fie minim, unde costul total este suma costurilor individuale de pe muchiile care formeaza ciclul.

Limbajul formal pentru problema de decizie corespunzatoare este :

PCV={<G,c,k> : G=(V,E) este un graf complet, c este o functie de la V ×V → Z ,

k Z si G are un ciclu pentru comisul voiajor, de cost cel mult k}.

Problema Comis Voiajor (CV ):

Instanta: Un graf ponderat cu c(i, j)

pentru orice muchie {i, j} E ¸si K Z.

Intrebare: Exista un circuit hamiltonian de cost ≤ K?

Sa se arate ca CV este NP-completa.

Pentru gasirea unei solutii optime la aceasta problema este nevoie de algoritmi cu timp de rulare foarte mare (de ordin exponential O(2n)). In situatiile practice asemenea algoritmi cu timp foarte mare de rulare nu sunt acceptabili. Ca urmare se face un compromis si se accepta algoritmi care nu gasesc solutia optima ci doar o solutie aproape de optim, dar au in schimb un timp de rulare mic. Propunem in continuare o solutie greedy la aceasta problema. Ideea este urmatoarea. Se porneste dintr-un oras oarecare. Se cauta drumul cel mai scurt care pleaca din orasul respectiv catre orase nevizitate inca. Se parcurge acel drum si se ajunge intr-un alt oras. Aici din nou se cauta cel mai scurt drum catre orasele nevizitate inca. Se parcurge si acest drum, ajungându-se intr-un nou oras. Repetând acesti pasi se parcurg toate orasele. La final se parcurge drumul care duce inapoi spre primul oras.

Sa consideram exemplul din figura 1. Avem 4 orase cu distantele reprezentate in figura.

Pornim vizitarea oraselor din orasul 0. De aici alegem drumul cel mai scurt catre orasele nevizitate, si anume (0,2) de lungime 2. Ajunsi in orasul 2, alegem din nou drumul cel mai scurt spre orasele nevizitate, si anume (2,3) de lungime 1. Din orasul 3 mai avem doar un singur oras nevizitat, 1, asa ca alegem drumul spre el (3,1) de lungime 1. In acest moment am parcurs toate orasele si ne reintoarcem in orasul 0 pe drumul (1,0) de lungime 4. Drumul rezultat este 0, 2, 3, 1, 0, iar distanta totala de parcurs este 2 + 1 + 1 + 4 = 8.

Implementare Distantele intre orase le memoram intr-un tablou bidimensional D. Distanta intre orasele (i,j) va fi memorata in elementul di,j al matricii. In termeni Greedy, multimea initiala A este multimea tuturor perechilor de orase. Pentru reteaua de orase din figura 2 multimea A contine elementele {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}. Multimea B care trebuie gasita va contine o parte din aceste perechi de orase, si anume acele perechi care inlantuite sa formeze un drum ce trece prin toate orasele. Daca avem un numar de n orase, atunci multimea B va contine n perechi de orase.

In implementare nu vom lucra cu multimea A sub aceasta forma explicita de perechi de orase, ci vom folosi matricea distantelor D. De asemenea drumul comis-voiajorului nu il vom pastra sub forma de perechi de orase, ci sub forma unui sir al oraselor.

Pentru a memora drumul parcurs de comis-voiajor, folosim un tablou unidimensional drum. In acest tablou vom memora indicii oraselor parcuse, in ordinea parcurgerii.

Pentru a sti care orase au fost parcurse, facem o marcare logica a oraselor folosind un tablou unidimensional vizitat. Elementele din acest tablou care au valoarea 1 reprezinta orase vizitate.

Calculabilitate si complexitate , Algoritmi nedeterministi - problema comis-voiajorului.