Κεφάλαιο 6Αλγοριθμικές Τεχνικές

Κατ’ αρχάς παρουσιάζεται η πρώτη μας προσπάθεια: ένας προφανής τρόπος επίλυσης του προβλήματος, όπου εξετάζεται κάθε δυνατή περίπτωση υποπίνακα. Η συνάρτηση max_subseq_sum1 που ακολουθεί, δέχεται τον πίνακα A, που αποτελείται από $n$ στοιχεία, και επιστρέφει τη ζητούμενη μέγιστη τιμή. Με left και right συμβολίζονται τα δύο ακραία στοιχεία της υποακολουθίας, που κάθε φορά εξετάζεται. Για κάθε εξεταζόμενη υποακολουθία, το αντίστοιχο άθροισμα των τιμών των στοιχείων της υπολογίζεται με τη βοήθεια της μεταβλητής current_sum που συγκρίνεται με τη μεταβλητή max_sum και την αντικαθιστά αν έχει μεγαλύτερη τιμή.

     function max_subseq_sum1;
1.   max_sum <-- 0; left <-- 0; right <-- 0;
2.   for i <-- 1 to n do
3.      for j <-- i to n do
4.         current_sum <-- 0;
5.         for k <-- i to j do
6.            current_sum <-- current_sum+A[k];
7.         if (current_sum>max_sum) then
8.            max_sum <-- current_sum;
9.            left <-- i; right <-- j
10.  return max_sum

Η συνάρτηση αυτή αποτελείται από τρεις φωλιασμένες εντολές for. Η εύρεση της πολυπλoκότητας αναδεικνύεται εύκολα, όπως φαίνεται στη συνέχεια, θεωρώντας ως βαρόμετρο την εντολή 6 (με μοναδιαίο κόστος), που βρίσκεται στο εσωτερικότερο σημείο των βρόχων.

	$T(n)$	$=$	${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=i}^n}{\displaystyle \sum _{k=i}^j}1={\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=i}^n}(j-i+1)$
		$=$	${\displaystyle \frac{1}{2}}{\displaystyle \sum _{i=1}^n}(n-i+1)(n-i+2)$
		$=$	${\displaystyle \frac{1}{2}}{\displaystyle \sum _{i=1}^n}{i}^2-\left(n+{\displaystyle \frac{3}{2}}\right){\displaystyle \sum _{i=1}^n}i+{\displaystyle \frac{1}{2}}(n^2+3n+2){\displaystyle \sum _{j=1}^n}1$
		$=$	${\displaystyle \frac{1}{2}}{\displaystyle \frac{n(n+1)(2n+1)}{6}}-\left(n+{\displaystyle \frac{3}{2}}\right){\displaystyle \frac{n(n+1)}{2}}+{\displaystyle \frac{n}{2}}(n^2+3n+2)$
		$=$	${\displaystyle \frac{n^3+3n^2+2n}{6}}$

Έτσι, προκύπτει ότι η πολυπλοκότητα αυτού του αλγορίθμου είναι Θ($n^3$).

Παρατηρώντας τον προηγούμενο αλγόριθμο εύκολα βγαίνει το συμπέρασμα ότι γίνονται πολλοί περιττοί υπολογισμοί. Έτσι, προκειμένου να βελτιωθεί η πολυπλοκότητα του αλγορίθμου αυτού, μπορεί να παραληφθεί η μία από τις τρεις φωλιασμένες εντολές for. Αυτό προκύπτει από την παρατήρηση ότι το άθροισμα των τιμών των στοιχείων του υποπίνακα A(left..right) είναι ίσο με το άθροισμα των τιμών των στοιχείων του υποπίνακα A(left..right-1) και του στοιχείου A(right), οπότε κατά τον υπολογισμό του A(left..right) υπολογίζεται και πάλι το άθροισμα των τιμών των στοιχείων A(left..right-1). Αν γίνει η αλλαγή αυτή στη συνάρτηση max_subseq_sum1 προκύπτει η συνάρτηση max_subseq_sum2.

     function max_subseq_sum2;
1.   max_sum <-- 0; left <-- 0; right <-- 0;
2.   for i <-- 1 to n do
3.      current_sum <-- 0;
4.      for j <-- i to n do
5.         current_sum <-- current_sum+A[j];
6.         if (current_sum>max_sum) then
7.            max_sum <-- current_sum;
8.            left <-- i; right <-- j
9.   return max_sum

Ευκολότερα από την προηγούμενη φορά είναι δυνατόν να αποδειχθεί ότι ο αλγόριθμος έχει τετραγωνική πολυπλοκότητα Θ($n^2$).

Μία διαφορετική αντιμετώπιση του προβλήματος προκύπτει ακολουθώντας τη στρατηγική Διαίρει και Βασίλευε, δηλαδή διαιρώντας τον πίνακα σε δύο υποπίνακες (σχεδόν) ίσου μήκους. Για τα υποδιανύσματα αυτά υπολογίζονται αναδρομικά οι ακολουθίες μέγιστου αθροίσματος, διαιρώντας τα σε επί μέρους υποδιανύσματα, αν και όσο χρειασθεί. Έτσι, διακρίνουμε τρεις περιπτώσεις: η υποακολουθία του μέγιστου αθροίσματος είτε περιέχεται στο πρώτο μισό του αρχικού πίνακα, είτε περιέχεται στο δεύτερο μισό, είτε τέλος περιέχεται και στα δύο. Όταν ισχύει η τρίτη περίπτωση, τότε η λύση του προβλήματος βασίζεται στη σκέψη ότι πρέπει να υπολογισθεί αφενός η υποακολουθία με μέγιστο άθροισμα του πρώτου μισού, η οποία περιέχει το τελευταίο στοιχείο του πρώτου υποπίνακα και αφετέρου η υποακολουθία με μέγιστο άθροισμα του δεύτερου μισού, η οποία περιέχει το πρώτο στοιχείο του δεύτερου υποπίνακα. Η λύση του αρχικού προβλήματος είναι εκείνη από τις τρεις υποακολουθίες που έχει το μέγιστο άθροισμα των τιμών των στοιχείων της.

Για παράδειγμα, αν ο πίνακας Α έχει την πρώτη μορφή του Πίνακα 6.2, τότε διαιρείται στο μέσο και προκύπτει η δεύτερη μορφή του σχήματος. Με βάση αυτή τη θεώρηση υπολογίζεται η υποακολουθία μέγιστου αθροίσματος του πρώτου μισού (είναι ο υποπίνακας A(1..2)=(3,3) με άθροισμα 6), η υποακολουθία του δεύτερου μισού (είναι ο υποπίνακας A(7)=(7) με ένα μόνο στοιχείο) και η υποακολουθία που περιέχει το τελευταίο στοιχείο του πρώτου μισού και το πρώτο του δεύτερου μισού (είναι ο υποπίνακας A(4..7)=(1,4,-4,7) με άθροισμα 8). Επομένως, η υποακολουθία με μέγιστο άθροισμα είναι ο υποπίνακας A(4...7) με άθροισμα των τιμών των στοιχείων ίσο με 8.

Η αναδρομική συνάρτηση max_subseq_sum3 υπολογίζει το μέγιστο άθροισμα των τιμών των στοιχείων μεταξύ όλων των υποακολουθιών του πίνακα A, διαιρώντας τον πίνακα σε επιμέρους τμήματα. Αυτό είναι το σκέλος Διαίρει. Η βασική συνθήκη (base case) θεωρεί την υποακολουθία με ένα μόνο στοιχείο, όπου αν το στοιχείο αυτό έχει τιμή θετική, τότε το άθροισμα ισούται με την τιμή αυτή, αλλιώς το άθροισμα ισούται με μηδέν. Με άλλα λόγια, στο σημείο αυτό υλοποιείται το σκέλος Βασίλευε της γενικής μεθόδου.

     function max_subseq_sum3(left,right);
1.   if left=right then
2.      if A[left]>0 then return A[left]
3.      else return 0;
4.   else
5.      center <-- (left+right)/2;
6.      max_lsum <-- max_subseq_sum3(left,center);
7.      max_rsum <-- max_subseq_sum3(center+1,right);
8.      max_lborder_sum <-- 0; lborder_sum <-- 0;
9.      for i <-- center downto left do
10.        lborder_sum <-- lborder_sum+A[i];
11.        if (lborder_sum>max_lborder_sum) then
12.           max_lborder_sum <-- lborder_sum
13.     max_rborder_sum <-- 0; rborder_sum <-- 0;
14.     for i <-- center+1 to right do
15.        rborder_sum <-- rborder_sum+A[i];
16.        if (rborder_sum>max_rborder_sum) then
17.           max_rborder_sum <-- rborder_sum
18.     temp <-- max_lborder_sum+max_rborder_sum;
19.     return max(max_lsum,max_rsum,temp)

Οι χρησιμοποιούμενες μεταβλητές είναι ακέραιες και έχουν το εξής νόημα. Οι μεταβλητές max_lsum και max_rsum εξυπηρετούν τις δύο πρώτες περιπτώσεις που αναφέρθηκαν και δίνουν το μέγιστο άθροισμα για το αριστερό και δεξιό υποπίνακα, αντίστοιχα. Οι υπόλοιπες μεταβλητές αφορούν στην τρίτη περίπτωση. Οι μεταβλητές lborder_sum και rborder_sum δίνουν το κάθε φορά υπολογιζόμενο άθροισμα στα αριστερά και δεξιά του center, ενώ στις max_lborder_sum και max_rborder_sum αποθηκεύεται το μέχρι στιγμής μέγιστο άθροισμα για το αριστερό και δεξιό υποπίνακα αντίστοιχα, τα οποία αργότερα θα προστεθούν για να δώσουν το αποτέλεσμα της τρίτης περίπτωσης. Τέλος, θεωρείται ότι υπάρχει μία συνάρτηση max, που επιστρέφει το μεγαλύτερο από τα στοιχεία που είναι τα ορίσματά της.

Η πολυπλοκότητα της μεθόδου μπορεί να προκύψει με βάση την αντίστοιχη αναδρομική εξίσωση. Κατ’αρχάς, αν το μήκος του πίνακα είναι 1, τότε η δραστηριότητα στις εντολές 1-3 αποτιμάται ως σταθερό μοναδιαίο κόστος, δηλαδή $T(1)=1$. Αν ο πίνακας είναι μεγαλύτερος, τότε θα εκτελεσθούν δύο αναδρομικές κλήσεις, ενώ στις εντολές 9-17 θα εκτελεσθούν δύο απλοί βρόχοι for γραμμικής πολυπλοκότητας. Επομένως, ισχύει:

$$T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n$$

(6.1)

Θεωρώντας ότι $n=2^k$ για απλοποίηση, έπεται ότι:

	$T(n)$	$=$	$2T(n/2)+n=\mathrm{\hspace{0.25em}2}\left(2T(n/4)+n/2\right)+n=\mathrm{\hspace{0.25em}4}T(n/4)+2n$
		$=$	$\mathrm{\dots }={\mathrm{\hspace{0.25em}2}}^{k}T(n/2^k)+kn={\mathrm{\hspace{0.25em}2}}^k+kn=n\lg n+n=\mathrm{\Theta }(n\lg n)$

Στο συμπέρασμα αυτό καταλήγουμε αν απλώς θεωρήσουμε ότι το βάθος των αναδρομικών κλήσεων είναι Θ($\lg n$), ενώ κάθε φορά ο πίνακας υφίσταται επεξεργασία της τάξης Θ($n$). Ακολουθεί ο τελευταίος αλγόριθμος, που είναι ο καλύτερος που μπορούμε να σχεδιάσουμε.

Τέλος, λοιπόν, μία ακόμη λύση του προβλήματος που διαπραγματευόμαστε, δίνεται από τη συνάρτηση max_subseq_sum4 που φαίνεται στη συνέχεια. Η συνάρτηση αυτή, σαρώνει όλα τα στοιχεία του πίνακα και τα προσθέτει όσο το άθροισμα τους είναι θετικό. Αν κάποια στιγμή η τιμή του αθροίσματος αυτού γίνει αρνητική, τότε μηδενίζεται η τιμή αυτού του αθροίσματος και συνεχίζεται η άθροιση των τιμών των στοιχείων από το επόμενο στοιχείο.

     function max_subseq_sum4;
1.   i <-- 0; current_sum <-- 0; max_sum <-- 0;
2.   left <-- 0; right <-- 0;
3.   for j <-- 1 to n do
4.      current_sum <-- current_sum+A[j];
5.      if (current_sum>max_sum) then
6.         max_sum <-- current_sum;
7.         left <-- i; right <-- j
8.      else
9.         if (current_sum<0) then
10.           i <-- j+1; current_sum <-- 0
11.  return max_sum;

Ο αλγόριθμος αυτός ανήκει στην κατηγορία των λεγόμενων on-line αλγορίθμων. Οι αλγόριθμοι αυτοί επεξεργάζονται τα δεδομένα όπως έρχονται, δηλαδή δεν είναι ανάγκη τα δεδομένα να είναι γνωστά εκ των προτέρων. Επιπλέον, αυτός ο τρόπος επίλυσης παρουσιάζει το σημαντικό πλεονέκτημα ότι σαρώνει μόνο μία φορά τα στοιχεία του πίνακα. Αυτό σημαίνει ότι αν εξετασθεί κάποιο στοιχείο από τον αλγόριθμο, τότε δεν υπάρχει λόγος να παραμένει κάπου αποθηκευμένο γιατί δεν πρόκειται να χρησιμοποιηθεί ξανά. Επίσης, ένα τελικό πλεονέκτημα του αλγορίθμου αυτού είναι ότι σε κάθε χρονική στιγμή, κατά τη διάρκεια της εκτέλεσης του αλγορίθμου, ο αλγόριθμος έχει υπολογίσει το μέγιστο άθροισμα της υποακολουθίας των στοιχείων που έχει εξετάσει. Η ανάλυση αυτού του αλγορίθμου είναι πολύ εύκολη υπόθεση. Καθώς ο κορμός του αλγορίθμου είναι ένας απλός βρόχος for (εντολή 3), έπεται ότι η πολυπλοκότητα είναι γραμμική Θ($n$).

Μία πρώτη βελτίωση σε σχέση με την προηγούμενη προφανή αλλά μη πρακτική μέθοδο, είναι να θεωρηθεί ότι δεν μπορούν να τοποθετηθούν περισσότερες από μία βασίλισσες στη ίδια γραμμή. Η νέα μέθοδος οδηγεί σε σημαντική βελτίωση καθώς το πλήθος των δυνατών διαφορετικών καταστάσεων μειώνεται σε $8^8$=16.777.216. Ο αριθμός αυτός προκύπτει λαμβάνοντας υπ’όψιν ότι κάθε βασίλισσα μπορεί να καταλάβει 1 θέση μεταξύ 8 υποψηφίων θέσεων, ενώ η τοποθέτηση μίας βασίλισσας στην αντίστοιχη γραμμή μπορεί, κατ’ αρχάς να θεωρηθεί ανεξάρτητο γεγονός από τις τοποθετήσεις των άλλων βασιλισσών.

Οι βασίλισσες αριθμούνται από 1 ως 8, όπως επίσης οι στήλες και οι γραμμές της σκακιέρας. Έστω ότι η $i$-οστή βασίλισσα τοποθετείται στην $i$-οστή γραμμή και στη στήλη που συμβολίζεται με $X(i)$ (όπου $1\le i\le 8$). Άρα, λύσεις του προβλήματος αποτελούν τα διανύσματα $(X(1),\mathrm{\dots },X(8))$, με τέτοιες τιμές των $X(i)$, έτσι ώστε να μην υπάρχουν δύο οποιεσδήποτε βασίλισσες που να βρίσκονται στην ίδια στήλη ή στην ίδια διαγώνιο. Συνεπώς, δεδομένης μίας τοποθέτησης για κάθε ζεύγος βασιλισσών πρέπει να γίνουν δύο έλεγχοι: (α) για το αν βρίσκονται στην ίδια στήλη και (β) για το αν βρίσκονται στην ίδια διαγώνιο. Ο έλεγχος για να διαπιστώσουμε αν δύο βασίλισσες βρίσκονται στην ίδια στήλη είναι εύκολος. Δηλαδή, αν για την $i$-οστή και την $j$-οστή βασίλισσα ισχύει $X(i)=X(j)$ (όπου $1\le i,j\le 8$), τότε είναι προφανές ότι οι βασίλισσες αυτές βρίσκονται στην ίδια στήλη. Όμως, πώς διαπιστώνουμε αν δύο βασίλισσες βρίσκονται στην ίδια διαγώνιο;

Ο έλεγχος για το αν δύο βασίλισσες ανήκουν στην ίδια διαγώνιο βασίζεται στην εξής διαπίστωση: Αν θεωρήσουμε οποιαδήποτε θέση μίας διαγωνίου με κατεύθυνση από επάνω αριστερά προς κάτω δεξιά, τότε η διαφορά “γραμμή-στήλη” παραμένει σταθερή. Για παράδειγμα, για τις θέσεις (1,1), (2,2), …, (8,8) της κύριας διαγωνίου που ακολουθεί αυτήν την κατεύθυνση, η διαφορά αυτή ισούται με 0. Επίσης για τις θέσεις (1,2), (2,3), …, (7,8) (αντίστοιχα (2,1), (3,2), … (8,7)) της διαγωνίου που είναι επάνω (αντίστοιχα κάτω) από την προηγούμενη κύρια διαγώνιο, η διαφορά αυτή είναι -1 (αντίστοιχα 1).

Για τις θέσεις των διαγωνίων που έχουν κατεύθυνση από επάνω δεξιά προς κάτω αριστερά παρατηρούμε ότι παραμένει σταθερό το άθροισμα “γραμμή+στήλη”. Για παράδειγμα, για τα στοιχεία (1,8), (2,7), … (8,1) της κύριας διαγωνίου στη συγκεκριμένη κατεύθυνση ισχύει “γραμμή+στήλη”=9. Για τα στοιχεία των διαγωνίων επάνω και κάτω από τη κεντρική αυτή διαγώνιο ισχύει “γραμμή+στήλη”=8 και 10, αντίστοιχα. Έτσι, με βάση τις παρατηρήσεις αυτές, καταλήγουμε ότι αν ισχύει $i-X(i)=j-X(j)$ ή $i+X(i)=j+X(j)$, τότε η $i$-οστή και η $j$-οστή βασίλισσα ανήκουν στην ίδια διαγώνιο.

Η λογική συνάρτηση Place1(k) που ακολουθεί, λαμβάνει ως παράμετρο την τιμή k της βασίλισσας που πρόκειται να τοποθετηθεί στη σκακιέρα, ελέγχει τις θέσεις των βασιλισσών στις προηγούμενες γραμμές και επιστρέφει true, αν μπορεί να γίνει η τοποθέτησή της στη στήλη X(k).

     function Place1(k);
1.   j <-- 1; flag <-- true;
2.   while (j<k-1) and (flag=true) do
3.      if (X[i]<>X[k]) or (abs(X[i]-X[k])<>abs(i-k))
4.         then j <-- j+1
5.      else flag <-- false;
6.   return flag

Για να καθορισθεί αν ένα διάνυσμα ($X(1),\mathrm{\dots },X(8)$), με τιμές των $X(i)$ (για $1\le i\le 8$) στο διάστημα [1,8], αποτελεί λύση του προβλήματος πρέπει να ελεγχθούν όλα τα ζεύγη των βασιλισσών, οπότε αν βρεθεί έστω και ένα ζεύγος όπου οι βασίλισσες αλληλο-απειλούνται, τότε το διάνυσμα δεν αποτελεί λύση. Ο έλεγχος αυτός γίνεται με την κλήση της λογικής συνάρτησης Solution(X), που έχει παράμετρο το διάνυσμα X και επιστρέφει true, αν το X είναι λύση του προβλήματος.

     function Solution(X);
1.   i <-- 1; flag <-- true;
2.   while (i<=8) and (place1(i)) do i <-- i+1;
3.   if i=9 then return true else return false

Η μέθοδος αυτή επίλυσης του προβλήματος μπορεί να υλοποιηθεί με τη χρήση 8 φωλιασμένων εντολών for, όπως φαίνεται στη συνέχεια. Όπως αναφέρθηκε, ο αλγόριθμος αυτός εξετάζει συνολικά 16.777.216 διαφορετικές τοποθετήσεις. Την πρώτη από αυτές, την βρίσκει και την τυπώνει μετά από 1.299.852 δοκιμές.

     procedure Queens1;
1.   for X[1] <-- 1 to 8 do
2.      for X[2] <-- 1 to 8 do
3.         for X[3] <-- 1 to 8 do
4.            for X[4] <-- 1 to 8 do
5.               for X[5] <-- 1 to 8 do
6.                  for X[6] <-- 1 to 8 do
7.                     for X[7] <-- 1 to 8 do
8.                        for X[8] <-- 1 to 8 do
9.                           if Solution(X) then
10.                             for j <-- 1 to 8 do
11.                                write(X[j],' ')

Όπως έχει ήδη αναφερθεί, λύσεις του προβλήματος αποτελούν τα διανύσματα ($X(1),\mathrm{\dots },X(8)$) με στοιχεία που είναι διαφορετικά μεταξύ τους και μπορούν να πάρουν τιμές από 1 έως 8, δηλαδή αποτελούν διαφορετικές διατάξεις των ακεραίων 1..8. Αυτό οδηγεί σε μία νέα μέθοδο που στηρίζεται στην εξέταση πολύ λιγότερων καταστάσεων σε σχέση με τις μεθόδους που εξετάσθηκαν προηγουμένως. Το πλήθος των δυνατών καταστάσεων είναι 8!= 40.320.

Μία άλλη προσέγγιση του προβλήματος, λοιπόν, είναι με την κλήση κάποιας διαδικασίας Perm να παραχθούν όλες οι διαφορετικές διατάξεις των αριθμών στο διάνυσμα (1,2,3,4,5,6,7,8). Υπάρχουν πολλές μέθοδοι εύρεσης των διαφορετικών αυτών διατάξεων, οι οποίες λέγονται γεννήτριες διατάξεων (permutation generation). H επόμενη διαδικασία Perm στηρίζεται στην εξής λογική: Θέτει όλες τις τιμές από 1 ως 8 στην πρώτη θέση του διανύσματος και για κάθε τέτοια τοποθέτηση αναδρομικά βρίσκει τις διαφορετικές διατάξεις των 7 στοιχείων του διανύσματος, τα οποία απομένουν. Όταν αναδιαταχθούν τα 8 στοιχεία, τότε τυπώνεται το διάνυσμα που προκύπτει, αν είναι λύση του προβλήματος.

     procedure Perm(i);
1.   if i=n then
2.      if Solution(X) then
3.         for j <-- 1 to n do write(X[j],' ')
4.   else
5.      for j <-- i to n do
6.         Swap(X[i],X[j]); Perm(i+1);
7.         Swap(X[j],X[i])

Η επόμενη διαδικασία Queens2 αρχικά δίνει την τιμή (1,2,3,4,5,6,7,8) στο διάνυσμα X και καλώντας τη διαδικασία Perm(1) βρίσκει τις διαφορετικές διατάξεις του διανύσματος, τυπώνοντας αυτές που αποτελούν λύση στο πρόβλημα.

     procedure Queens2;
1.   for i <-- 1 to 8 do X[i] <-- i;
2.   Perm(1)

Όπως αναφέρθηκε, ο αριθμός των δυνατών καταστάσεων είναι 40.320, αλλά η πρώτη λύση θα δοθεί μετά από 2.830 δοκιμές. Όμως πέρα από το γεγονός ότι οι λύσεις θα βρεθούν με πολύ λιγότερες δοκιμές σε σύγκριση με τη διαδικασία Queens1, η μέθοδος είναι ταχύτερη, γιατί δεν χρειάζεται η συνάρτηση Place1 να εκτελεί ελέγχους σε σχέση με τις στήλες αλλά μόνο ως προς τις διαγώνιους. Η νέα εκδοχή της συνάρτησης αυτής, Place2, παρουσιάζεται στη συνέχεια.

     function Place2(k);
1.   j <-- 1; flag <-- true;
2.   while (j<k-1) and (flag=true) do
3.      if (abs(X[i]-X[k])<>abs(i-k)) then j <-- j+1
4.      else flag <-- false;
5.   return flag

Τέλος, το πρόβλημα των 8 βασιλισσών μπορεί να αντιμετωπιστεί με τη μέθοδο της Οπισθοδρόμησης, σύμφωνα με την οποία αφού τοποθετηθεί μία βασίλισσα, στη συνέχεια ελέγχεται αν υπάρχει επιτρεπτή θέση, για να τοποθετηθεί η επόμενη. Αν βρεθεί τέτοια θέση, τότε ο αλγόριθμος διαχειρίζεται την τοποθέτηση της επόμενης βασίλισσας, διαφορετικά επιστρέφει (δηλαδή, οπισθοδρομεί) στην πιο πρόσφατα τοποθετημένη και την τοποθετεί στη επόμενη δυνατή θέση σε σχέση με αυτή όπου είχε τοποθετηθεί προηγουμένως. Αν τέτοια θέση δεν υπάρχει, τότε γίνεται οπισθοδρόμηση στην αμέσως προηγούμενη κοκ.

Η διαδικασία που υλοποιεί αυτόν τον τρόπο επίλυσης είναι η Queens3. Αυτή χρησιμοποιεί τη συνάρτηση Place1(k), που περιγράφηκε προηγουμένως, για να καθορίσει αν η $k$-οστή βασίλισσα μπορεί να τοποθετηθεί στη στήλη $X(k)$. Η κλήση της Queens3(8) δίνει τη λύση του προβλήματος. Ένα παράδειγμα επίλυσης του προβλήματος των 4 βασιλισσών απεικονίζεται στο Σχήμα 6.9.

     procedure Queens3 (n);
1.   X[1] <-- 0; k <-- 1;
2.   while k>0 do
3.      X[k] <-- X[k]+1;
4.      while (X[k]<=n) and (not place(k)) do
5.         X[k] <-- X[k]+1;
6.      if X[k]<=n then
7.         if k=n then
8.            for i <-- 1 to n do write(X[i],' ')
9.         else
10.           k <-- k+1; X[k] <-- 0
11.     else k <-- k-1 {* backtracking *}

Ο τελευταίος τρόπος επίλυσης μπορεί να βελτιωθεί ακόμη περισσότερο, αν το πλήθος των καταστάσεων του προβλήματος οργανωθεί σε μορφή δένδρου. Σε κάθε επίπεδο του δένδρου από τη ρίζα μέχρι τα φύλλα, οι κόμβοι περιγράφουν μία νόμιμη κατάσταση με 0, 1, 2, κτλ. βασίλισσες τοποθετημένες, ώστε να μην αλληλο-απειλούνται. Όλα τα κλαδιά ($v,u$) του δένδρου είναι τέτοια, ώστε στον κόμβο $v$ να περιγράφεται μία κατάσταση για $k$ βασίλισσες, ενώ στο κόμβο $u$ να περιγράφεται μία κατάσταση με $k+1$ βασίλισσες, η οποία προκύπτει από την προηγούμενη με την προσθήκη μίας επιπλέον βασίλισσας σε επιτρεπτή θέση. Τμήμα του δένδρου αυτού φαίνεται στο επόμενο σχήμα. Παρατηρούμε ότι η ρίζα απεικονίζει την κατάσταση ενός διανύσματος με 0 βασίλισσες και έχει οκτώ παιδιά. Ωστόσο, το πρώτο παιδί έχει μόνον έξι παιδιά καθώς δεν θα ήταν νόμιμη μία κατάσταση με μία βασίλισσα στις θέσεις 2,1 ή 2,2, δεδομένου ότι ήδη υπάρχει μία βασίλισσα στη θέση 1,1. Επεκτείνοντας αυτό το δένδρο προς τα φύλλα, είτε φθάνουμε σε καταστάσεις που οδηγούν σε αδιέξοδο και σταματούμε τις περαιτέρω τοποθετήσεις βασιλισσών, είτε οδηγούμαστε στη λύση.

Αυτή η μέθοδος έχει δύο πλεονεκτήματα σε σχέση με τις προηγούμενες. Το πρώτο είναι ότι μειώνει το πλήθος των καταστάσεων, όπου αναζητούνται οι λύσεις του προβλήματος, αφού οι κόμβοι του δένδρου είναι λιγότεροι από 8!=40.320. Για την ακρίβεια, αν με τη βοήθεια του προγράμματος μετρήσουμε τους κόμβους του δένδρου, τότε θα βρούμε ότι είναι μόνο 2057, ενώ η πρώτη λύση θα βρεθεί μετά την εξέταση 114 κόμβων. Το δεύτερο είναι, ότι για να εξετασθεί αν ένας κόμβος του δένδρου, που εκφράζει ένα διάνυσμα μήκους $k$, αντιπροσωπεύει μία νόμιμη κατάσταση, δεν είναι απαραίτητο να ελεγχθούν όλα τα δυνατά ζεύγη μεταξύ των $k$ βασιλισσών, αλλά αρκεί να ελεγχθεί αν η $k$-οστή βασίλισσα απειλεί τις προηγούμενες. Αυτός ο έλεγχος μπορεί να γίνει πολύ αποτελεσματικά αν σε κάθε κόμβο αποθηκεύουμε τις διαγωνίους (και των δύο κατευθύνσεων) που ελέγχονται από τις ήδη τοποθετημένες βασίλισσες. Τις διαγωνίους που έχουν κατεύθυνση από κάτω αριστερά προς επάνω δεξιά τις συμβολίζουμε με d45, ενώ με d135 συμβολίζουμε τις διαγωνίους της άλλης κατεύθυνσης. Για να καταλάβουμε την αποτελεσματικότητα αυτής της τεχνικής, αρκεί να σκεφθούμε ότι στις προηγούμενες μεθόδους για να ελέγξουμε αν μία κατάσταση από 8 τοποθετημένες βασίλισσες είναι νόμιμη πρέπει να εκτελέσουμε 28 ελέγχους, στη χειρότερη περίπτωση.

Στη συνέχεια, δίνεται η διαδικασία Queens4 που κωδικοποιεί την τελευταία μέθοδο. Η λύση του προβλήματος λαμβάνεται δίνοντας την κλήση Queens4 ((0,0,0,0,0,0,0,0),0,col,d45,d135) . Προϋποτίθεται ότι οι μεταβλητές col,d45,d135 είναι τύπου συνόλου (πχ. SET of 1..15 στην Pascal).

     procedure Queens4(X; k; col,d45,d135);
1.   if k=8 then
2.      for j <-- 1 to 8 do write(X[j],' ')
2.   else
3.      for j <-- 1 to 8 do
5.         t1 <-- j-k; t2 <-- j+k;
6.         if not (j in col) and not (t1 in d45) and
7.               not (t2 in d135) then
8.            col <-- col+[j]; d135 <-- d135+[t2];
8.            d45 <-- d45+[t1]; X[k+1] <-- j;
9.            Queens4(X,k+1,col,d45,d135)

Στην προηγούμενη ανάπτυξη των λύσεων του προβλήματος των 8 βασιλισσών δεν έγινε αναφορά στην πολυπλοκότητα των αντίστοιχων μεθόδων. Αν γενικεύσουμε το πρόβλημα και θεωρήσουμε ότι πρέπει να τοποθετηθούν $n$ βασίλισσες σε σκακιέρα $n\times n$ χωρίς να αλληλο-απειλούνται, τότε σε σχέση με την πολυπλοκότητα αναφέρονται συνοπτικά τα εξής: Η μη αναπτυχθείσα μέθοδος που αναφέρθηκε στην εισαγωγή έχει πολυπλοκότητα της τάξης $\left(\begin{array}{c}{n}^2\\ n\end{array}\right)$, άρα πολυπλοκότητα Θ($n^n$). Η πρώτη εξαντλητική μέθοδος έχει πολυπλοκότητα Θ($n^n$), ενώ η δεύτερη εξαντλητική μέθοδος έχει πολυπλοκότητα $\mathrm{\Theta }(n!)=\mathrm{\Theta }(n^n)$. Με απλά λόγια, όλες έχουν την ίδια δραματική πολυπλοκότητα, με διαφορετικό βέβαια σταθερό συντελεστή. Οι δύο τελευταίες μέθοδοι διακρίνονται από εκθετική πολυπλοκότητα.

Ο άπληστος αλγόριθμος κάθε φορά επιλέγει από τον πίνακα κόστους $C$ την ακμή εκείνη $(i,j)$ που έχει την ελάχιστη τιμή, από όλες όσες δεν έχουν μέχρι στιγμής εξετασθεί και την προσθέτει στο ήδη σχηματισμένο μονοπάτι, αν:

• •

  δεν υπάρχει στο ήδη σχηματισμένο μονοπάτι άλλη ακμή που να ξεκινά από τον κόμβο $i$ ή να καταλήγει στον κόμβο $j$, και

• •

  με την προσθήκη της ακμής ($i,j$) δεν σχηματίζεται κύκλος (εκτός αν είναι η ακμή εκείνη, που με την προσθήκη της σχηματίζεται ο κύκλος που περνά από όλους τους κόμβους του γράφου, δηλαδή ο κύκλος που είναι λύση του προβλήματος).

Με βάση τα προηγούμενα προκύπτει ότι αρχικά πρέπει να έχουμε τις ακμές οργανωμένες, έτσι ώστε να βρίσκουμε εύκολα την ακμή με ελάχιστη τιμή κόστους. Αυτό σημαίνει ότι οι ακμές πρέπει να αποθηκευθούν σε ένα σωρό. Σε μία τέτοια περίπτωση, η εύρεση της κατάλληλης ακμής επιτυγχάνεται με τη βοήθεια της DeleteHeap, που επιστρέφει τα άκρα της ακμής ($i,j$) με το ελάχιστο κόστος, το οποίο ονομάζουμε min.

Οι ακμές που έχουν ήδη προστεθεί στο κύκλο, αποθηκεύονται σε μία λίστα που ορίζεται ως ολική μεταβλητή, την ονομάζουμε Current_Path και είναι τύπου δείκτη Path_Edge που δείχνει προς τη μεταβλητή edge τύπου εγγραφής. Σε κάθε κόμβο, δηλαδή, αποθηκεύεται μία ακμή ($i,j$), ενώ ο δείκτης next δείχνει στον επόμενο κόμβο της λίστας. Για να προστεθεί μία ακμή ($i,j$) στο μονοπάτι που έχει αναπτυχθεί μέχρι στιγμής, πρέπει να μην υπάρχει στο μονοπάτι αυτό (και επομένως στη λίστα Current_Path) άλλη ακμή της μορφής ($i,k$) ή ($k,j$). Αυτό συμβαίνει γιατί σε κάθε κύκλο υπάρχει για κάθε κόμβο μία ακμή που καταλήγει σ’ αυτόν και μία που ξεκινά από αυτόν. Έτσι, σαρώνονται όλα τα στοιχεία της λίστας και αν βρεθούν ακμές αυτής της μορφής, τότε η προσθήκη της νέας ακμής απορρίπτεται. Αυτή τη διαδικασία ακολουθεί η λογική συνάρτηση Third_Edge(i,j) που επιστρέφει true αν η ακμή ($i,j$) αποτελεί την τρίτη ακμή που προσπίπτει στον κόμβο $i$ ή $j$, οπότε και απορρίπτεται η εισαγωγή της στο μονοπάτι.

     function Third_Εdge(u,v);
1.   new(p); p <-- Current_Path;
2.   counter1 <-- 0; counter2 <-- 0;
3.   while (p<>nil) and (count1<=1) and (count2<=1) do
4.      if p.i=u then count1 <-- count1+1;
5.      if p.j=v then count2 <-- count2+1;
6.      p <-- p.next
7.   if (count1>=1) or (count2>=1) then return true
8.   else return false

Αν η συνάρτηση Third_Edge(i,j) επιστρέψει false, τότε πρέπει να γίνει έλεγχος για το σχηματισμό κύκλου, πριν προστεθεί η ακμή ($i,j$) στο μονοπάτι. Κύκλος σχηματίζεται, όταν υπάρχουν ακμές $(j,k_1),(k_1,k_2),\mathrm{\dots },(k_p,i)$ που να ανήκουν όλες στο μονοπάτι. Αν ο κύκλος αυτός περιέχει όλους τους κόμβους του γράφου, τότε αποτελεί λύση του προβλήματος, αλλιώς απορρίπτεται η εισαγωγή της ακμής ($i,j$).

Η συνάρτηση Find_Next_Node(v) επιστρέφει έναν κόμβο $k$, αν η ακμή ($v,k$) ανήκει στο μονοπάτι. Αν δεν υπάρχει τέτοια ακμή, τότε επιστρέφει μηδέν, που σημαίνει ότι στην περίπτωση αυτή δεν σχηματίζεται κύκλος και επομένως η ακμή ($i,j$) μπορεί να εισαχθεί στο μονοπάτι.

     function Find_Next_Node(u);
1.   new(p); p <-- Current_Path;
2.   while (p.next<>nil) and (p.i<>u) do p <-- p.next;
3.   if p.i=u then return p.j else return 0

Η λογική συνάρτηση Cycle(i,j) χρησιμοποιεί τη συνάρτηση Find_Next_ Node και από τον κόμβο $j$ αναπτύσσει το μεγαλύτερο μονοπάτι που μπορεί να αναπτυχθεί, έτσι ώστε όλες οι ακμές του να περιέχονται στο Current_Path. Έστω ότι το μονοπάτι αυτό είναι το $(j,k_1,k_2,\mathrm{\dots },k_p)$. Aν $k_p=i$, τότε σχηματίζεται κύκλος, οπότε αν οι κόμβοι $j,k_1,k_2,\mathrm{\dots },k_p$ είναι ακριβώς οι κόμβοι του γράφου, τότε το μονοπάτι αυτό είναι η λύση του προβλήματος. Αν όμως οι κόμβοι $j,k_1,k_2,\mathrm{\dots },k_p$ είναι λιγότεροι από τους κόμβους του γράφου, τότε αυτό σημαίνει ότι σχηματίζεται κύκλος που δεν αποτελεί λύση. Έτσι, η συνάρτηση Cycle επιστρέφει true απορρίπτοντας την εισαγωγή της ακμής ($i,j$) στο Current_Path. Αν δεν ισχύει $k_p=i$ και δεν υπάρχει κόμβος $k_{p+1}$ τέτοιος ώστε η ακμή ($k_p,k_{p+1}$) να περιέχεται στο Current_Path, δηλαδή η κλήση της συνάρτησης Find_Next_Node(kp) επιστρέφει μηδέν, τότε δεν σχηματίζεται κύκλος με την εισαγωγή της ($i,j$) και η Cycle(i,j) επιστρέφει false.

     function Cycle(u,v);
1.   s <-- [u,v]; a <-- Find_Next_Node(v);
2.   while (a<>0) and (a<>u) do
4.      s <-- s+[a]; a <-- Find_Next_Node(a)
6.   if (a=0) then return false
7.   else if (a=u) and (Include_all(s)) then
9.      cycle <-- false; solution <-- true
11.  else return true;

Η συνάρτηση Cycle καλεί τη λογική συνάρτηση Include_all, που σκοπό έχει να ελέγξει αν στο μονοπάτι περιλαμβάνονται όλες οι κορυφές του γράφου και δίνεται στη συνέχεια. Επίσης, η μεταβλητή s είναι τύπου set, ενώ η λογική μεταβλητή solution είναι καθολική και θα φανεί η χρήση της μέσα στο κύριο πρόγραμμα.

     function Include_all(s);
1.   Include_all <-- true;
2.   while (Include_all=true) and i<=n do
3.      if (not (i in s)) then Include_all <-- false;
4.      i <-- i+1

Επομένως, η συνολική διαδικασία που ακολουθείται είναι: όσο δεν έχει βρεθεί λύση, επιλέγεται η ακμή με το μικρότερο κόστος μεταξύ αυτών που δεν έχουν εξετασθεί ως τώρα, γίνονται οι δύο έλεγχοι και ανάλογα, είτε γίνεται η εισαγωγή της ακμής στο Current_Path είτε απορρίπτεται. Στη συνέχεια, ακολουθεί το κύριο πρόγραμμα που δένει όλες τις προηγούμενες συναρτήσεις. Getfile είναι η συνάρτηση που διαβάζει το γράφο εισόδου, ο οποίος αναπαρίσταται με τη μέθοδο του πίνακα γειτνίασης.

1.   Getfile; new(Current_Path); Current_Path <-- nil;
2.   lenght <-- 0; solution <-- false;
3.   while (not solution) do
4.      DeleteHeap(i,j,min);
5.      if not(Third_edge(i,j) and Cycle(i,j)) then
6.         new(p); p.i <-- i; p.j <-- j;
7.         p.next <-- Current_Path;
8.         Current_Path <-- p; length <-- length+min;
9.         if solution=true then
10.           new(p); p <-- Current_Path;
11.           while p<>nil do
12.              writeln(p.i,'  ',p.j); p <-- p.next
13.           writeln('Συνολικό κόστος ',length)

Ας θεωρήσουμε το γράφο του Σχήματος 6.11. Για την επίλυση του TSP για το γράφο αυτό, ο άπληστος αλγόριθμος ακολουθεί την εξής διαδικασία: Η ακμή με το ελάχιστο κόστος είναι η (2,1) με κόστος 5, που είναι η πρώτη ακμή που εισάγεται στο Current_Path. Από αυτές που απομένουν, η ακμή με ελάχιστο κόστος είναι η (3,1), που όμως δεν εισάγεται στο μονοπάτι, γιατί ήδη σε αυτό υπάρχει η (2,1). Για τον ίδιο λόγο απορρίπτεται και η (4,1). Στον Πίνακα 6.3 παρουσιάζονται διάφορα στοιχεία καθώς ο αλγόριθμος εξελίσσεται.

Ο κύκλος που σχηματίζεται αποτελείται από τις ακμές (2,1), (4,2), (3,4) και (1,3), είναι ο (1,3,4,2,1) και έχει μήκος 40. Παρατηρείται ότι ο κύκλος (1,2,4,3,1) έχει μήκος 35. Επομένως ο αλγόριθμος αυτός δεν δίνει πάντα τη βέλτιστη λύση. Γι’αυτόν το λόγο κατατάσσεται στην κατηγορία των προσεγγιστικών ευριστικών άπληστων αλγορίθμων. Ωστόσο, ο αλγόριθμος αυτός είναι χρήσιμος γιατί είναι σχετικά γρήγορος σε σχέση με αυτούς που θα εξετασθούν στη συνέχεια. Πιο συγκεκριμένα, η συνάρτηση DeleteHeap είναι τάξης Ο($\lg n$), οι συναρτήσεις Third_Edge, Find_Next_Node και Include_All είναι γραμμικές, ενώ η συνάρτηση Cycle είναι τετραγωνικής τάξης. Το τελευταίο προκύπτει από την πράξη βαρόμετρο while p<>nil do. Τελικά, η πολυπλοκότητα της μεθόδου αυτής είναι τάξης Ο($n^2$). Η επόμενη λύση δίνει πράγματι τον κύκλο με το μικρότερο κόστος.

Σύμφωνα με τις αρχές του Δυναμικού Προγραμματισμού, τις οποίες γνωρίζουμε από τη Σχεδίαση Αλγορίθμων, το TSP μπορεί να λυθεί κάνοντας χρήση της συνάρτησης:

$$g(i,S)=\underset{j\in S}{\min }(C_{ij}+g(j,S-\{j\}))$$

(6.2)

όπου το $S$ είναι σύνολο κόμβων. Η συνάρτηση $g(i,S)$ επιστρέφει το κόστος του συντομότερου μονοπατιού που ξεκινά από τον κόμβο $i$, περνά ακριβώς μία φορά από όλους τους κόμβους του συνόλου $S$ και καταλήγει στον κόμβο 1, που χωρίς απώλεια της γενικότητας μπορεί να θεωρηθεί ότι ο κύκλος ξεκινά από αυτόν και σε αυτόν καταλήγει. Η συνάρτηση αυτή μπορεί να υλοποιηθεί αναδρομικά ως εξής.

     function g(i,s);
1.   cost <-- maxint;
2.   if s=[] then g <-- C[i,1]
3.   else
4.      for j <-- 2 to n do
5.         if j in s then
6.            k <-- C[i,j]+g(j,s-[j]);
7.            if k<cost then cost <-- k;
8.            g <-- cost

Αν δεν ζητείται μόνο το κόστος της συντομότερης διαδρομής, αλλά και αυτή η ίδια η διαδρομή, τότε πρέπει να ορισθεί μία συνάρτηση $J$, τέτοια ώστε το $J(i,S)$ να ισούται με τον κόμβο $j$ που ελαχιστοποιεί το άθροισμα $C_{ij}+g(j,S-\{j\})$.

Ορίζεται μία λίστα Next_Node του τύπου List_Next_Node, που είναι ένας δείκτης προς μεταβλητές τύπου element, που με τη σειρά του είναι τύπου εγγραφής με τα πεδία node, s, node_min_cost, next. Σε κάθε στοιχείο της λίστας αυτής αποθηκεύονται ο κόμβος $j$ (που ελαχιστοποιεί το κόστος $g(i,S)$) ως τιμή του πεδίου node_min_cost, ο κόμβος $i$ ως τιμή του πεδίου node καθώς επίσης και το σύνολο S.

Για να μην υπολογίζεται μόνο το κόστος του μονοπατιού, αλλά να προσδιορίζεται και το ίδιο το μονοπάτι που έχει ελάχιστο κόστος, χρησιμοποιείται μία παραλλαγή της συνάρτησης g που περιγράφτηκε προηγουμένως. Σύμφωνα με τη νέα παραλλαγή κάθε φορά που βρίσκεται ένας κόμβος $j$ που ελαχιστοποιεί το κόστος $C_{ij}+g(j,S-\{j\})$, προστίθεται στη λίστα Next_Node ένας κόμβος με πεδία που έχουν αντίστοιχα τις τιμές $i,S,j$. Αν όμως υπάρχει ήδη στη λίστα κόμβος με τιμές στα δύο πρώτα πεδία τις τιμές $i$ και $S$, τότε ενημερώνεται η τιμή του τρίτου πεδίου και γίνεται $j$.

     function g(i,s);
1.   cost <-- maxint;
2.   if s=[] then g <-- C[i,1]
3.   else
4.      for j <-- 2 to n do if j in s then
5.         k <-- C[i,j]+g(j,s-[j]);
6.         if k<cost then
7.            cost <-- k;
8.            if not exist_in_path(i,s,j) then
9.               new(p); p.node <-- i; p.s <-- s;
10.              next_node <-- p; p.node_min_cost <-- j;
11.              p.next <-- next_node
12.        g <-- cost

Μετά την κλήση της συνάρτησης αυτής έχει υπολογισθεί το κόστος του συντομότερου κύκλου και έχουν βρεθεί οι τιμές των κόμβων $j$ που ελαχιστοποιούν τα αθροίσματα $C_{ij}+g(j,S-\{j\})$ για κάθε κόμβο $i$ του γράφου και για κάθε σύνολο κόμβων $S$. Ο συντομότερος κύκλος είναι $(1,J(1,\{\mathrm{2..}N\}),J(J(1,\{\mathrm{2..}N\})$, $\{\mathrm{2..}N\}-J(1,\{\mathrm{2..}N\})),\mathrm{\dots },1)$. Για να βρεθεί, γίνεται αναζήτηση στους κόμβους της λίστας Next_Node, όπως φαίνεται από τον κώδικα της διαδικασίας Search(i,S) που ακολουθεί.

     procedure Search(i,s);
1.   new(p); p <-- next_node;
2.   while ((p.next<>nil) and ((p.node<>i) or (p.s<>s)))
3.      do p <-- p.next;
4.   if (p.node=i) and (p.s=s) then
5.      write(p.node_min_cost,' ');
6.      Search(p.node_min_cost,s-[p.node_min_cost]);

Για το γράφο του προηγούμενου σχήματος, οι τιμές της συνάρτησης J παρουσιάζονται στον Πίνακα 6.4, οπότε ο συντομότερος κύκλος που βρίσκει ο αλγόριθμος είναι (1,2,4,3,1) με κόστος 35.

Επιλογικά, στη βιβλιογραφία αναφέρονται και άλλες επακριβείς λύσεις που στηρίζονται στη μέθοδο της οπισθοδρόμησης και στη μέθοδο της διακλάδωσης και του περιορισμού. Το γεγονός είναι ότι το TSP είναι ένα κλασικό NP-complete πρόβλημα και επομένως δεν μπορεί κανείς να είναι αισιόδοξος ότι θα βρει αποδοτικούς αλγορίθμους για μία γενική λύση του. Οι τεχνικές που περιγράψαμε εδώ δίνουν μία αρκετά ικανοποιητική προσεγγιστική λύση για μικρές (σχετικά) τιμές. Επειδή το πρόβλημα έχει πολλές πρακτικές εφαρμογές, έχει απασχολήσει πολλούς ερευνητές σε μία προσπάθεια να πετύχουν λύσεις σε όλο και μεγαλύτερα στιγμιότυπα του προβλήματος. Το 1954 οι Dantzig, Fulkerson και Johnson έλυσαν το πρόβλημα για 42 πόλεις των ΗΠΑ, ενώ το 1980 οι Padberg και Hong το έλυσαν για 318 πόλεις. Το 1992 οι Applegate, Bixby, Cook από το Πανεπιστήμιο Rice, και ο Chvatal από το Πανεπιστήμιο Rutgers βρήκαν τη βέλτιστη διαδρομή για 3.038 πόλεις των ΗΠΑ, χρησιμοποιώντας ένα σύστημα από 50 σταθμούς εργασίας. Το 1993 ανέβασαν τον αριθμό των πόλεων σε 4.461 πόλεις, ενώ το 1994 ανέβασαν τον αριθμό αυτό σε 7.397 πόλεις. Αυτό το ρεκόρ είχε μείνει ακατάρριπτο μέχρι το 1998. Με τη βοήθεια 3 ισχυρών μηχανών (Digital AlphaServer 4100 με 12 επεξεργαστές) και ένα σύνολο από 12 προσωπικούς υπολογιστές Pentium II, οι οποίοι έτρεχαν το πρόγραμμα για περίπου 3 μήνες, οι τέσσερις ερευνητές πέτυχαν να δώσουν λύση στο πρόβλημα για τις 13.509 πόλεις των ΗΠΑ με πληθυσμό περισσότερο από 500 κατοίκους.