Χρωματισμός Χάρτη

Άσκηση 1
Ας υποθέσουμε ότι σας δίνεται ένας χάρτης, ο οποίος χωρίζεται σε διαφορετικές περιοχές όπως η επόμενη εικόνα.

Χάρτης Περιοχών
Χάρτης Περιοχών

Στόχος μας είναι ο χρωματισμός των περιοχών του χάρτη με 4 διαφορετικά χρώματα έτσι ώστε γειτονικές περιοχές να έχουν διαφορετικό χρωματισμό. Έτσι, ο παραπάνω χάρτης πρέπει να έχει, για παράδειγμα, την επόμενη μορφή.

Χρωματισμένος Χάρτης
Χρωματισμένος Χάρτης

Να γίνει αλγόριθμος που να εκτελεί την παραπάνω εργασία. Συγκεκριμένα θα δέχεται ως δεδομένα έναν πίνακα Χ[4] με τα τέσσερα χρώματα που θέλουμε να χρωματίσουμε τον χάρτη, κι έναν πίνακα Γ ΝxN, με λογικές τιμές οι οποίες θα δείχνουν αν δυο περιοχές του χάρτη είναι γειτονικές. Δηλαδή, όταν Γ[i,j] είναι αληθής τότε η περιοχή i με την περιοχή j είναι γειτονικές. Όταν δεν είναι τότε είναι ψευδής. Σε περίπτωση αποτυχίας χρωματισμού με τέσσερα μόνο χρώματα να τυπώνεται κατατοπιστικό μήνυμα.

Αλγόριθμος Χρωματισμός_Χάρτη
Δεδομένα // Χ, Γ, N //
 
!Χ είναι ένας πίνακας 4 θέσεων στον οποίο καταχωρούνται τα χρώματα π.χ. Χ[1] <- ‘Κόκκινο’ κ.ο.κ
!Γ είναι ένας δισδιάστατος πίνακας NxN στον οποίο καταχωρούνται λογικές τιμές σχετικά με το αν δύο περιοχές είναι γειτονικές.
!N είναι ο αριθμός των περιοχών
!ΧΠ είναι ο πίνακας που καταχωρεί το χρώμα κάθε περιοχής.
 
!Αρχικά καμία περιοχή δεν είναι χρωματισμένη.
Για i από 1 μέχρι Ν
  	ΧΠ[i] <- 0
Τέλος_επανάληψης
 
Για i από 1 μέχρι Ν
	Για k από 1 μέχρι 4
		!Υποψήφιο χρώμα για την περιοχή
		ΥΧΠ[k] <- ΑΛΗΘΗΣ
	Τέλος_επανάληψης
 
	Για j από 1 μέχρι Ν
		Αν (i <> j) ΚΑΙ Γ[i, j] = ΑΛΗΘΗΣ ΚΑΙ ΧΠ[j] <> 0 τότε
			ΥΧΠ[ΧΠ[j]] <- ΨΕΥΔΗΣ
		Τέλος_αν
	Τέλος_επανάληψης
 
	βρέθηκε <- ΨΕΥΔΗΣ
	k <- 1
	Όσο k <= 4 KAI βρέθηκε = ΨΕΥΔΗΣ επανάλαβε
		Αν ΥΧΠ[k] = ΑΛΗΘΗΣ τότε
			ΧΠ[i] <- k
			βρέθηκε <- ΑΛΗΘΗΣ
			Εμφάνισε "Στην περιοχή ", i, "τοποθετήθηκε το χρώμα ", Χ[k]
		Αλλιώς
			k <- k + 1
		Τέλος_αν
	Τέλος_επανάληψης
 
	Αν (ΟΧΙ(βρέθηκε)) τότε
		Εμφάνισε "Αδυναμία καταχώρησης χρώματος στην περιοχή ", i
	Τέλος_αν
 
Τέλος_επανάληψης
Τέλος Χρωματισμός_Χάρτη

Αφήστε μια απάντηση

Η ηλ. διεύθυνσή σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *