Stable Marrige--稳定婚姻问题

Stable Marrige

算法第一次作业！！
part1:暴力求解，遍历所有可能组合，输出一对stable的
part2:普通的通过preferences list求解
part3:第二问基础上加上cost

其实第一问好像跑不出来的，时间复杂度无穷大（捂脸），不过后来我知道了用全排列搞出所有组合

package pro;
/*** Class to implement Stable Matching algorithms*/import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;public class Assignment1 {// Part1: Implement a Brute Force Solutionpublic static ArrayList stableMatchBruteForce(Preferences preferences) {ArrayList> prof_list=preferences.getProfessors_preference();ArrayList> stu_list=preferences.getStudents_preference();int prof_length=preferences.getProfessors_preference().size();int stu_length=preferences.getStudents_preference().size();//random arraylistArrayList p_match=randomMatching(prof_length);ArrayList s_match=new ArrayList();for(int i=0;iif(ifStable(p_match,s_match,preferences)) {p_match=randomMatching(prof_length);s_match=new ArrayList();for(int i=0;ireturn p_match;//prof opt}// Part2: Implement Gale-Shapley Algorithm，public static ArrayList stableMatchGaleShapley(Preferences preferences) {ArrayList> prof_list=preferences.getProfessors_preference();ArrayList> stu_list=preferences.getStudents_preference();int prof_length=preferences.getProfessors_preference().size();int stu_length=preferences.getStudents_preference().size();//save the status of whether they`re matched,and initialize ArrayList prof_match=new ArrayList();ArrayList stu_match=new ArrayList();for(int i=0;i1);stu_match.add(-1);}Queue q=new LinkedList();for(int i=0;i//insert element in the end, position 0 saves professor 1}//traverse prof，until emptyInteger prof_num=0;while((prof_num=q.poll())!=nul

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！