嗨，我
正在实现基于WikiLink的A *搜索算法，但我根本没有从我的搜索中得到答案。 关于我可能做错了什么的任何提示和/或帮助
我得到一张包含泥土和障碍物的地图，我需要前往所有污垢颗粒并将它们吸走并返回我的起点
搜索功能
private void search_Astar(State start){ // we have confirmed a valid start state
// needed vars
Map<State, Integer> g_score = new HashMap<>();
Map<State, Integer> f_score = new HashMap<>();
Queue<State> openQueue = new PriorityQueue<State>(((State o1, State o2) -> f_score.get(o1) - f_score.get(o2)));
HashSet<State> closedSet = new HashSet<>();
// inits
g_score.put(start, 0);
f_score.put(start, start.heuristic());
openQueue.add(start);
// search
while (!openQueue.isEmpty()){
State current = openQueue.poll();
if (current.isGoal()){
// create path
solutionStack.push(Actions.Turn_Off);
while (current.takenAction != null){
solutionStack.push(current.takenAction);
current = current.parent;
}
return;
}
closedSet.add(current);
for (String action:current.legalActions()){
State child = current.CreateState(action);
if (closedSet.contains(child)) continue;
int tentativeG = g_score.get(current) + 1; // the cost to take an action
if (!openQueue.contains(child)) openQueue.add(child);
else if (tentativeG >= g_score.getOrDefault(child, Integer.MAX_VALUE)) continue;
g_score.put(child, tentativeG);
f_score.put(child, tentativeG + child.heuristic());
}
}
}
和州级（对不起巨大）
import java.util.ArrayList;
import java.util.Collection;
public class State {
// keep track of position and orientation
public Orientation orientation;
public Position position;
public boolean turned_on;
// track world state
private Collection<Position> dirt;
private Collection<Position> obstacles;
private Position size;
// variables for detirmining goal state and heuristic
private Position home;
// for calculating G
public State parent;
public String takenAction;
public State(Position position, Orientation orientation, boolean turned_on, Collection dirt, Collection obs, Position home,
Position size, State parent, String action) {
this.position = position;
this.orientation = orientation;
this.turned_on = turned_on;
this.dirt = dirt;
this.obstacles = obs;
this.home = home;
this.size = size;
this.parent = parent;
this.takenAction = action;
}
public int G(){
State curr = parent;
int total = 0;
while (curr != null){
total += 1;
curr = parent.parent;
}
return total;
}
public String toString() {
return "State{position: " + position + ", orientation: " + orientation + ", on:" + turned_on + "}";
}
@Override
public int hashCode(){
int hashVal = 23;
hashVal = ((hashVal + position.x) << 5) - (hashVal + position.x);
hashVal = ((hashVal + position.y) << 5) - (hashVal + position.y);
if(turned_on){
hashVal += 1243;
}
if (orientation == Orientation.NORTH){
hashVal += 12;
}else if (orientation == Orientation.EAST){
hashVal += 2234;
}else if (orientation == Orientation.WEST){
hashVal += 32345;
}
return hashVal + dirt.size();
}
@Override
public boolean equals(Object o){
if (o instanceof State){
State other = (State)o;
if(!other.position.equals(this.position)){
return false;
}else if( other.turned_on != this.turned_on){
return false;
}else if( other.orientation != this.orientation){
return false;
}else if (other.dirt.size() != this.dirt.size()){
return false;
} else{
return true;
}
}else {
return false;
}
}
/**
* check to see if current node is a valid goal node
*
* @return true if valid, false otherwise
*/
public Boolean isGoal(){
return dirt.isEmpty() && position.equals(home);
}
/**
* Calculate all legal moves from current state
*
* @return Collection of legal actions (as string)
*/
public Collection<String> legalActions(){
Collection<String> actions = new ArrayList<String>();
if (!turned_on){
actions.add(Actions.Turn_On);
}else{
// no reason we couldn't turn
actions.add(Actions.Turn_Left);
actions.add(Actions.Turn_Right);
if (dirt.contains(position)){
actions.add(Actions.Suck);
}
// check if we can move forward
// ATTENTION this must be at bottom of function
if (orientation == Orientation.NORTH){
for (Position o: obstacles) {
if (o.y == position.y + 1 && o.x == position.x || position.y == size.y){
return actions;
}
}
// we have checked every obstacle and we would not collide
actions.add(Actions.Go);
}else if (orientation == Orientation.SOUTH){
for (Position o: obstacles) {
if (o.y == position.y - 1 && o.x == position.x || position.y == 1){
return actions;
}
}
actions.add(Actions.Go);
}else if (orientation == Orientation.WEST){
for (Position o: obstacles) {
if (o.x == position.x - 1 && o.y == position.y|| position.x == 1){
return actions;
}
}
actions.add(Actions.Go);
}else {
// we are pointing east
for (Position o: obstacles) {
if (o.x == position.x + 1 && o.y == position.y|| position.x == size.x){
return actions;
}
}
actions.add(Actions.Go);
}
}
return actions;
}
/**
* return a value to determine how optimal this state is
*
* evaluation methood: number of dirt left times a constant
* which is the added to the distance to the closest dirt
* if there are no dirts left it is the mannhatan distance to home
*
* note: should add state depth?
* @return int
*/
public int heuristic(){
int h = 0;
for (Position p:obstacles){
h += mannhatandist(p);
}
h += mannhatandist(home);
return h + dirt.size();
}
private int mannhatandist(Position p){
return Math.abs(p.x - position.x) + Math.abs(p.y - position.y);
}
private int distToClosest(){
int min = Integer.MAX_VALUE;
if (dirt.isEmpty()){
int dist = Math.abs(home.x - position.x) + Math.abs(home.y - position.y);
return dist;
}
for (Position p: dirt) {
int dist = Math.abs(p.x - position.x) + Math.abs(p.y - position.y);
min = Math.min(min, dist);
}
if (!turned_on) min++;
return min;
}
public State CreateState(String action) {
//Copy the "old" values from the current state.
//Before any action done, the "new" state has the same values.
Position new_position = new Position(position.x, position.y);
Orientation new_orientation = orientation;
boolean new_turned_on = turned_on;
Collection new_dirt = new ArrayList(dirt);
State new_parent = this;
//If the action is to turn the robot on, the turned_on variable for the new state takes the value "true".
if(action == "TURN_ON") {
new_turned_on = true;
}
//If the action is to turn the robot on, the turned_on variable for the new state takes the value "true".
else if(action == "TURN_OFF") {
new_turned_on = false;
}
//If the action is to suck, the current position needs to be taken out of the new state's dirt collection.
else if(action == "SUCK") {
new_dirt.remove(position);
}
//If the action is to go it depends on the orientation of the robot how the position of the new state will change.
else if(action == "GO") {
//If it's facing north, the y position increases by one, considering the old state and so on.
if(orientation == Orientation.NORTH) {
new_position.y++;
}
else if(orientation == Orientation.EAST) {
new_position.x++;
}
else if(orientation == Orientation.SOUTH) {
new_position.y--;
}
else {
new_position.x--;
}
}
//If the action is to turn left it depends on the orientation of the robot in the current state what the new orientation will be.
else if(action == "TURN_LEFT") {
if(orientation == Orientation.NORTH) {
new_orientation = Orientation.WEST;
}
else if(orientation == Orientation.EAST) {
new_orientation = Orientation.NORTH;
}
else if(orientation == Orientation.SOUTH) {
new_orientation = Orientation.EAST;
}
else {
new_orientation = Orientation.SOUTH;
}
}
//If the action is to turn right it depends on the orientation of the robot in the current state what the new orientation will be.
else if(action == "TURN_RIGHT") {
if(orientation == Orientation.NORTH) {
new_orientation = Orientation.EAST;
}
else if(orientation == Orientation.EAST) {
new_orientation = Orientation.SOUTH;
}
else if(orientation == Orientation.SOUTH) {
new_orientation = Orientation.WEST;
}
else {
new_orientation = Orientation.NORTH;
}
}
//Make a new state from the new variables that have been changed according to the action done.
State new_state = new State(new_position, new_orientation, new_turned_on, new_dirt, obstacles, home, size, new_parent, action);
return new_state;
}
}
我现在已经修复了它。 问题是我的启发式不一致。我已经修改了它，它现在性能正常
我不会分享我的答案，因为这是针对学校项目的，并且由于学校的自动反作弊系统可能会检测到这一点，我将在此评论中添加我的学校用户名（dagur13）
附言当我收到项目的成绩时，我将发布更新的代码