The deferred acceptance algorithm, also known as the GaleShapley algorithm, can be used to construct a stable matching of men and women. In this algorithm, members of one gender are the suitors and members of the other gender the suitees. The algorithm uses a sequence of rounds; in each round every suitor whose proposal was rejected in the previous round proposes to his or her highest ranking suitee who has not already rejected a proposal from this suitor. A suitee rejects all proposals except that from the suitor that this suitee ranks highest among all the suitors who have proposed to this suitee in this round or previous rounds. The proposal of this highest ranking suitor remains pending and is rejected in a later round if a more appealing suitor proposes in that round. The series of rounds ends when every suitor has exactly one pending proposal. All pending proposals are then accepted. 66. Show that the problem of deciding whether a specific program with a specific input halts is solvable.

3.1.66

Temukan pembahasan soal-soal dari buku ajar perkuliahan yang disusun oleh dosen-dosen terbaik. Solusi yang mendalam dan komprehensif dapat meningkatkan kemampuan kamu.

3.1.66

Beli untuk melihat jawaban ini

Soal Terkait

Copilot AI