java - 实现 Prim 算法的策略模式

Question

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

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

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

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

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

界面

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() {
     ...
   }
}

接口(interface)保证了“getPath()”操作。

它是一种面向对象的语言，可能时不时地需要编写一些对象。随着时间的推移，全静态的编程方式不会为您提供任何类型的维护优势(所以它还不如 C)。

如果您发现(在达到这个中间值之后)您确实需要一个策略，那么请将您传递给构造函数的对象移动到接口(interface)中的方法中。剪切之前(上面)解决方案中的所有内部字段，您将把 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) {
     ...
   }
}