Минимальное сокращение по Karger MinCut Java Большая ошибка ввода
Я работаю и пытаюсь это исправить некоторое время. На самом деле прошло довольно много недель, но у меня закончились возможные решения или модификации. Таким образом, алгоритм является рандомизированным алгоритмом минимального разреза Каргера, и моя реализация представлена ниже:
Алгоритм:
Это для неориентированного графа. Каждая вершина хранится в виде ключа в hashmap, а смежные вершины хранятся в виде массива в значениях hashmap, например, для
если контрольный пример:
1 2 6
2 1 3 4 5
3 2 4
4 2 3 5
5 2 4 6
6 1 5
где первый столбец - это ключи, а числа рядом с ними - его значения (arraylist).
мой алгоритм
- Выберите первую встречающуюся вершину с именем "i", имеющую более 2 смежных вершин (в данном случае 2)
- Хотя в списке "i" более двух чисел
- Выберите случайным образом соседнюю вершину, которая называется "U"
- Слияние "U" с "i" (слияние с другой вершиной с именем "V" не дает правильного ответа)
- Теперь проверьте, состоит ли новый список "i" из самого "i", и удалите его. (Self Loop)
- Перекрестная ссылка нового списка "i" на другие вершины
Удалите "U" (ключ), например, если "U" было 6, обновленные вершины будут выглядеть так:
1 2 6 2 2 1 3 4 5 1 5 3 2 4 4 2 3 5 5 2 4 6 2Следовательно, когда "i" будет иметь уникальный номер, алгоритм завершится (это делается путем добавления списка "i" в Set). Например:
2 6 6 6 2 2
Так что это 2 минимальных разреза для данного графика.
Код:
Мой код для вышеупомянутого алгоритма в Java следующим образом:
package practice;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class MinCut {
static Map <Integer,ArrayList <Integer>> vertices=new HashMap <Integer,ArrayList <Integer>>() ;
static Random random= new Random ();
static int SIZE=0;
static TreeSet <Integer> minSize= new TreeSet <Integer> ();
static int reps=0;
static ArrayList <Integer> uTracker= new ArrayList <Integer> ();
public static void main(String[] args) {
int reps2=0;
for (int i=0;i<=10;i++){
minCutCalc();
TreeSet <Integer> trackSet= new TreeSet <Integer> ();
if (!uTracker.isEmpty()){
Collections.sort(uTracker);
for (int o=0;o<uTracker.size();o++){
System.out.println("uTracker: "+uTracker.get(o));
if (!trackSet.add(uTracker.get(o))){
reps2++;
}
}
//to check "U"s in every run
uTracker.clear();
}
}
//prints the lowest number in the set hence the minimum cut
System.out.println("The attempted minimum cut is: "+minSize.first());
System.out.println("FINAL REPS: "+reps2);
}
private static void minCutCalc() {
readMap();
int i=0;
i=selectVertex(1);
//for testing purposes
System.out.println(" \"i\" is: "+i);
if (vertices.get(i) != null){
Set <Integer> tempSet= new LinkedHashSet <Integer> ();
while (vertices.get(i).size()>2){
/*to remove any instances of "i" copied into list from other vertices
* to avoid getting "i" selected as "U" in random numbers as then "U"
* will be deleted hence showing result as "null"
*/
for (int l=0;l<vertices.get(i).size();l++){
for (int c=0;c<vertices.get(i).size();c++){
if (vertices.get(i).get(c)==i){
int index=vertices.get(i).indexOf(i);
System.out.println("Yes it contains "+i+": "+vertices.get(i).get(index));
vertices.get(i).remove(index);
}
}
}
//for testing purposes
System.out.println("\"i\" is: "+i);
for (int j=0;j<vertices.get(i).size();j++){
System.out.println("\n"+"LIST DISPLAY: "+vertices.get(i).get(j));
}
if (!tempSet.isEmpty()){
tempSet.clear();
}
tempSet.addAll(vertices.get(i));
//if there is only one occurrence of a number in the list
if (tempSet.size()==1){
break;
}
int U=selectRandom(i,vertices);
//for testing purposes
System.out.println("PRINT u: "+U);
//to check if unique "U"s are selected each time
uTracker.add(U);
for (int n=0;n<vertices.get(U).size();n++){
System.out.println("\"U\" List: "+vertices.get(U).get(n));
}
//merging "U"'s vertices to "i"
if (vertices.containsKey(U)){
vertices.get(i).addAll(vertices.get(U));
for (int y=0;y<vertices.get(U).size();y++){
System.out.println(vertices.get(U).get(y));
//cross referencing "i" to rest of the vertices in "U"'s list
if (vertices.get(U).get(y)!=i){
vertices.get(vertices.get(U).get(y)).add(i);
}
}
}
vertices.remove(U);
//if any of the vertices consists of "U" as its edge it will be deleted
for (int t=1;t<=SIZE;t++){
if (vertices.containsKey(t)){
for (int y=0;y<vertices.get(t).size();y++){
for (int z=0;z<vertices.get(t).size();z++){
if (vertices.get(t).get(z)==U){
int index=vertices.get(t).indexOf(U);
vertices.get(t).remove(index);
}
}
}
}
}
//for testing purposes
System.out.println("\"i\" is: "+i);
for (int j=0;j<vertices.get(i).size();j++){
System.out.println("LIST \"AFTER\" DISPLAY: "+vertices.get(i).get(j));
}
//null check
if (vertices.get(i)==null){
System.out.println("This is null: "+i);
break;
}
}
}
//to check the final result
for (int o=1;o<=SIZE;o++){
System.out.println(" SHOW at "+o+" index: "+vertices.get(o));
if (vertices.get(o)!=null){
//minimum cuts (size of current list) are added to a set
minSize.add(vertices.get(o).size());
}
}
System.out.println("Total Number of Repititions: "+reps);
}
private static void readMap() {
try {
FileReader file= new FileReader("C:\\xyz\\Desktop\\testMinCut.txt");
BufferedReader reader= new BufferedReader(file);
String line="";
while ((line=reader.readLine())!=null){
String [] lineArr;
lineArr=line.split("\t");
int vert1=Integer.parseInt(lineArr[0]);
vertices.put(vert1,new ArrayList <Integer> ());
for (int p=1;p<lineArr.length;p++){
int vert2=Integer.parseInt(lineArr[p]);
vertices.get(vert1).add(vert2);
}
}
SIZE=vertices.size();
} catch (FileNotFoundException e) {
System.err.println(e.toString());
} catch (IOException e) {
System.err.println(e.toString());
}
}
private static int selectVertex(int i) {
LinkedHashSet <Integer> storer= new LinkedHashSet <Integer> ();
for (int s=1;s<=SIZE;s++){
if (vertices.get(s)!=null){
if (!storer.isEmpty()){
storer.clear();
}
storer.addAll(vertices.get(s));
if (storer.size()>2){
i=s;
break;
}
else {
i=0;
}
}
}
return i;
}
private static int selectRandom(int i, Map<Integer, ArrayList<Integer>> vertices) {
int u;
int U = 0;
LinkedHashSet <Integer> tempSet2= new LinkedHashSet <Integer> ();
tempSet2.addAll(vertices.get(i));
u=random.nextInt(tempSet2.size());
Set <Integer> uSet=new HashSet <Integer> ();
Set <Integer> uSet2=new HashSet <Integer> ();
//to reassure unique "u" is selected each time
if (!uSet.isEmpty() && uSet.contains(u)){
u=random.nextInt(tempSet2.size());
reps++;
}
uSet.add(u);
U=vertices.get(i).get(u);
//ensuring unique "U" is selected
if (uSet2.contains(U)){
u=random.nextInt(tempSet2.size());
U=vertices.get(i).get(u);
reps++;
}
uSet2.add(U);
tempSet2.clear();
return U;
}
}
Проблема:
Проблема, с которой я сталкиваюсь, состоит в том, что этот алгоритм прекрасно работает почти для всех тестовых случаев, с которыми я сталкивался, за исключением одного очень большого тестового случая, состоящего из 200 вершин. Правильный ответ должен быть 17, но я продолжаю получать мой ответ как "20". Я отслеживал все выбранные буквы "U". По-видимому, все они уникальны без повторов, и я продолжаю получать ответ "20". Любой совет, пожалуйста? Еще раз спасибо. Ссылка на контрольный пример:
http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt
NB:
Это не домашнее задание, а практический вопрос, над которым я работаю и который я увидел в онлайн-курсе (Разработка и анализ алгоритмов) на Coursera. Курс окончен. Заранее большое спасибо. Я снова задаю этот вопрос, так как не смог получить ответ с первого раза. Я был бы признателен за любую предложенную помощь, так как я сказал, что этот вопрос сказывается на мне, так как я работаю над ним в течение достаточно долгого времени.
1 ответ
Поэтому мне удалось заставить его работать и получить правильный ответ. Проблема была в случайном выборе ребра. Так как я сначала выбирал вершину (у которой было более 2 ребер), а затем ребро из этой вершины, что было неправильным подходом, так как не все ребра равномерно распределены по вершинам. Итак, вот мой улучшенный алгоритм:
Держите список всех ребер в наборе
- Хотя в списке ребер осталось более 2 ребер
- Выберите случайное ребро из списка ребер и назовите его V
- Затем выберите другое случайное ребро из V (поскольку моя реализация - HashMap, поэтому получите список значений, являющийся массивом для значения ключа, "V") и назовите его "U".
- Объедините U & V, чтобы сделать комбинированный край
- Удалите U из списка ребер (поскольку я объединил список U, то есть его ребра были обозначены как V, поэтому объединенное ребро было просто V, поэтому после объединения U & V стало супер ребром, называемым просто "V")
Надеюсь, это было бы полезно для кого-то.