Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Πώς μοιάζει η υποκείμενη δομή δεδομένων ArrayList;

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

Ο μηχανισμός επέκτασης ArrayList είναι: όταν προστίθεται το πρώτο στοιχείο, η χωρητικότητα του ArrayList είναι 10 κάθε φορά που προστίθεται ένα νέο στοιχείο, εάν η χωρητικότητα ξεπεραστεί, η αρχική χωρητικότητα θα διπλασιαστεί, δηλαδή η αρχική χωρητικότητα * 2. , εάν η αρχική χωρητικότητα είναι 0, τότε η νέα χωρητικότητα είναι 1.

Πλεονεκτήματα και μειονεκτήματα του μηχανισμού επέκτασης ArrayList:

πλεονέκτημα:

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

έλλειψη:

1. Ο μηχανισμός επέκτασης ArrayList οδηγεί σε σπατάλη μνήμης και μπορεί εύκολα να προκαλέσει σπατάλη χώρου μνήμης.
2. Όταν η χωρητικότητα είναι μεγάλη, κάθε επέκταση απαιτεί μεγάλη ποσότητα μνήμης και πόρων CPU, κάτι που θα επηρεάσει την απόδοση, επομένως, όταν χρησιμοποιείτε το ArrayList, η αρχική χωρητικότητα πρέπει να ρυθμιστεί κατάλληλα.

Το ArrayList δεν είναι ασφαλές για νήματα

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

Οι συνήθεις μέθοδοι για την επίλυση της ανασφάλειας νημάτων ArrayList περιλαμβάνουν:

1. Χρησιμοποιήστε το Vector αντί για ArrayList: Το Vector συγχρονίζεται και όλες οι μέθοδοι τροποποιούνται με συγχρονισμό, επομένως είναι ασφαλές για νήματα.
2. Αναδίπλωση του ArrayList σε ασφάλεια νημάτων: Χρησιμοποιήστε τη μέθοδο Collections.synchronizedList(list) για να μετατρέψετε το ArrayList σε ασφάλεια νημάτων.
3. Χρησιμοποιήστε το CopyOnWriteList: Είναι μια συλλογή που είναι ασφαλής για το νήμα και υλοποιείται με την αντιγραφή του υποκείμενου πίνακα.
4. Χρησιμοποιήστε κλειδαριές για να επιτύχετε ασφάλεια νημάτων: Μπορείτε να χρησιμοποιήσετε μηχανισμούς κλειδώματος όπως το ReentrantLock για να εφαρμόσετε μια ArrayList ασφαλή για νήματα.

Η διαφορά μεταξύ στοίβας και σωρού

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

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

Κάτω στρώμα κορουτίνας

Η ουσία μιας κορουτίνας είναι μια ελαφριά κλωστή.

Αρχή C# GC (συλλογή σκουπιδιών).

1. Καταμέτρηση αναφοράς: Όταν γίνεται αναφορά σε ένα αντικείμενο, το πλήθος αναφοράς του αυξάνεται κατά 1. Όταν η αναφορά καθίσταται άκυρη, ο αριθμός αναφοράς του μειώνεται κατά 1. Εάν ο αριθμός αναφοράς ενός αντικειμένου γίνει 0, το αντικείμενο θα ανακτηθεί από τον συλλέκτη σκουπιδιών.
2. Mark-and-clear: Όταν ο συλλέκτης σκουπιδιών λειτουργεί, διασχίζει αντικείμενα σύμφωνα με σχέσεις αναφοράς, επισημαίνει προσβάσιμα αντικείμενα ως "ζωντανά", επισημαίνει μη προσβάσιμα αντικείμενα ως "νεκρά" και, στη συνέχεια, καθαρίζει όλα τα αντικείμενα που επισημαίνονται ως "νεκρά" .
3. Αλγόριθμος αντιγραφής: Ο συλλέκτης σκουπιδιών διαιρεί τη διαθέσιμη μνήμη σε δύο μπλοκ και χρησιμοποιεί μόνο ένα μπλοκ κάθε φορά, όταν ο χώρος είναι ανεπαρκής, τα σωζόμενα αντικείμενα αντιγράφονται σε άλλο μπλοκ χώρου και στη συνέχεια τα αντιγραμμένα αντικείμενα διαγράφονται από το πρωτότυπο. χώρος.
4. Αλγόριθμος συμπλήρωσης σήμανσης: Όταν ο συλλέκτης απορριμμάτων λειτουργεί, πρώτα θα σημαδέψει όλα τα σωζόμενα αντικείμενα και στη συνέχεια θα μετακινήσει όλα τα σωζόμενα αντικείμενα στο ένα άκρο για να καθαρίσει τα αχρησιμοποίητα θραύσματα χώρου.

Η διαφορά μεταξύ συγχρονισμού κατάστασης και συγχρονισμού καρέ

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

Συγχρονισμός καρέ Σημαίνει ότι σε κάθε κύκλο ελέγχου, οι εντολές ελέγχου κάθε μηχανής στο σύστημα πολλαπλών μηχανών μεταδίδονται σε άλλες μηχανές, έτσι ώστε κάθε μηχανή να παραμένει συγχρονισμένη. Ο συγχρονισμός πλαισίου μπορεί να επιτύχει την ακρίβεια του συνεργατικού ελέγχου πολλών μηχανών, αλλά επειδή μόνο ένας μικρός αριθμός εντολών ελέγχου μεταδίδεται σε κάθε κύκλο ελέγχου, η απόδοσή του σε πραγματικό χρόνο μπορεί να είναι σχετικά χαμηλή.

Κοινά σχέδια σχεδίασης

Μοτίβο Singleton

Μοτίβο εργοστασίου

Σύνθετο Μοτίβο

Μοτίβο διακομιστή μεσολάβησης

Χαρακτηριστικά συνδεδεμένων λιστών, δυαδικών δέντρων και πινάκων κατακερματισμού

1. Συνδεδεμένη λίστα:

• Είναι μια δομή γραμμικής λίστας, η οποία χαρακτηρίζεται από το ότι κάθε κόμβος έχει έναν δείκτη που δείχνει στον επόμενο κόμβο, σχηματίζοντας έτσι μια συνδεδεμένη λίστα.
• Ανεξάρτητα από την εισαγωγή ή τη διαγραφή ενός κόμβου, χρειάζεται μόνο να αλλάξετε την κατάδειξη του δείκτη και η χρονική πολυπλοκότητα είναι O(1).
• Η χρονική πολυπλοκότητα της εύρεσης ενός κόμβου είναι O(n), και πρέπει να κάνετε αναζήτηση με τη σειρά ξεκινώντας από τον κύριο κόμβο.
• Οι συνδεδεμένες λίστες δεν χρειάζεται να εξετάζουν ζητήματα κατανομής χώρου Γενικά, η δυναμική κατανομή μνήμης χρησιμοποιείται για την επίτευξη ευέλικτης διαχείρισης μνήμης.

2. Δυαδικό δέντρο:

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

3. Πίνακας κατακερματισμού:

• Ένας πίνακας κατακερματισμού είναι μια δομή δεδομένων που αντιστοιχίζει ένα κλειδί σε μια τοποθεσία σε έναν πίνακα για πρόσβαση σε εγγραφές για επιτάχυνση των αναζητήσεων.
• Η πολυπλοκότητα χρόνου αναζήτησης του πίνακα κατακερματισμού είναι O(1) και η πολυπλοκότητα χρόνου εισαγωγής και διαγραφής είναι O(n).
• Η υλοποίηση ενός πίνακα κατακερματισμού απαιτεί επιπλέον χώρο για την αποθήκευση του ίδιου του πίνακα κατακερματισμού και το πρόβλημα των συγκρούσεων κατακερματισμού πρέπει να επιλυθεί.

Η βασική αρχή του HashMap

Το κάτω επίπεδο του HashMap υλοποιείται χρησιμοποιώντας μια λίστα συνδεδεμένη με πίνακα (κόκκινο-μαύρο δέντρο). κώδικα και χρησιμοποιεί μια συνδεδεμένη λίστα (κόκκινο-μαύρο δέντρο) για την αποθήκευση των διενέξεων. HashMap Στην Java 8, όταν το μήκος της συνδεδεμένης λίστας υπερβαίνει το όριο (η προεπιλογή είναι 8), θα μετατραπεί σε κόκκινο-μαύρο δέντρο για να βελτιωθεί η αποτελεσματικότητα του ερωτήματος.Όταν η χωρητικότητα δεν είναι αρκετή, θα επεκταθεί αυτόματα Ο προεπιλεγμένος συντελεστής φορτίου είναι 0,75 και η μέθοδος επέκτασης είναι 2 φορές μεγαλύτερη από τη χωρητικότητα.

Πώς να προσδιορίσετε εάν μια συνδεδεμένη λίστα έχει κύκλο

1. Χρησιμοποιήστε έναν πίνακα κατακερματισμού για να διασχίσετε κάθε κόμβο στη συνδεδεμένη λίστα και να αποθηκεύσετε τη διεύθυνση του κόμβου στον πίνακα κατακερματισμού. Εάν ο τρέχων κόμβος υπάρχει ήδη στον πίνακα κατακερματισμού, αυτό σημαίνει ότι η συνδεδεμένη λίστα έχει έναν κύκλο.
2. Καθορίστε δύο δείκτες, ένας αργός δείκτης κινείται ένα βήμα τη φορά και ένας γρήγορος δείκτης κινείται δύο βήματα τη φορά Εάν ο γρήγορος δείκτης συναντήσει τον αργό δείκτη, σημαίνει ότι η συνδεδεμένη λίστα έχει έναν κύκλο.

Ποια είναι τα σενάρια χρήσης στοίβων και ουρών;

Λειτουργίες προς τα εμπρός και προς τα πίσω του προγράμματος περιήγησης: Οι ιστοσελίδες που επισκέπτεται το πρόγραμμα περιήγησης μπορούν να πραγματοποιήσουν τις λειτουργίες προς τα εμπρός και προς τα πίσω μέσω της δομής δεδομένων στοίβας.

Γνωρίζετε τίποτα για το πρόβλημα του tcp sticky;

Το πρόβλημα αλληλεπίδρασης TCP αναφέρεται στο γεγονός ότι το πρωτόκολλο TCP δεν κατακερματίζει τα δεδομένα κατά τη μετάδοση δεδομένων, με αποτέλεσμα η ποσότητα των δεδομένων που λαμβάνονται από το άκρο λήψης να είναι μεγαλύτερη από την ποσότητα των δεδομένων που αποστέλλονται από το άκρο αποστολής.

Οι τρόποι επίλυσης του προβλήματος κολλήματος TCP είναι:

1. Προσθήκη οριοθέτη στο άκρο αποστολής: Προσθήκη οριοθέτη στο άκρο αποστολής Αφού ο παραλήπτης λάβει τον οριοθέτη, μπορεί να διαχωρίσει τα δεδομένα με βάση τον οριοθέτη.
2. Προσθήκη κεφαλίδας στο τέλος αποστολής: Το άκρο αποστολής προσθέτει μια κεφαλίδα πριν από την αποστολή των δεδομένων Η κεφαλίδα περιέχει τις πληροφορίες μήκους των τρεχόντων δεδομένων.
3. Προσθήκη buffer στο τέλος αποστολής: Πριν από την αποστολή δεδομένων, το άκρο αποστολής τοποθετεί πρώτα τα δεδομένα στο buffer και στέλνει μόνο ένα μέρος των δεδομένων στο buffer κάθε φορά Μετά τη λήψη των δεδομένων, το άκρο λήψης καθορίζει εάν θα τα στείλει στοιχεία με βάση το συνολικό μήκος των δεδομένων.

Πώς να εφαρμόσετε ένα απλό TCP χρησιμοποιώντας UDP

Πρώτα απ 'όλα, τα datagrams UDP μπορούν να βοηθήσουν στην υλοποίηση της διαδικασίας τριπλής χειραψίας στο πρωτόκολλο TCP/IP. Στην πρώτη χειραψία, ένας πελάτης στέλνει ένα datagram UDP που περιέχει ένα αίτημα χειραψίας. Όταν ο διακομιστής λάβει αυτό το μήνυμα, θα απαντήσει με ένα μήνυμα επιβεβαίωσης, το οποίο υποδεικνύει ότι ο διακομιστής έχει λάβει το αίτημα χειραψίας του πελάτη και είναι έτοιμος να παρέχει υπηρεσίες. Στη δεύτερη χειραψία, ο πελάτης θα στείλει ξανά ένα datagram UDP Αυτή τη φορά το μήνυμα περιέχει ορισμένες χρήσιμες πληροφορίες, όπως τη διεύθυνση IP του πελάτη, τον αριθμό θύρας, κ.λπ., έτσι ώστε ο διακομιστής να μπορεί να αναγνωρίσει τον πελάτη. Στην τρίτη χειραψία, ο διακομιστής θα στείλει ένα datagram UDP που υποδεικνύει ότι η σύνδεση έχει δημιουργηθεί και ο πελάτης μπορεί να ξεκινήσει την αποστολή δεδομένων.

Δεύτερον, τα datagrams UDP μπορούν επίσης να βοηθήσουν στην υλοποίηση της διαδικασίας μετάδοσης δεδομένων στο πρωτόκολλο TCP/IP. Όταν ο πελάτης χρειάζεται να στείλει δεδομένα στον διακομιστή, τα δεδομένα θα ενσωματωθούν σε ένα datagram UDP και θα σταλούν στον διακομιστή αφού ο διακομιστής λάβει το datagram UDP, θα αναλύσει τα δεδομένα που περιέχονται στο μήνυμα και θα εκτελέσει σχετική επεξεργασία.

Τέλος, τα datagrams UDP μπορούν επίσης να βοηθήσουν στην υλοποίηση της διαδικασίας τερματισμού σύνδεσης στο πρωτόκολλο TCP/IP.Όταν ο πελάτης δεν χρειάζεται πλέον να επικοινωνεί με τον διακομιστή, μπορεί να στείλει ένα datagram UDP για να υποδείξει ότι ο πελάτης τερματίζει τη σύνδεση Αφού ο διακομιστής λάβει αυτό το μήνυμα, θα απελευθερώσει τους αντίστοιχους πόρους, ολοκληρώνοντας έτσι ολόκληρο το πρωτόκολλο TCP/IP. διαδικασία σύνδεσης

Έχετε χρησιμοποιήσει κορουτίνες; Γιατί να χρησιμοποιήσετε κορουτίνες;Γιατί οι κορουτίνες είναι πιο γρήγορες

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

Είναι πιο γρήγορο να διασχίσετε έναν πίνακα ή μια συνδεδεμένη λίστα του ίδιου μήκους; Γιατί;

Οι πίνακες είναι πιο γρήγοροι, επειδή η διεύθυνση κάθε στοιχείου του πίνακα είναι συνεχής και σταθερή και η διεύθυνση του επόμενου στοιχείου μπορεί να ληφθεί γρήγορα, ενώ η διεύθυνση κάθε στοιχείου της συνδεδεμένης λίστας είναι ασυνεχής και πρέπει να διασχίσετε τον δείκτη για να λάβετε τη διεύθυνση του επόμενου στοιχείου, ώστε ο πίνακας Traversing να είναι ταχύτερος.

Ας μιλήσουμε για εικονικές συναρτήσεις Γιατί χρειαζόμαστε εικονικές συναρτήσεις;

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

Μπορεί ο καταστροφέας να είναι εικονική συνάρτηση; Πρέπει να είναι εικονική συνάρτηση; Γιατί; Ποιο είναι το πρόβλημα αν δεν είναι εικονική λειτουργία;

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

Παρουσίαση του αγωγού απόδοσης

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

Η διαδικασία του αγωγού απόδοσης χωρίζεται σε τρία κύρια στάδια: στάδιο προετοιμασίας, στάδιο γεωμετρίας και στάδιο φωτισμού.

Στη φάση προετοιμασίας, η μηχανή παιχνιδιού φορτώνει τα μοντέλα και τις υφές της σκηνής του παιχνιδιού στη μονάδα επεξεργασίας γραφικών (GPU) και οργανώνει τα δεδομένα για χρήση σε επόμενες φάσεις.

Κατά το στάδιο της γεωμετρίας, χρησιμοποιούνται μετασχηματισμοί μήτρας για να τοποθετηθεί το μοντέλο σε τρισδιάστατο χώρο και να μετατραπεί το μοντέλο σε μια μορφή που μπορεί να υποστηριχθεί από pixel στην οθόνη.

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

Ας μιλήσουμε για τις λειτουργίες εισαγωγής, ερωτήματος και διαγραφής δυαδικών δέντρων αναζήτησης και ποια είναι η χρονική πολυπλοκότητα;

1. εισάγετε:

• Χρονική πολυπλοκότητα: O(log n)
• Βήματα:

1. Αντιμετωπίστε τον κόμβο που θα εισαχθεί ως νέο κόμβο φύλλου, ξεκινώντας από τον κόμβο ρίζας.
2. Εάν η τιμή του κόμβου που θα εισαχθεί είναι μικρότερη από την τρέχουσα τιμή του κόμβου, μεταβείτε στον αριστερό θυγατρικό κόμβο του τρέχοντος κόμβου.
3. Εάν η τιμή του κόμβου που θα εισαχθεί είναι μεγαλύτερη από την τρέχουσα τιμή του κόμβου, μεταβείτε στον δεξιό θυγατρικό κόμβο του τρέχοντος κόμβου.
4. Εάν ο τρέχων κόμβος δεν έχει θυγατρικούς κόμβους, ο κόμβος που θα εισαχθεί θα είναι ο θυγατρικός κόμβος του τρέχοντος κόμβου.
5. Διαφορετικά, επαναλάβετε τα βήματα 2 έως 4 έως ότου βρεθεί ένας κόμβος χωρίς θυγατρικούς κόμβους και ο κόμβος που θα εισαχθεί χρησιμοποιείται ως θυγατρικός κόμβος αυτού του κόμβου.

Ποιες είναι οι προϋποθέσεις για να αποκτήσει ο άπληστος αλγόριθμος τη βέλτιστη λύση;

Οι προϋποθέσεις για τον αλγόριθμο greedy να αποκτήσει τη βέλτιστη λύση είναι η "βέλτιστη υποδομή" και η "ιδιότητα greedy selection":

1. Βέλτιστη υποδομή: Η βέλτιστη λύση σε ένα πρόβλημα περιέχει τις βέλτιστες λύσεις στα υποπροβλήματα του προβλήματος.
2. Ιδιότητα άπληστης επιλογής: Σε κάθε βήμα, γίνεται μια τοπική βέλτιστη επιλογή και το τελικό αποτέλεσμα είναι η συνολική βέλτιστη λύση.