实施 Prim 算法的策略模式

Question

我正在为一个项目使用 Dijkstra 算法，但想尝试使用 Strategy Pattern 实现 Prims 算法，看看它有什么更好的，但我不确定如何使用 Strategy Pattern。我以前从未使用过模式，所以我不知道从哪里开始。

package wpi.cs509.routeFinder;

import wpi.cs509.dataModel.*;
import wpi.cs509.dataManager.*;

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class RouteFinder {

public static ArrayList<Point> computePaths(Point source, Graph g, Point destination)
{
    if(source.getId()==destination.getId()){
        ArrayList<Point> point=new ArrayList<Point>();
        point.add(source);
        return point;
    }
    source.minDistance = 0;
    PriorityQueue<Point> pointQueue = new PriorityQueue<Point>();
    pointQueue.add(source);

while (!pointQueue.isEmpty()) {
    Point u = pointQueue.poll();

        // Visit each edge exiting u
        for (Edge e : g.getNeighbors(u))
        {
            Point v = g.getPointById(e.getePointId()!=u.getId()?e.getePointId():e.getsPointId());
            float weight = e.getWeight();
            double distanceThroughU = u.minDistance + weight;
    if (distanceThroughU < v.minDistance) {
        pointQueue.remove(v);
        v.minDistance = distanceThroughU ;
        v.previous = u;
        pointQueue.add(v);
      //  System.out.println("u.id is"+u.getId());
            }
        }
    }
return getShortestPathTo(g.getPointById(destination.getId()));

}

public static ArrayList<Point> getShortestPathTo(Point destination)
{
    ArrayList<Point> path = new ArrayList<Point>();
    for (Point vertex = destination; vertex != null; vertex = vertex.previous)
    { 
        path.add(vertex);
    }

    Collections.reverse(path);
    return path;
}



public static void main(String[] args){
    Graph g = new Graph();
    ArrayList<Point> p = new ArrayList<Point>();
    //g=DataManager.getGraphByNameWithDB("testLab",2);
    Point source = new Point();
    source.setId(11);
    source.setX(111);
    source.setY(222);
    source.setBuildingName("testLab");
    source.setFloorNum(2);
    source.setMapEntrance(false);
    source.setDestination(true);
    source.setName("source");


    Point end = new Point();
    end.setId(15);
    end.setX(161);
    end.setY(616);
    end.setBuildingName("testLab");
    end.setFloorNum(2);
    end.setMapEntrance(false);
    end.setDestination(true);
    end.setName("end");

    p=computePaths(source,g,end);
    System.out.println(p.size());
    for(int i =0;i<p.size();i++)
    {
        System.out.println("result is "+p.get(i).getId());
    }
}
}

Answer 1

策略模式旨在将算法放入class，其中数据确保相同，这样算法就可以针对多个数据副本重复使用，而无需创建新的实例策略来处理它们。

除非你真的需要这种行为，否则我建议你不要使用策略模式开始，因为这在某种程度上削弱了面向对象的设计（通过分离数据和行为）。

相反，尝试使用 Route 接口，它有两个实现 DikstraRoute 和 PimsRoute。然后，您的顶级代码将只处理 Routes，而不需要处理它们的实现。

界面

public interface Route {
   public ArrayList<Point> getPath();
}

您的构造函数可能看起来像

public DikstraRoute implements Route {
   public DikstraRoute(Point start, Graph g, Point destination) {
     ...
   }

   @Override
   public ArrayList<Point> getPath() {
     ...
   }
}

public PimsRoute implements Route {
   public PimsRoute(Point start, Graph g, Point destination) {
     ...
   }

   @Override
   public ArrayList<Point> getPath() {
     ...
   }
}

接口是 "getPath()" 操作的保证。

它是一种面向对象的语言，可能时不时要写几个对象。随着时间的推移，全静态编程方式不会为您提供任何类型的维护优势（因此它也可能是 C）。

如果你发现（在打了这个中间之后）你毕竟真的需要一个策略，那么将你传递给构造函数的对象移动到接口中的方法中。删除您在之前（以上）解决方案中拥有的任何内部字段，并且您会将 Route 对象转换为 Route 策略。请记住，如果您的对象仅包含代码，但不包含状态，则它实际上是一种策略。

为了演示，策略方法看起来像

界面

public interface Route {
   public ArrayList<Point> getPath(Point start, Graph g, Point destination);
}

您的构造函数可能看起来像

public DikstraRoute implements Route {
   public DikstraRoute() {
     ...
   }

   @Override
   public ArrayList<Point> getPath(Point start, Graph g, Point destination) {
     ...
   }
}

public PimsRoute implements Route {
   public PimsRoute() {
     ...
   }

   @Override
   public ArrayList<Point> getPath(Point start, Graph g, Point destination) {
     ...
   }
}

实施 Prim 算法的策略模式

Strategy Pattern implementing Prim's Algorithm

java

dijkstra

strategy-pattern

prims-algorithm