我正在研究这个问题，在给定一组三元组的情况下找到最小的三元组，这组三元组在所有三个维度上都是最小的。但是，如果存在一个三元组，其最小的是任何一个或两个维度，而不是所有三个维度中最小的一个，那也需要考虑。
示例
我举个例子。 说吧，我的三胞胎如下
(25, 30, 34), (15, 31, 21), (10, 40, 21), (50, 30, 34), (25, 30, 10), (9, 20, 15)
现在，(9,20,15) 看起来是所有三个维度中最小的。但是，还存在一个选项 (25,30,10) 在第三个维度中最小，因为它在第三个维度中的得分 (10) 比任何其他选项都最小，因此也需要包含在输出中也。所以最终输出将是 {(9,20,15) and (25,30,10)}
因此，基本上应该考虑一个解决方案，如果它是显性的或最优的。我可以如下定义这些
1. Dominant : If an outcome o is at least as good for another agent as another outcome o' and there is some
agent who strictly prefers o to o'. Then o pareto-dominates o'
2. Optimal : o* is pareto-optimal if it isn't pareto-dominated by anything else
我的算法
这是我的算法。请参阅随附的代码。假设这三个维度分别称为 Course1Score、Course2Score 和 Course3Score。
所以我遍历输入，并为以下每一个找到最小的
1.{Course1Score}
2.{Course2Score}
3.{Course3Score}
4.{Course1Score, Course2Score}
5.{Course1Score, Course3Score}
6.{Course2Score, Course3Score}
7.{Course1Score, Course2Score, Course3Score}
然后我在最小化上述目标的解决方案中找到了不同的解决方案。
假案
现在这适用于大多数情况，除了下面的情况。让输入为 (1,100,100), (100,1,100), (100,100,1), (1,1,1) 根据上述算法，最小化上述目标的分数如下
1.Minimize {Course1Score} - (1,100,100)
(remember this won't be over-written by say,(1,1,1) since Course1Score of (1,1,1) IS NOT LESS than Course1Score of (1,100,100) which comes first in the order of inputs) )
2.Minimize {Course2Score} - (100,1,100)
3.Minimize {Course3Score} - (100,100,1)
4.Minimize {Course1Score, Course2Score} - (1,100,100)
5.Minimize {Course1Score, Course3Score} - (1,100,100)
6.Minimize {Course2Score, Course3Score} - (100,1,100)
7.Minimize {Course1Score, Course2Score, Course3Score} - (1,1,1)
继续算法，我们找到不同的解决方案并将它们报告为 (1,100,100)、(100,1,100)、(100,100,1)、(1,1,1) 但是，这个解决方案是不正确的。由于 (1,1,1) 在所有三个维度上都击败了所有其他解决方案，并且 (1,100,100)、(100,1,100)、(100,100,1) 在任何方面都优于 (1,1,1)尺寸。所以，我添加了一个额外的条件来检查这个可以在函数中找到的末尾
在线 java fiddle
这是一个 online java fiddle我的实现
我的实现
请找到我的代码
import java.util.ArrayList;
/* Glossary
* 1. Dominant : If an outcome o is at least as good for another agent as another outcome o' and there is some
* agent who strictly prefers o to o'. Then o Triplet-dominates o'
*
* 2. Optimal : o* is Triplet-optimal if it isn't Triplet-dominated by anything else
*
* */
public class HelloWorld
{
public static void main(String[] args)
{
Triplet myTriplet = new Triplet();
/* Populating input and printing them */
System.out.println("Printing input");
myTriplet.PopulateSampleInput();
myTriplet.Print(myTriplet.options);
/* Printing the Triplet-Optimal solutions */
ArrayList<Option> TripletSolutions = myTriplet.FindTripletOptimalSolutions();
System.out.println("Printing TripletSolutions : ");
myTriplet.Print(TripletSolutions);
}
}
class Triplet
{
ArrayList<Option> options;
public Triplet()
{
options = new ArrayList<Option>();
}
void PopulateSampleInput()
{
Option option1 = new Option(25, 30, 34);
Option option2 = new Option(15, 31, 21);
Option option3 = new Option(10, 40, 21);
Option option4 = new Option(50, 30, 34);
Option option5 = new Option(25, 30, 10);
Option option6 = new Option(9, 20, 15);
options.add(option1);
options.add(option2);
options.add(option3);
options.add(option4);
options.add(option5);
options.add(option6);
}
void Print(ArrayList<Option> al)
{
for(int i = 0;i< al.size();i++)
{
System.out.println(al.get(i).Course1Score + "," + al.get(i).Course2Score + "," + al.get(i).Course3Score);
}
}
ArrayList<Option> FindTripletOptimalSolutions()
{
Option[] map = new Option[7];
/* Initialization : Initially the best solution for minimizing all objectives is the first solution */
for(int i = 0;i<map.length;i++)
map[i] = options.get(0);
for(int i=1;i<options.size();i++)
{
/* Fixing {1} */
if(options.get(i).Course1Score < map[0].Course1Score)
map[0] = options.get(i);
/* Fixing {2} */
if(options.get(i).Course2Score < map[1].Course2Score)
map[1] = options.get(i);
/* Fixing {3} */
if(options.get(i).Course3Score < map[2].Course3Score)
map[2] = options.get(i);
/* Fixing {1,2} */
if(options.get(i).Course1Score <= map[3].Course1Score && options.get(i).Course2Score <= map[3].Course2Score)
map[3] = options.get(i);
/* Fixing {1,3} */
if(options.get(i).Course1Score <= map[4].Course1Score && options.get(i).Course3Score <= map[4].Course3Score)
map[4] = options.get(i);
/* Fixing {2,3} */
if(options.get(i).Course2Score <= map[5].Course2Score && options.get(i).Course3Score <= map[5].Course3Score)
map[5] = options.get(i);
/* Fixing {1,2,3} */
if(options.get(i).Course1Score <= map[6].Course1Score && options.get(i).Course2Score <= map[6].Course2Score && options.get(i).Course3Score <= map[6].Course3Score)
map[6] = options.get(i);
}
/* find unique solutions */
ArrayList<Option> DistinctSolutions = new ArrayList<Option>();
DistinctSolutions = findUnique(map);
/* keeping only solutions that add something new */
ArrayList<Option> TripletSolutions = EliminateWeakSolutionInCaseOfTie(DistinctSolutions);
return TripletSolutions;
}
/* This function returns the unique solutions, otherwise, they will cancel out each other inside the
* EliminateWeakSolutionInCaseOfTie function that comes next */
ArrayList<Option> findUnique(Option[] map)
{
ArrayList<Option> TripletSolutions = new ArrayList<Option>();
for(int i = 0;i<map.length;i++)
{
if(!TripletSolutions.contains(map[i]))
TripletSolutions.add(map[i]);
}
return TripletSolutions;
}
/* This function in case of ties where map[0]'s Course1Score is only equal to, but not less than
* map[6]'s Course1Score, which in addition to minimizing Course1Score, also minimizes
* Course2Score and Course3Score */
ArrayList<Option> EliminateWeakSolutionInCaseOfTie(ArrayList<Option> DistinctSolutions)
{
ArrayList<Option> TripletSolutions = new ArrayList<Option>();
int Include = 1;
for(int i = 0;i<DistinctSolutions.size();i++,Include=1)
{
for(int j = 0;j<DistinctSolutions.size();j++)
{
if(i!=j && DistinctSolutions.get(j).Course1Score <= DistinctSolutions.get(i).Course1Score && DistinctSolutions.get(j).Course2Score <= DistinctSolutions.get(i).Course2Score && DistinctSolutions.get(j).Course3Score <= DistinctSolutions.get(i).Course3Score)
{
Include = 0;
break;
}
}
if(Include == 1)
TripletSolutions.add(DistinctSolutions.get(i));
}
return TripletSolutions;
}
}
class Option
{
int Course1Score;
int Course2Score;
int Course3Score;
public Option(int Course1Score, int Course2Score, int Course3Score)
{
// TODO Auto-generated constructor stub
this.Course1Score = Course1Score;
this.Course2Score = Course2Score;
this.Course3Score = Course3Score;
}
}
您能否为上述建议一个算法，和/或查看我的算法和实现？
编辑:我认为这个解决方案有效
伪代码
ParetoSolutionPool[1] = input[1]
for(i in 2:input)
boolean ParetoDominant = false;
boolean ParetoOptimal = true;
for(j in 1:ParetoSolutionPool)
if(input[i] ParetoDominates ParetoSolutionPool[j])
remove ParetoSolutionPool[j]
ParetoDominant = true;
if(input[i] IsParetoDominatedBy ParetoSolutionPool[j])//extra if(ParetoDominant == false && ParetoOptimal == true && above)
ParetoOptimal = false;
end of for loop over j
if(ParetoDominant || ParetoOptimal == true)
add input[i] to ParetoSolutionPool
end of for loop over i
伪代码
基本上，两次检查。 1.如果一个输入/选项占主导地位(在所有三个维度上都较低)，则现有解决方案之一会弹出该“现有解决方案”，并由该输入替换，因为它一致更好。 (例如 25、30、10 优于 25、30、34)
2.如果一个输入(在所有三个维度上)不比任何现有解决方案差，那么它也必须被考虑到解决方案池中。
所以基本上在上述两种情况中的任何一种情况下，都会将输入添加到解决方案池中。两者之间的唯一区别在于，在第一种情况下，较弱的现有解决方案也会被弹出。
代码
package TripletOptimizationAlgorithms;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
public class algo4
{
public static void main(String[] args)
{
Triplet myTriplet = new Triplet();
/* Populating input and printing them */
System.out.println("Printing input");
//myTriplet.PopulateSampleInput();
myTriplet.PopulateSampleInputFromFile();
myTriplet.Print(myTriplet.options);
System.out.println("Number of inputs read=="+myTriplet.options.size());
/* Printing the Triplet-Optimal solutions */
final long startTime = System.currentTimeMillis();
ArrayList<Option> TripletSolutions = myTriplet.FindTripletOptimalSolutions();
final long endTime = System.currentTimeMillis();
System.out.println("Printing TripletSolutions : ");
myTriplet.Print(TripletSolutions);
System.out.println("Total execution time: " + (endTime - startTime) + " milliseconds" );
}
}
class Triplet
{
ArrayList<Option> options;
public Triplet()
{
options = new ArrayList<Option>();
}
void PopulateSampleInput()
{
Option option1 = new Option(25, 30, 34);
Option option2 = new Option(15, 31, 21);
Option option3 = new Option(10, 40, 21);
Option option4 = new Option(30, 30, 34);
Option option5 = new Option(25, 30, 10);
Option option6 = new Option(9, 20, 15);
options.add(option1);
options.add(option2);
options.add(option3);
options.add(option4);
options.add(option5);
options.add(option6);
}
void PopulateSampleInputFromFile()
{
try
{
String pwd = Paths.get(".").toAbsolutePath().normalize().toString();
String inputpath = pwd + "/src/TripletOptimizationAlgorithms/myinput.txt";
FileInputStream fstream = new FileInputStream(inputpath);
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
while ((strLine = br.readLine()) != null)
{
String[] tokens = strLine.split(" ");
Option myoption = new Option(Integer.parseInt(tokens[0]),Integer.parseInt(tokens[1]),Integer.parseInt(tokens[2]));//process record , etc
options.add(myoption);
}
in.close();
}
catch (Exception e)
{
System.err.println("Error: " + e.getMessage());
}
}
void Print(ArrayList<Option> al)
{
for(int i = 0;i< al.size();i++)
{
System.out.println(al.get(i).Course1Score + "," + al.get(i).Course2Score + "," + al.get(i).Course3Score);
}
}
ArrayList<Option> FindTripletOptimalSolutions()
{
/* Initialization : Initialize the TripletSolutions to be the first option */
ArrayList<Option> TripletSolutions = new ArrayList<Option>();
TripletSolutions.add(options.get(0));
/* looping across input */
for(int i = 1;i<options.size();i++)
{
boolean TripletDominant = false;
boolean TripletOptimal = true;
Option optionUnderCheck = options.get(i);
ArrayList<Integer> IndicesToRemove = new ArrayList<Integer>();
/* looping across TripletSolutions */
for(int j = 0;j<TripletSolutions.size();j++)
{
if(isTripletDominant(optionUnderCheck, TripletSolutions.get(j)) == true)
{
TripletDominant = true;
IndicesToRemove.add(j);
}
if(IsTripletDominatedBy(optionUnderCheck, TripletSolutions.get(j)) == true)
{
TripletOptimal = false;
}
}
/* the weaker solutions have to be removed */
if(TripletDominant == true)
{
Collections.sort(IndicesToRemove, Collections.reverseOrder());
for(int k = 0;k<IndicesToRemove.size();k++)
{
TripletSolutions.remove(IndicesToRemove.get(k).intValue());
}
}
if(TripletDominant == true || TripletOptimal == true)
TripletSolutions.add(optionUnderCheck);
}
return TripletSolutions;
}
boolean isTripletDominant(Option optionUnderCheck, Option existingSolution)
{
if(optionUnderCheck.Course1Score <= existingSolution.Course1Score && optionUnderCheck.Course2Score <= existingSolution.Course2Score && optionUnderCheck.Course3Score <= existingSolution.Course3Score)
return true;
return false;
}
boolean IsTripletDominatedBy(Option optionUnderCheck, Option existingSolution)
{
if(optionUnderCheck.Course1Score >= existingSolution.Course1Score && optionUnderCheck.Course2Score >= existingSolution.Course2Score && optionUnderCheck.Course3Score >= existingSolution.Course3Score)
return true;
return false;
}
}
class Option
{
int Course1Score;
int Course2Score;
int Course3Score;
public Option(int Course1Score, int Course2Score, int Course3Score)
{
// TODO Auto-generated constructor stub
this.Course1Score = Course1Score;
this.Course2Score = Course2Score;
this.Course3Score = Course3Score;
}
}
最佳答案
其实这个可以简化很多。
因此，让我们看一下您的匹配规则:
- {Course1Score} 最低
- {Course2Score} ...
- {Course3Score} ...
- {Course1Score, Course2Score} 最佳或主导解决方案
- {Course1Score, Course3Score} ...
- {Course2Score, Course3Score} ...
- {Course1Score, Course2Score, Course3Score} ...
规则 1、2 和 3 只是搜索最小化 CourseNScore 的值(将 N 替换为规则编号)。 4,5 和 6 搜索对 (a , b)(用相应的 CourseScore 替换 a 和 b)，使得存在没有与较低的 a 或 b 配对。这些对也可以通过规则 1 - 3 找到，无论它们是显性的还是最优的。同样适用于规则 7 和规则 4 - 6。
因此，我们可以轻松地将搜索减少到找到 1 个元素最少的元组，并减少匹配集。这将大大加快搜索速度。这将产生 3 组元组(一组用于搜索的元组的每个元素)。
下一步:
减少找到的元组集。这可以通过一种非常幼稚的方法来完成:
匹配规则 7 的解决方案必须在搜索生成的所有集中。符合规则 4 的解决方案必须在符合规则 1 和 2 的集合中。
因此，减少结果成为一项非常微不足道的任务。
评论:
Java 中的变量名和方法名通常是小写的。
从 Option 生成 String 的部分，就像在 Triplet.Print 中使用的那样，应该转移到 Option.toString()，因为这是通常的方式。但是这段代码没有什么可批评的。
关于java - 给定一组选项找到最小的三元组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34032097/